License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.84
URN: urn:nbn:de:0030-drops-145246
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14524/
Go to the corresponding LIPIcs Volume Portal


Peyerimhoff, Norbert ; Roth, Marc ; Schmitt, Johannes ; Stix, Jakob ; Vdovina, Alina

Parameterized (Modular) Counting and Cayley Graph Expanders

pdf-format:
LIPIcs-MFCS-2021-84.pdf (0.8 MB)


Abstract

We study the problem #EdgeSub(Φ) of counting k-edge subgraphs satisfying a given graph property Φ in a large host graph G. Building upon the breakthrough result of Curticapean, Dell and Marx (STOC 17), we express the number of such subgraphs as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients.
Our approach relies on novel constructions of low-degree Cayley graph expanders of p-groups, which might be of independent interest. The properties of those expanders allow us to analyse the coefficients in the aforementioned linear combinations over the field 𝔽_p which gives us significantly more control over the cancellation behaviour of the coefficients. Our main result is an exhaustive and fine-grained complexity classification of #EdgeSub(Φ) for minor-closed properties Φ, closing the missing gap in previous work by Roth, Schmitt and Wellnitz (ICALP 21).
Additionally, we observe that our methods also apply to modular counting. Among others, we obtain novel intractability results for the problems of counting k-forests and matroid bases modulo a prime p. Furthermore, from an algorithmic point of view, we construct algorithms for the problems of counting k-paths and k-cycles modulo 2 that outperform the best known algorithms for their non-modular counterparts.
In the course of our investigations we also provide an exhaustive parameterized complexity classification for the problem of counting graph homomorphisms modulo a prime p.

BibTeX - Entry

@InProceedings{peyerimhoff_et_al:LIPIcs.MFCS.2021.84,
  author =	{Peyerimhoff, Norbert and Roth, Marc and Schmitt, Johannes and Stix, Jakob and Vdovina, Alina},
  title =	{{Parameterized (Modular) Counting and Cayley Graph Expanders}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{84:1--84:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14524},
  URN =		{urn:nbn:de:0030-drops-145246},
  doi =		{10.4230/LIPIcs.MFCS.2021.84},
  annote =	{Keywords: Cayley graphs, counting complexity, expander graphs, fine-grained complexity, parameterized complexity}
}

Keywords: Cayley graphs, counting complexity, expander graphs, fine-grained complexity, parameterized complexity
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI