2 papers
cs.CC2021
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Jacob Focke, Dániel Marx, Paweł Rzążewski
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 grap…
cs.CC2018
The Complexity of Approximately Counting Retractions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
Let be a graph that contains an induced subgraph . A retraction from to is a homomorphism from to that is the identity function on . Retractions are very…