Journal article
Parameterized counting of partially injective homomorphisms
- 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 # 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 595.0KB, Terms of use)
-
- Publisher copy:
- 10.1007/s00453-021-00805-y
Authors
- Publisher:
- Springer
- Journal:
- Algorithmica More from this journal
- Volume:
- 832
- Issue:
- 2021
- Pages:
- 1829–1860
- Publication date:
- 2021-03-11
- Acceptance date:
- 2021-01-15
- DOI:
- EISSN:
-
1432-0541
- ISSN:
-
0178-4617
- Language:
-
English
- Keywords:
- Pubs id:
-
1170522
- Local pid:
-
pubs:1170522
- Deposit date:
-
2022-02-01
Terms of use
- Copyright holder:
- Marc Roth.
- Copyright date:
- 2021
- Rights statement:
- © The Author(s) 2021. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record