Homomorphism Tensors and Linear Equations

Advances in Combinatorics

Abstract

[Graph isomorphism](https://en.wikipedia.org/wiki/Graph_isomorphism_problem) 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](https://en.wikipedia.org/wiki/Weisfeiler_Leman_graph_isomorphism_test): 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.

Authors 3

1. Martin Grohe Aachen

   RWTH Aachen University · ORCID

   Affiliation as printed

   ORCID iD: 0000-0002-0292-9142

   RWTH Aachen University

2. Gaurav Rattan Aachen

   RWTH Aachen University · University of Twente · ORCID

   Affiliation as printed

   ORCID iD: 0000-0002-5095-860X

   University of Twente

   RWTH Aachen University

3. Tim Seppelt Aachen

   RWTH Aachen University · IT University of Copenhagen · ORCID

   Affiliation as printed

   IT-Universitetet i København

   ORCID iD: 0000-0002-6447-0568

   RWTH Aachen University