Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
Pith reviewed 2026-05-18 21:09 UTC · model grok-4.3
The pith
Parameterised VCSPs on hypergraphs have explicit complexity dichotomies when cast as symmetric Holant problems.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We establish complete and explicit complexity dichotomy theorems for parameterised VCSPs expressed as parameterised Holant problems on uniform hypergraphs. For resolving the P vs #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 FPT vs #W[1] question, we build upon the recently established combinatorial toolkit for parameterised holants on graphs and extend the homomorphism basis to uniform hypergraphs, employing CFI filters to establish polynomial-time algorithms for isolating vectors in the homomorphism basis.
What carries the argument
Symmetric parameterised Holant problems on uniform hypergraphs, which model the VCSPs and allow gadget reductions for complexity classification.
If this is right
- All weighted parameterised factor problems on hypergraphs fall under the dichotomy.
- Counting weight-k solutions to linear equation systems over hypergraphs is classified as P or #P.
- Infinite constraint languages in parameterised VCSPs receive explicit complexity classifications.
- The framework allows polynomial time isolation of vectors using CFI filters in hypergraph settings.
Where Pith is reading between the lines
- The results may extend to classify problems in quantum computing or statistical physics models on hypergraphs.
- Testing the dichotomy on specific uniform hypergraphs like 3-uniform ones could validate the gadget constructions.
- Connections to degree sequence problems in graph theory could lead to new gadget designs.
- This could inform algorithmic approaches for hypergraph counting in data analysis.
Load-bearing premise
The construction of hypergraph gadgets depends on the existence of uniform hypergraphs with prescribed degree sequences that are realisable.
What would settle it
Observe a parameterised Holant instance on a uniform hypergraph where the counting problem is in P but the dichotomy predicts #W[1]-hardness, or vice versa.
read the original abstract
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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the complexity of parameterised counting constraint satisfaction problems with infinite constraint languages by expressing them as parameterised Holant problems on uniform hypergraphs. It establishes complete complexity dichotomy theorems for both the P versus #P and FPT versus #W[1] questions, relying on hypergraph gadgets based on degree-sequence realisability for the former and extensions of homomorphism bases with CFI filters for the latter.
Significance. This result is significant as it generalizes previous work on homomorphisms and finite languages to valued VCSPs modeling weighted factor problems and linear equation systems. The technical approach using CFI filters for polynomial-time algorithms in the homomorphism basis represents a notable contribution that could influence future work in parameterised counting complexity. The extension to uniform hypergraphs and explicit dichotomies fill an important gap if the gadget constructions hold without gaps.
major comments (1)
- [Gadget constructions for P vs #P] In the gadget constructions for the P vs #P dichotomy: The existence of hypergraph gadgets is asserted using necessary properties of degree sequences for realisability in uniform hypergraphs. For infinite-valued constraints, it is unclear whether these conditions are also sufficient to realise every required gadget while preserving parameterised counting complexity. An explicit sufficiency argument or verification that no cases are left unhandled would be needed to support the completeness claim.
minor comments (2)
- The abstract mentions reliance on Aivasiliotis et al. (ICALP 2025) and Curticapean (SODA 2024); ensure all references are correctly formatted and complete in the bibliography.
- [Introduction] Clarify the distinction between uniform hypergraphs and standard graphs in the introduction and notation sections for readers unfamiliar with the extension.
Simulated Author's Rebuttal
We thank the referee for their thoughtful review and for recognising the significance of our results on parameterised Holant problems and their implications for VCSPs. We address the single major comment below and outline the changes we will make to improve clarity.
read point-by-point responses
-
Referee: [Gadget constructions for P vs #P] In the gadget constructions for the P vs #P dichotomy: The existence of hypergraph gadgets is asserted using necessary properties of degree sequences for realisability in uniform hypergraphs. For infinite-valued constraints, it is unclear whether these conditions are also sufficient to realise every required gadget while preserving parameterised counting complexity. An explicit sufficiency argument or verification that no cases are left unhandled would be needed to support the completeness claim.
Authors: We agree that the presentation would benefit from an explicit statement on sufficiency. The manuscript invokes the necessary conditions on degree sequences because, for uniform hypergraphs, these conditions form part of a known if-and-only-if characterisation of realisable sequences (drawing on standard results in hypergraph degree-sequence theory). Consequently, any sequence satisfying the necessary conditions we check is guaranteed to be realisable, and the gadgets can be constructed without changing the parameterised counting complexity. To make this fully transparent and to verify that no cases required by the dichotomy are omitted, we will add a short clarifying paragraph (or subsection) in the gadget-construction section that (i) recalls the relevant if-and-only-if theorem, (ii) confirms that the sequences arising from our infinite constraint languages meet the conditions, and (iii) notes that the same realisability therefore holds for all cases needed for the P vs #P dichotomy. This revision strengthens readability but does not alter the technical claims. revision: yes
Circularity Check
No significant circularity; independent gadget proofs and hypergraph extensions
full rationale
The paper proves existence of hypergraph gadgets directly from degree-sequence realisability properties for uniform hypergraphs and extends the homomorphism basis and CFI-filter techniques with new arguments for the infinite-constraint case. The citation to Aivasiliotis et al. (ICALP 2025) supplies only the graph-case toolkit; the present work adds the uniform-hypergraph reduction and the P vs #P half of the dichotomy via explicit combinatorial constructions rather than by re-using fitted parameters or self-referential definitions. No equation or claim reduces to its own input by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Properties of degree sequences necessary for realisability in uniform hypergraphs
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We express parameterised VCSPs as parameterised Holant problems on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems... For resolving the P vs. #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.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.