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]
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]