ITU

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

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

View graph of relations

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
Volume204
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication date2021
Article number34
DOIs
Publication statusPublished - 2021

Downloads

No data available

ID: 86408104