graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a fractional isomorphism of

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

s whose adjacency matrices are denoted ''A'' and ''B'' is a

doubly stochastic matrix In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e., :\sum_i x_=\sum_j x_ ...

''D'' such that ''DA'' = ''BD''. If the doubly stochastic matrix is a

permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permutation of elements. ...

, then it constitutes a

graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...

. Fractional isomorphism is the coarsest of several different relaxations of

Computational complexity

Whereas the

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational c ...

is not known to be decidable in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

and not known to be

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, the fractional graph isomorphism problem is decidable in polynomial time because it is a special case of the

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

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 In mathematical optimization and computer science, a feasible region, feasible set, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, ...

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 In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...

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

References

{{reflist, refs= {{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 {{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 {{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 Fractional graph theory

Computational complexity

Equivalence to coarsest equitable partition

See also

References