×

Parameterised Holant Problems. arXiv:2409.13579

Preprint, arXiv:2409.13579 [cs.CC] (2024).
Summary: We investigate the complexity of parameterised holant problems \(\textsc{p-Holant}(\mathcal{S})\) for families of signatures \(\mathcal{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 \(\mathcal{S}\): Depending on \(\mathcal{S}\), \(\textsc{p-Holant}(\mathcal{S})\) is: (1) solvable in FPT-near-linear time (i.e. \(f(k)\cdot \tilde{\mathcal{O}}(|x|)\)); (2) solvable in ”FPT-matrix-multiplication time” (i.e. \(f(k)\cdot {\mathcal{O}}(n^{\omega})\)) 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)\cdot {\mathcal{O}}(n^{\omega})\). We also establish a complete classification for a natural uncoloured version of parameterised holant problem \(\textsc{p-UnColHolant}(\mathcal{S})\), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of \(\textsc{p-UnColHolant}(\mathcal{S})\) is different: Depending on \(\mathcal{S}\) all instances are either solvable in FPT-near-linear time, or #W[1]-complete.
arXiv data are taken from the arXiv OAI-PMH API. If you found a mistake, please report it directly to arXiv.