Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters

Abstract

A homomorphism from a graph G to a graph H is an edge-preserving mapping from V (G) to V (H). In the graph homomorphism problem, denoted by Hom(H), the graph H is fixed and we need to determine if there exists a homomorphism from an instance graph G to H. We study the complexity of the problem parameterized by the cutwidth of G, i.e., we assume that G is given along with a linear ordering v1, . . ., vn of V (G) such that, for each i ∈ {1, . . ., n − 1}, the number of edges with one endpoint in {v1, . . ., vi} and the other in {vi+1, . . ., vn} is at most k. We aim, for each H, for algorithms for Hom(H) running in time c^k_Hn^O(1) and matching lower bounds that exclude c^k_H^·o⁽¹⁾n^O(1) or c^k_H^(1−Ω(1))n^O(1) time algorithms under the (Strong) Exponential Time Hypothesis. In the paper we introduce a new parameter that we call mimsup(H). Our main contribution is strong evidence of a close connection between cH and mimsup(H): an information-theoretic argument that the number of states needed in a natural dynamic programming algorithm is at most mimsup(H)^k, lower bounds that show that for almost all graphs H indeed we have cH ≥ mimsup(H), assuming the (Strong) Exponential-Time Hypothesis, and an algorithm with running time exp(O(mimsup(H) · k log k))n^O(1). In the last result we do not need to assume that H is a fixed graph. Thus, as a consequence, we obtain that the problem of deciding whether G admits a homomorphism to H is fixed-parameter tractable, when parameterized by cutwidth of G and mimsup(H). The parameter mimsup(H) can be thought of as the p-th root of the maximum induced matching number in the graph obtained by multiplying p copies of H via a certain graph product, where p tends to infinity. It can also be defined as an asymptotic rank parameter of the adjacency matrix of H. Such parameters play a central role in, among others, algebraic complexity theory and additive combinatorics. Our results tightly link the parameterized complexity of a problem to such an asymptotic matrix parameter for the first time.