Homomorphism Tensors and Linear Equations

Graph isomorphism is a fundamental computational complexity problem, which concerns determining whether two input graphs are isomorphic. While this problem, which clearly belongs to the class NP, is not known to be polynomial-time solvable, it is not NP-complete unless the polynomial hierarchy collapses to its second level. Perhaps, the most well-known heuristic algorithm for the problem is the Weisfeiler-Leman algorithm: the algorithm initially colors all vertices of the input graphs by the same color and in each round, recolors each vertex by a new color representing the multiset of colors assigned to its neighbors. In particular, the color of each vertex after the first round corresponds to its degree.

By a classical result of Lovász, two graphs $G$ and $H$ are isomorphic if and only if the number of homomorphisms from every graph $F$ to $G$ is the same as the number of homomorphisms from $F$ to $H$. When the choice of $F$ is restricted to trees, two graphs $G$ and $H$ are distinguishable by the numbers of homomorphisms from $F$ if and only if the Wesfeiler-Leman algorithm distinguishes them. More generally, two graphs are distinguishable by the number of homomorphisms from graphs with treewidth at most $k$ if and only if the $k$-dimensional extension of the Wesfeiler-Leman algorithm distinguishes them. This is equivalent to the existence of a non-negative fractional isomorphism with variables associated with $k$-vertex partial isomorphisms; such fractional isomorphisms are Sherali-Adams linear relaxations of the (integer) isomorphism problem. The algebraic methods developed in this paper yield the following result, which can be viewed as sandwiched between the Sherali-Adams levels: two graphs are distinguishable by the number of homomorphisms from graphs with pathwidth at most $k$ if and only if there exists a fractional isomorphism with variables associated with $k$-vertex partial isomorphisms.