Modular counting of subgraphs : Matchings, matching-splittable graphs, and paths
(2021) 29th Annual European Symposium on Algorithms, ESA 2021 In Leibniz International Proceedings in Informatics, LIPIcs 204.- 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 nf(t,s)-time algorithm to compute modulo 2t 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 2t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is... (More)
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 nf(t,s)-time algorithm to compute modulo 2t 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 2t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is ModqW[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).
(Less)
- author
- Curticapean, Radu ; Dell, Holger and Husfeldt, Thore LU
- organization
- publishing date
- 2021-09-01
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Counting complexity, Matchings, Parameterized complexity, Paths, Subgraphs
- host publication
- 29th Annual European Symposium on Algorithms, ESA 2021
- series title
- Leibniz International Proceedings in Informatics, LIPIcs
- editor
- Mutzel, Petra ; Pagh, Rasmus and Herman, Grzegorz
- volume
- 204
- article number
- 34
- publisher
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- conference name
- 29th Annual European Symposium on Algorithms, ESA 2021
- conference location
- Vitual, Lisbon, Portugal
- conference dates
- 2021-09-06 - 2021-09-08
- external identifiers
-
- scopus:85115050589
- ISSN
- 1868-8969
- ISBN
- 9783959772044
- DOI
- 10.4230/LIPIcs.ESA.2021.34
- language
- English
- LU publication?
- yes
- id
- 6a7e7bcd-fa2e-46c8-aec8-1516a6e74c2a
- date added to LUP
- 2021-10-01 15:07:17
- date last changed
- 2022-04-27 04:21:19
@inproceedings{6a7e7bcd-fa2e-46c8-aec8-1516a6e74c2a, abstract = {{<p>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<sup>f</sup>(t,s<sup>)</sup>-time algorithm to compute modulo 2<sup>t</sup> 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<sup>t</sup>. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is ModqW[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).</p>}}, author = {{Curticapean, Radu and Dell, Holger and Husfeldt, Thore}}, booktitle = {{29th Annual European Symposium on Algorithms, ESA 2021}}, editor = {{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}}, isbn = {{9783959772044}}, issn = {{1868-8969}}, keywords = {{Counting complexity; Matchings; Parameterized complexity; Paths; Subgraphs}}, language = {{eng}}, month = {{09}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, series = {{Leibniz International Proceedings in Informatics, LIPIcs}}, title = {{Modular counting of subgraphs : Matchings, matching-splittable graphs, and paths}}, url = {{http://dx.doi.org/10.4230/LIPIcs.ESA.2021.34}}, doi = {{10.4230/LIPIcs.ESA.2021.34}}, volume = {{204}}, year = {{2021}}, }