CISPA
Browse

Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds

Download (859.49 kB)
Version 2 2024-01-26, 13:19
Version 1 2024-01-26, 09:01
journal contribution
posted on 2024-01-26, 13:19 authored by Jacob FockeJacob Focke, Dániel MarxDániel Marx, Rzążewski Paweł

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L(v)⊆V(H) for every v∈V(G), a {\em list homomorphism} is a function f:V(G)→V(H) that preserves the edges (i.e., uv∈E(G) implies f(u)f(v)∈E(H)) and respects the lists (i.e., f(v)∈L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time |V(H)|t⋅nO(1). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H we define irr(H) the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S⊆V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. We show that, for every fixed graph H, the number of list homomorphisms from (G,L) to H

* can be counted in time irr(H)t⋅nO(1) if a tree decomposition of G having width at most t is given in the input, and

* cannot be counted in time (irr(H)−ϵ)t⋅nO(1) for any ϵ>0, even if a tree decomposition of G having width at most t is given in the input, unless the #SETH fails.

Thereby we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

Journal

ACM Transactions on Algorithms

Publisher

ACM

Sub Type

  • Article

BibTeX

@article{Focke:Marx:Paweł:2024, title = "Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds", author = "Focke, Jacob" AND "Marx, Dániel" AND "Paweł, Rzążewski", year = 2024, month = 1, journal = "ACM Transactions on Algorithms", publisher = "ACM", issn = "1549-6325" }