Fractional graph isomorphism
In graph theory, a fractional isomorphism of graphs whose adjacency matrices are denoted A and B is a doubly stochastic matrix D such that DA = BD. If the doubly stochastic matrix is a permutation matrix, then it constitutes a graph isomorphism.{{r|fgt|rsu}} Fractional isomorphism is the coarsest of several different relaxations of graph isomorphism.{{r|mrssv}}
Computational complexity
Whereas the graph isomorphism problem is not known to be decidable in polynomial time and not known to be NP-complete, the fractional graph isomorphism problem is decidable in polynomial time because it is a special case of the 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 of a linear program.{{r|rsu}}
Equivalence to coarsest equitable partition
Two graphs are also fractionally isomorphic if they have a common coarsest equitable partition. A partition 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 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).{{r|fgt|rsu}}
See also
References
{{reflist|refs=
| last1 = Mančinska | first1 = Laura
| last2 = Roberson | first2 = David E.
| last3 = Šámal | first3 = Robert
| last4 = Severini | first4 = Simone | author4-link = Simone Severini
| last5 = Varvitsiotis | first5 = Antonios
| editor1-last = Chatzigiannakis | editor1-first = Ioannis
| editor2-last = Indyk | editor2-first = Piotr | editor2-link = Piotr Indyk
| editor3-last = Kuhn | editor3-first = Fabian
| editor4-last = Muscholl | editor4-first = Anca | editor4-link = Anca Muscholl
| contribution = Relaxations of graph isomorphism
| doi = 10.4230/LIPICS.ICALP.2017.76
| pages = 76:1–76:14
| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10–14, 2017, Warsaw, Poland
| volume = 80
| year = 2017| doi-access = free
}}
| last1 = Ramana | first1 = Motakuri V.
| last2 = Scheinerman | first2 = Edward R.
| last3 = Ullman | first3 = Daniel
| doi = 10.1016/0012-365X(94)90241-0
| issue = 1–3
| journal = Discrete Mathematics
| mr = 1297385
| pages = 247–265
| title = Fractional isomorphism of graphs
| volume = 132
| year = 1994}}
}}