@inproceedings{6a7e7bcdfa2e46c8aec81516a6e74c2a,
title = "Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths",
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 ModqW[1]-complete and prove that counting k-paths modulo 2 is ⊕W[1]-complete, answering an open question by Bj{\"o}rklund, Dell, and Husfeldt (ICALP 2015).",
keywords = "Counting complexity, Matchings, Parameterized complexity, Paths, Subgraphs",
author = "Radu Curticapean and Holger Dell and Thore Husfeldt",
year = "2021",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.ESA.2021.34",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Petra Mutzel and Rasmus Pagh and Grzegorz Herman",
booktitle = "29th Annual European Symposium on Algorithms, ESA 2021",
note = "29th Annual European Symposium on Algorithms, ESA 2021 ; Conference date: 06-09-2021 Through 08-09-2021",
}