2024/09/20 by Aivasiliotis, Panagiotis, Göbel, Andreas, Roth, Marc +1 · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.13579
We investigate the complexity of parameterised holant problems p-Holant(S) for families of signatures S. The parameterised holant framework was introduced by Curticapean in 2015 as a counter-part to the classical 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, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures S: Depending on S, p-Holant(S) is: (1) solvable in FPT-near-linear time (i.e. f(k)⋅ O(|x|)); (2) solvable in "FPT-matrix-multiplication time" (i.e. f(k)⋅ O(nω)) but not solvable in FPT-near-linear time unless the Triangle Conjecture fails; or (3) #W[1]-complete and no significant improvement over brute force is possible unless ETH 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 f(k)⋅ O(nω). 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.