2 Search Results for "Stix, Jakob"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.7

Parameterised Holant Problems

Authors: Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We investigate the complexity of parameterised holant problems p-Holant(𝒮) for families of symmetric signatures 𝒮. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures 𝒮: Depending on the signatures, p-Holant(𝒮) is either 1) solvable in "FPT-near-linear time", i.e., in time f(k)⋅ 𝒪̃(|x|), or 2) solvable in "FPT-matrix-multiplication time", i.e., in time f(k)⋅ {𝒪}(n^{ω}), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or 3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)⋅ {𝒪}(n^{ω}). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(𝒮), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(𝒮) is different: Depending on 𝒮 all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).

Cite as

Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt. Parameterised Holant Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aivasiliotis_et_al:LIPIcs.ICALP.2025.7,
  author =	{Aivasiliotis, Panagiotis and G\"{o}bel, Andreas and Roth, Marc and Schmitt, Johannes},
  title =	{{Parameterised Holant Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.7},
  URN =		{urn:nbn:de:0030-drops-233842},
  doi =		{10.4230/LIPIcs.ICALP.2025.7},
  annote =	{Keywords: holant problems, counting problems, parameterised algorithms, fine-grained complexity theory, homomorphisms}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2021.84

Parameterized (Modular) Counting and Cayley Graph Expanders

Authors: Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

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.

Cite as

Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2021.84},
  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}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2021

Refine by Author
2 Roth, Marc
2 Schmitt, Johannes
1 Aivasiliotis, Panagiotis
1 Göbel, Andreas
1 Peyerimhoff, Norbert
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
2 Theory of computation → Problems, reductions and completeness
1 Mathematics of computing → Combinatorics
1 Mathematics of computing → Graph algorithms
1 Mathematics of computing → Graph theory
1 Theory of computation → Parameterized complexity and exact algorithms

Refine by Keyword
1 Cayley graphs
1 counting complexity
1 counting problems
1 expander graphs
1 fine-grained complexity
Show More...

2 Search Results for "Stix, Jakob"

Parameterised Holant Problems

Abstract

Cite as

Parameterized (Modular) Counting and Cayley Graph Expanders

Abstract

Cite as

Thanks for your feedback!

Could not send message