Jump to content

Fractional graph isomorphism

From Wikipedia, the free encyclopedia

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.[1][2] Fractional isomorphism is the coarsest of several different relaxations of graph isomorphism.[3]

Computational complexity[edit]

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.[2]

Equivalence to coarsest equitable partition[edit]

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).[1][2]

See also[edit]

References[edit]

  1. ^ a b Scheinerman, Edward; Ullman, Daniel (1997). "Chapter 6: Fractional Isomorphism". Fractional Graph Theory. John Wiley & Sons. pp. 127–151. ISBN 0-471-17864-0.
  2. ^ a b c Ramana, Motakuri V.; Scheinerman, Edward R.; Ullman, Daniel (1994). "Fractional isomorphism of graphs". Discrete Mathematics. 132 (1–3): 247–265. doi:10.1016/0012-365X(94)90241-0. MR 1297385.
  3. ^ Mančinska, Laura; Roberson, David E.; Šámal, Robert; Severini, Simone; Varvitsiotis, Antonios (2017). "Relaxations of graph isomorphism". In Chatzigiannakis, Ioannis; Indyk, Piotr; Kuhn, Fabian; Muscholl, Anca (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:10.4230/LIPICS.ICALP.2017.76.