Lower bound found for graph comparison using bounded treewidth graphs
An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability
Discrete Mathematics
Summary
Sometimes people compare two graphs by counting certain patterns coming from smaller graphs. This paper looks at how big these smaller graphs need to be to tell two bigger graphs apart based on a property called treewidth. The authors prove a new almost-best possible lower limit on the size of these smaller graphs, showing they must be very large in some cases. This helps understand how complex these comparisons must be.
What this means in practice
- •For graph algorithm designers: Establishes fundamental limits on the graph sizes needed to distinguish graphs using bounded treewidth methods, guiding efficient algorithm design.
- •For machine learning engineers: Clarifies complexity boundaries of features based on graph homomorphisms relevant to graph neural networks and related learning models.
A theory result. No direct application yet.
Authors
Moritz Lichter, Harry Vinall-Smeeth
Abstract
One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. This is the field of homomorphism distinguishability which has gained a lot of traction in recent years. In this paper, we study the case where $\mathcal{H}$ is the class of graphs of treewidth $k$. This has connections to important concepts in logic, machine learning, combinatorial optimization and proof complexity. In particular, Dvořák showed that $G_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ are distinguishable by the $k$-dimensional Weisfeiler-Leman algorithm. While the relation between the iteration number of this algorithm and the depth of the tree-decomposition of a distinguishing graph is understood, our understanding of the \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/2})}$ lower bound on the size of a graph of treewidth $k$ required to distinguish two graphs of order $n$. This bound is proved via a new combinatorial game along with a construction which uses a recent compression technique for CFI graphs. It is almost tight to the known $2^{O(n^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.