cispa_all_3514.pdf (869.74 kB)

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

conference contribution

posted on 2023-11-29, 18:19 authored by Jacob FockeJacob Focke, Dániel MarxDániel Marx, Paweł RzążewskiThe 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)\subseteq V(H) for every v\in V(G), a list homomorphism is a function f:V(G)\to V(H) that preserves the edges (i.e., uv\in E(G) implies f(u)f(v)\in E(H)) and respects the lists (i.e., f(v)\in 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\cdot n^O(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) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S\subseteq 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.
It follows from earlier results that if irr(H)=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard.
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\cdot n^O(1) if a tree decomposition of G having width at most t is given in the input, and
- given that irr(H)\ge 2, cannot be counted in time (irr(H)-\epsilon)^t\cdot n^O(1) for any \epsilon>0, even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#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

## Preferred Citation

Jacob Focke, Dániel Marx and Paweł Rzążewski. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2022.## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM-SIAM Symposium on Discrete Algorithms (SODA)## Legacy Posted Date

2021-11-08## Open Access Type

- Green

## BibTeX

@inproceedings{cispa_all_3514, title = "Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds", author = "Focke, Jacob and Marx, Dániel and Rzążewski, Paweł", booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}", year="2022", }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC