Parameterised Holant Problems

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