ITU

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

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

Standard

Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. / Curticapean, Radu-Cristian; Dell, Holger; Husfeldt, Thore.

Proceedings of the 29th Annual European Symposium on Algorithms. Vol. 204 Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2021. 34.

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

Harvard

Curticapean, R-C, Dell, H & Husfeldt, T 2021, Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. in Proceedings of the 29th Annual European Symposium on Algorithms. vol. 204, 34, Schloss Dagstuhl--Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2021.34

APA

Curticapean, R-C., Dell, H., & Husfeldt, T. (2021). Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In Proceedings of the 29th Annual European Symposium on Algorithms (Vol. 204). [34] Schloss Dagstuhl--Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2021.34

Vancouver

Curticapean R-C, Dell H, Husfeldt T. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In Proceedings of the 29th Annual European Symposium on Algorithms. Vol. 204. Schloss Dagstuhl--Leibniz-Zentrum für Informatik. 2021. 34 https://doi.org/10.4230/LIPIcs.ESA.2021.34

Author

Curticapean, Radu-Cristian ; Dell, Holger ; Husfeldt, Thore. / Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. Proceedings of the 29th Annual European Symposium on Algorithms. Vol. 204 Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2021.

Bibtex

@inproceedings{d51dcde5ec044d8fafcbd15635254bfd,
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).",
author = "Radu-Cristian Curticapean and Holger Dell and Thore Husfeldt",
year = "2021",
doi = "10.4230/LIPIcs.ESA.2021.34",
language = "English",
volume = "204",
booktitle = "Proceedings of the 29th Annual European Symposium on Algorithms",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik",

}

RIS

TY - GEN

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

AU - Curticapean, Radu-Cristian

AU - Dell, Holger

AU - Husfeldt, Thore

PY - 2021

Y1 - 2021

N2 - 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).

AB - 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).

U2 - 10.4230/LIPIcs.ESA.2021.34

DO - 10.4230/LIPIcs.ESA.2021.34

M3 - Article in proceedings

VL - 204

BT - Proceedings of the 29th Annual European Symposium on Algorithms

PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik

ER -

ID: 86408104