2026 [ nach oben ]

Aivasiliotis, Panagiotis; Göbel, Andreas; Roth, Marc Symmetric Parameterised Holants on Hypergraphs: Towards a  Classification for Parameterised VCSPsInternational Colloquium on Automata, Languages and Programming (ICALP) 2026
[ BibTeX ]
 
@article{aivasiliotis2026symmetric, author = {Aivasiliotis, Panagiotis and Göbel, Andreas and Roth, Marc}, journal = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sys:relevantfor:ae friedrich myown panagiotisaivasiliotis}, title = {Symmetric Parameterised Holants on Hypergraphs: Towards a  Classification for Parameterised VCSPs}, year = 2026 }

2025 [ nach oben ]

Aivasiliotis, Panagiotis; Göbel, Andreas; Roth, Marc; Schmitt, Johannes Parameterised Holant Problems52nd International Colloquium on Automata, Languages, and Programming (ICALP) 2025: 7:1–7:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. 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 S: Depending on the signatures, p-Holant(S) 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)·O(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)·O(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(S), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(S) is different: Depending on S all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).
@inproceedings{aivasiliotis2025parameterised, abstract = {We investigate the complexity of parameterised holant problems p-Holant(S) for families of symmetric signatures S. 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 S: Depending on the signatures, p-Holant(S) 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)·O(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)·O(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(S), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(S) is different: Depending on S all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).}, author = {Aivasiliotis, Panagiotis and Göbel, Andreas and Roth, Marc and Schmitt, Johannes}, booktitle = {52nd International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {sys:relevantfor:ae friedrich myown panagiotisaivasiliotis}, pages = {7:1–7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Parameterised Holant Problems}, volume = 334, year = 2025 }