In [[graph theory]], a '''fractional isomorphism of [[Graph (discrete mathematics)|graph]]s''' whose [[adjacency matrix|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 [[Relaxation (approximation)|relaxations]] of [[graph isomorphism]].{{r|mrssv}}
==Computational complexity== Whereas the [[graph isomorphism problem]] is not known to be decidable in [[time complexity#Polynomial time|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 [[Basic feasible solution|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 set|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== * [[Graph isomorphism]] * [[Fibrations of graphs]]
==References== <references>
<ref name=fgt>{{cite book | last1=Scheinerman | first1=Edward | author1-link = Ed Scheinerman | last2=Ullman | first2=Daniel | title=Fractional Graph Theory | year=1997 | url=http://www.ams.jhu.edu/~ers/fgt/ | publisher=John Wiley & Sons | isbn=0-471-17864-0 | chapter = Chapter 6: Fractional Isomorphism|pages=127–151}}</ref>
<ref name=mrssv>{{cite conference | 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 }}</ref>
<ref name=rsu>{{cite journal | 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}}</ref>
</references>
[[Category:Fractional graph theory]]