2026-07-24T08:33:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14615 2024-03-06T10:54:27Z ddc:004 open_access

Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths Curticapean, Radu Dell, Holger Husfeldt, Thore Counting complexity matchings paths subgraphs parameterized complexity 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Radu Curticapean and Holger Dell and Thore Husfeldt 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.34 urn:nbn:de:0030-drops-146154 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.34 eng https://creativecommons.org/licenses/by/4.0/legalcode