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