Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908998509264896 |
|---|---|
| author | Aivasiliotis, Panagiotis Göbel, Andreas Roth, Marc |
| author_facet | Aivasiliotis, Panagiotis Göbel, Andreas Roth, Marc |
| contents | We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer $k$, how many ways are there to assign $k$ variables to 1 (and the others to 0) such that all constraints are satisfied. Existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of finite constraint languages due to Creignou and Vollmer (SAT 2012), and Bulatov and Marx (SICOMP 2014).
In this work, we tackle a more general setting of Valued Parameterised Counting Constraint Satisfaction Problems (VCSPs) with infinite constraint languages. In this setting we are able to model significantly more general problems such as (weighted) parameterised factor problems on hypergraphs and counting weight-$k$ solutions of systems of linear equations, not captured by existing complexity classifications.
We express parameterised VCSPs as parameterised Holant problems on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems. For resolving the $\mathrm{P}$ vs. $\#\mathrm{P}$ question, we mainly rely on hypergraph gadgets, the existence of which we prove using properties of degree sequences necessary for realisability in uniform hypergraphs. For the $\mathrm{FPT}$ vs. $\#\mathrm{W}[1]$ question, we build upon the recently established combinatorial toolkit for parameterised holants on the special case of graphs by Aivasiliotis et al. (ICALP 2025) and also rely on an extension of the framework of the homomorphism basis due to Curticapean, Dell and Marx (STOC 17) to uniform hypergraphs. As a technical highlight, we also employ Curticapean's "CFI Filters'' (SODA 2024) to establish polynomial-time algorithms for isolating vectors in the homomorphism basis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_19794 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs Aivasiliotis, Panagiotis Göbel, Andreas Roth, Marc Computational Complexity We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer $k$, how many ways are there to assign $k$ variables to 1 (and the others to 0) such that all constraints are satisfied. Existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of finite constraint languages due to Creignou and Vollmer (SAT 2012), and Bulatov and Marx (SICOMP 2014). In this work, we tackle a more general setting of Valued Parameterised Counting Constraint Satisfaction Problems (VCSPs) with infinite constraint languages. In this setting we are able to model significantly more general problems such as (weighted) parameterised factor problems on hypergraphs and counting weight-$k$ solutions of systems of linear equations, not captured by existing complexity classifications. We express parameterised VCSPs as parameterised Holant problems on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems. For resolving the $\mathrm{P}$ vs. $\#\mathrm{P}$ question, we mainly rely on hypergraph gadgets, the existence of which we prove using properties of degree sequences necessary for realisability in uniform hypergraphs. For the $\mathrm{FPT}$ vs. $\#\mathrm{W}[1]$ question, we build upon the recently established combinatorial toolkit for parameterised holants on the special case of graphs by Aivasiliotis et al. (ICALP 2025) and also rely on an extension of the framework of the homomorphism basis due to Curticapean, Dell and Marx (STOC 17) to uniform hypergraphs. As a technical highlight, we also employ Curticapean's "CFI Filters'' (SODA 2024) to establish polynomial-time algorithms for isolating vectors in the homomorphism basis. |
| title | Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2508.19794 |