Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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).
Original languageEnglish
Title of host publicationProceedings of the 29th Annual European Symposium on Algorithms
Number of pages17
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication date2021
Article number34
Publication statusPublished - 2021


Dive into the research topics of 'Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths'. Together they form a unique fingerprint.

Cite this