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. Fractional isomorphism is the coarsest of several different relaxations of graph isomorphism.

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.

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).

See also

• Graph isomorphism