Parameterized Counting of Partially Injective Homomorphisms
Author:
Open Access
- 11 March 2021
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 83 (6) , 1829-1860
Abstract
We study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixed-parameter tractable and $$\#\mathsf {W[1]}$$ -complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS 16) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC 17). Moreover, we invoke Rota’s NBC-Theorem to obtain an explicit criterion for fixed-parameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs.
Keywords
This publication has 52 references indexed in Scilit:
- An approximation trichotomy for Boolean #CSPJournal of Computer and System Sciences, 2010
- Strong computational lower bounds via parameterized complexityJournal of Computer and System Sciences, 2006
- Counting H-colorings of partial k-treesTheoretical Computer Science, 2002
- Counting trees in a graph is #P-completeInformation Processing Letters, 1994
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Homomorphisms of derivative graphsDiscrete Mathematics, 1971
- On the foundations of combinatorial theory I. Theory of M bius FunctionsProbability Theory and Related Fields, 1964
- Dimer Statistics and Phase TransitionsJournal of Mathematical Physics, 1963
- The statistics of dimers on a latticePhysica, 1961
- Dimer problem in statistical mechanics-an exact resultPhilosophical Magazine, 1961