Parameterised Holant Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916716276088832 |
|---|---|
| author | Aivasiliotis, Panagiotis Göbel, Andreas Roth, Marc Schmitt, Johannes |
| author_facet | Aivasiliotis, Panagiotis Göbel, Andreas Roth, Marc Schmitt, Johannes |
| contents | We investigate the complexity of parameterised holant problems p-$\mathrm{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}$, p-$\mathrm{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^ω)$) 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^ω)$.
We also establish a complete classification for a natural uncoloured version of parameterised holant problem p-$\mathrm{UnColHolant}(\mathcal{S})$, which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-$\mathrm{UnColHolant}(\mathcal{S})$ is different: Depending on $\mathcal{S}$ all instances are either solvable in FPT-near-linear time, or #W[1]-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13579 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterised Holant Problems Aivasiliotis, Panagiotis Göbel, Andreas Roth, Marc Schmitt, Johannes Computational Complexity Combinatorics We investigate the complexity of parameterised holant problems p-$\mathrm{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}$, p-$\mathrm{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^ω)$) 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^ω)$. We also establish a complete classification for a natural uncoloured version of parameterised holant problem p-$\mathrm{UnColHolant}(\mathcal{S})$, which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-$\mathrm{UnColHolant}(\mathcal{S})$ is different: Depending on $\mathcal{S}$ all instances are either solvable in FPT-near-linear time, or #W[1]-complete. |
| title | Parameterised Holant Problems |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2409.13579 |