Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Modular counting of subgraphs : Matchings, matching-splittable graphs, and paths

Curticapean, Radu ; Dell, Holger and Husfeldt, Thore LU (2021) 29th Annual European Symposium on Algorithms, ESA 2021 In Leibniz International Proceedings in Informatics, LIPIcs 204.
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... (More)

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

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Counting complexity, Matchings, Parameterized complexity, Paths, Subgraphs
host publication
29th Annual European Symposium on Algorithms, ESA 2021
series title
Leibniz International Proceedings in Informatics, LIPIcs
editor
Mutzel, Petra ; Pagh, Rasmus and Herman, Grzegorz
volume
204
article number
34
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
29th Annual European Symposium on Algorithms, ESA 2021
conference location
Vitual, Lisbon, Portugal
conference dates
2021-09-06 - 2021-09-08
external identifiers
  • scopus:85115050589
ISSN
1868-8969
ISBN
9783959772044
DOI
10.4230/LIPIcs.ESA.2021.34
language
English
LU publication?
yes
id
6a7e7bcd-fa2e-46c8-aec8-1516a6e74c2a
date added to LUP
2021-10-01 15:07:17
date last changed
2022-04-27 04:21:19
@inproceedings{6a7e7bcd-fa2e-46c8-aec8-1516a6e74c2a,
  abstract     = {{<p>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<sup>f</sup>(t,s<sup>)</sup>-time algorithm to compute modulo 2<sup>t</sup> 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<sup>t</sup>. 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).</p>}},
  author       = {{Curticapean, Radu and Dell, Holger and Husfeldt, Thore}},
  booktitle    = {{29th Annual European Symposium on Algorithms, ESA 2021}},
  editor       = {{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}},
  isbn         = {{9783959772044}},
  issn         = {{1868-8969}},
  keywords     = {{Counting complexity; Matchings; Parameterized complexity; Paths; Subgraphs}},
  language     = {{eng}},
  month        = {{09}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics, LIPIcs}},
  title        = {{Modular counting of subgraphs : Matchings, matching-splittable graphs, and paths}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ESA.2021.34}},
  doi          = {{10.4230/LIPIcs.ESA.2021.34}},
  volume       = {{204}},
  year         = {{2021}},
}