Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.34
URN: urn:nbn:de:0030-drops-146154
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14615/
Curticapean, Radu ; Dell, Holger ; Husfeldt, Thore
Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths
| pdf-format: |
|
Abstract
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of k-matchings can be determined in polynomial time by a simple reduction to the determinant. We generalize this to an n^{f(t,s)}-time algorithm to compute modulo 2^t the number of subgraph occurrences of patterns that are s vertices away from being matchings. This shows that the known polynomial-time cases of subgraph detection (Jansen and Marx, SODA 2015) carry over into the setting of counting modulo 2^t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is {Mod}_q W[1]-complete and prove that counting k-paths modulo 2 is ⊕W[1]-complete, answering an open question by Björklund, Dell, and Husfeldt (ICALP 2015).
BibTeX - Entry
@InProceedings{curticapean_et_al:LIPIcs.ESA.2021.34,
author = {Curticapean, Radu and Dell, Holger and Husfeldt, Thore},
title = {{Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {34:1--34:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14615},
URN = {urn:nbn:de:0030-drops-146154},
doi = {10.4230/LIPIcs.ESA.2021.34},
annote = {Keywords: Counting complexity, matchings, paths, subgraphs, parameterized complexity}
}
| Keywords: | Counting complexity, matchings, paths, subgraphs, parameterized complexity | |
| Seminar: | 29th Annual European Symposium on Algorithms (ESA 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 31.08.2021 |
