# Fractional graph isomorphism

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Fractional_graph_isomorphism
> Markdown URL: https://mediated.wiki/source/Fractional_graph_isomorphism.md
> Source: https://en.wikipedia.org/wiki/Fractional_graph_isomorphism
> Source revision: 1341667881
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [graph theory](/source/Graph_theory), a **fractional isomorphism of [graphs](/source/Graph_(discrete_mathematics))** whose [adjacency matrices](/source/Adjacency_matrix) are denoted *A* and *B* is a [doubly stochastic matrix](/source/Doubly_stochastic_matrix) *D* such that *DA* = *BD*. If the doubly stochastic matrix is a [permutation matrix](/source/Permutation_matrix), then it constitutes a [graph isomorphism](/source/Graph_isomorphism).[1][2] Fractional isomorphism is the coarsest of several different [relaxations](/source/Relaxation_(approximation)) of [graph isomorphism](/source/Graph_isomorphism).[3]

## Computational complexity

Whereas the [graph isomorphism problem](/source/Graph_isomorphism_problem) is not known to be decidable in [polynomial time](/source/Time_complexity#Polynomial_time) and not known to be [NP-complete](/source/NP-complete), the fractional graph isomorphism problem is decidable in polynomial time because it is a special case of the [linear programming](/source/Linear_programming) problem, for which there is an efficient solution. More precisely, the conditions on matrix *D* that it be doubly stochastic and that *DA* = *BD* can be expressed as linear inequalities and equalities, respectively, so any such matrix *D* is a [feasible solution](/source/Basic_feasible_solution) of a linear program.[2]

## Equivalence to coarsest equitable partition

Two graphs are also fractionally isomorphic if they have a common coarsest [equitable partition](/source/Equitable_partition). A [partition](/source/Partition_of_a_set) of a graph is a collection of pairwise disjoint sets of vertices whose union is the vertex set of the graph. A partition is equitable if for any pair of vertices *u* and *v* in the same block of the partition and any block *B* of the partition, both *u* and *v* have the same number of neighbors in *B*. An equitable partition *P* is coarsest if each block in any other equitable partition is a subset of a block in *P*. Two coarsest equitable partitions *P* and *Q* are common if there is a [bijection](/source/Bijection) *f* from the blocks of *P* to the blocks of *Q* such for any blocks *B* and *C* in *P*, the number of neighbors in *C* of any vertex in *B* equals the number of neighbors in *f(C)* of any vertex in *f(B)*.[1][2]

## See also

- [Graph isomorphism](/source/Graph_isomorphism)

- [Fibrations of graphs](/source/Fibrations_of_graphs)

## References

1. ^ [***a***](#cite_ref-fgt_1-0) [***b***](#cite_ref-fgt_1-1) [Scheinerman, Edward](/source/Ed_Scheinerman); Ullman, Daniel (1997). "Chapter 6: Fractional Isomorphism". [*Fractional Graph Theory*](http://www.ams.jhu.edu/~ers/fgt/). John Wiley & Sons. pp. 127–151. [ISBN](/source/ISBN_(identifier)) [0-471-17864-0](https://en.wikipedia.org/wiki/Special:BookSources/0-471-17864-0).

1. ^ [***a***](#cite_ref-rsu_2-0) [***b***](#cite_ref-rsu_2-1) [***c***](#cite_ref-rsu_2-2) Ramana, Motakuri V.; Scheinerman, Edward R.; Ullman, Daniel (1994). "Fractional isomorphism of graphs". *Discrete Mathematics*. **132** (1–3): 247–265. [doi](/source/Doi_(identifier)):[10.1016/0012-365X(94)90241-0](https://doi.org/10.1016%2F0012-365X%2894%2990241-0). [MR](/source/MR_(identifier)) [1297385](https://mathscinet.ams.org/mathscinet-getitem?mr=1297385).

1. **[^](#cite_ref-mrssv_3-0)** Mančinska, Laura; Roberson, David E.; Šámal, Robert; [Severini, Simone](/source/Simone_Severini); Varvitsiotis, Antonios (2017). "Relaxations of graph isomorphism". In Chatzigiannakis, Ioannis; [Indyk, Piotr](/source/Piotr_Indyk); Kuhn, Fabian; [Muscholl, Anca](/source/Anca_Muscholl) (eds.). *44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10–14, 2017, Warsaw, Poland*. LIPIcs. Vol. 80. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 76:1–76:14. [doi](/source/Doi_(identifier)):[10.4230/LIPICS.ICALP.2017.76](https://doi.org/10.4230%2FLIPICS.ICALP.2017.76).

---
Adapted from the Wikipedia article [Fractional graph isomorphism](https://en.wikipedia.org/wiki/Fractional_graph_isomorphism) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Fractional_graph_isomorphism?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.