The Counting General Dominating Set Framework
Pith reviewed 2026-05-21 11:47 UTC · model grok-4.3
The pith
Counting dominating sets is #P-complete for 3-regular planar bipartite graphs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We introduce a new framework of counting problems called #GDS that encompasses (#σ, ρ)-Set, a class of domination-type problems that includes counting dominating sets and counting total dominating sets. We explore the intricate relation between #GDS and the well-known Holant. We adapt the technique of gadget construction of Holant to the #GDS framework; using this technique, we prove the #P-completeness of counting dominating sets for 3-regular planar bipartite simple graphs. Through a generalization of a Holant dichotomy, and a special reduction method via symmetric bipartite graphs, we also prove the #P-completeness of counting total dominating sets for the same graph class.
What carries the argument
The #GDS framework, which generalizes (#σ, ρ)-Set problems and supports direct adaptation of Holant gadget constructions to transfer #P-completeness.
If this is right
- Counting dominating sets is #P-complete on the restricted class of 3-regular planar bipartite simple graphs.
- Counting total dominating sets is likewise #P-complete on the same graph class.
- Gadget constructions can be transferred from Holant to #GDS while maintaining exact counting equivalence.
- The special reduction via symmetric bipartite graphs extends the dichotomy technique to total domination counting.
Where Pith is reading between the lines
- The #GDS framework could be applied to establish #P-completeness for additional variants of set-counting problems on planar graphs.
- The symmetric bipartite reduction technique may connect to hardness proofs for other enumeration problems that admit similar symmetry.
- These exact-counting hardness results suggest that approximation or parameterized algorithms for domination counting would need to exploit features beyond planarity and bipartiteness.
Load-bearing premise
The gadget constructions and reductions adapted from the Holant framework to the new #GDS framework preserve exact counting equivalence without introducing polynomial-time computable factors or structural changes that would invalidate the #P-completeness transfer.
What would settle it
A polynomial-time algorithm that exactly counts the number of dominating sets in every 3-regular planar bipartite simple graph would show the #P-completeness claim is false.
read the original abstract
We introduce a new framework of counting problems called #GDS that encompasses #$(\sigma, \rho)$-Set, a class of domination-type problems that includes counting dominating sets and counting total dominating sets. We explore the intricate relation between #GDS and the well-known Holant. We adapt the technique of gadget construction of Holant to the #GDS framework; using this technique, we prove the #P-completeness of counting dominating sets for 3-regular planar bipartite simple graphs. Through a generalization of a Holant dichotomy, and a special reduction method via symmetric bipartite graphs, we also prove the #P-completeness of counting total dominating sets for the same graph class.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the #GDS framework, which generalizes #($σ, ρ$)-Set problems including counting dominating sets and total dominating sets. It relates #GDS to Holant problems, adapts Holant gadget constructions to prove #P-completeness of counting dominating sets on 3-regular planar bipartite simple graphs, and uses a generalization of a Holant dichotomy together with reductions via symmetric bipartite graphs to prove the same for total dominating sets on the same class.
Significance. If the gadget adaptations preserve exact solution counts and all stated graph restrictions, the results would extend known #P-completeness boundaries for domination counting problems to a highly restricted graph class (3-regular planar bipartite simple graphs), providing concrete applications of Holant techniques beyond their original setting.
major comments (2)
- [Gadget construction and reduction sections (following the abstract description of adaptation from Holant)] The central #P-completeness claims rest on gadget constructions adapted from Holant to #GDS. The manuscript must explicitly verify (with bijections or polynomial-time computable non-vanishing factors) that each gadget preserves exact counting equivalence while simultaneously maintaining planarity, bipartiteness, 3-regularity, and simplicity; any hidden multiplicative factor depending on input size would invalidate the hardness transfer. This verification is load-bearing for both the dominating-set and total-dominating-set results.
- [Section on generalization of Holant dichotomy and symmetric bipartite graph reductions] The generalization of the Holant dichotomy to the #GDS framework, used for the total-dominating-set result via symmetric bipartite graphs, requires a precise statement of the new dichotomy and a proof that the special reduction method does not introduce structural changes that destroy the target graph class properties.
minor comments (2)
- [Introduction and framework definition] Clarify the precise definition of the #GDS framework and how it strictly encompasses #($σ, ρ$)-Set without additional assumptions.
- [Preliminaries] Ensure all notation for symmetric bipartite graphs and gadget signatures is introduced before first use and is consistent with prior Holant literature.
Simulated Author's Rebuttal
We thank the referee for the thorough review and valuable comments on our manuscript. We address each major comment in detail below, providing clarifications on the gadget constructions and the generalized dichotomy. Where appropriate, we commit to revisions that strengthen the presentation without altering the core results.
read point-by-point responses
-
Referee: The central #P-completeness claims rest on gadget constructions adapted from Holant to #GDS. The manuscript must explicitly verify (with bijections or polynomial-time computable non-vanishing factors) that each gadget preserves exact counting equivalence while simultaneously maintaining planarity, bipartiteness, 3-regularity, and simplicity; any hidden multiplicative factor depending on input size would invalidate the hardness transfer. This verification is load-bearing for both the dominating-set and total-dominating-set results.
Authors: We agree that explicit verification of counting equivalence and graph-class preservation is necessary for the reductions to be rigorous. The manuscript adapts Holant gadgets to the #GDS framework by describing local replacements that maintain 3-regularity, planarity, bipartiteness, and simplicity through careful choice of symmetric bipartite components. However, the current text relies on implicit bijections derived from the Holant originals. In the revised version, we will insert a new subsection (likely after the gadget definitions) that explicitly constructs the solution bijections for each gadget, shows that the multiplicative factor is a fixed constant (independent of input size) arising only from the gadget's internal structure, and verifies that no edges or vertices violate the target restrictions. This addresses the concern directly for both the dominating-set and total-dominating-set proofs. revision: yes
-
Referee: The generalization of the Holant dichotomy to the #GDS framework, used for the total-dominating-set result via symmetric bipartite graphs, requires a precise statement of the new dichotomy and a proof that the special reduction method does not introduce structural changes that destroy the target graph class properties.
Authors: The manuscript states the generalized dichotomy in the section following the #GDS-Holant relation, extending the Holant classification by mapping #GDS instances to symmetric Holant problems on bipartite graphs while preserving the signature properties. The special reduction via symmetric bipartite graphs is constructed so that each replacement graph is itself 3-regular, planar, bipartite, and simple, ensuring the overall instance remains in the target class. We acknowledge that the proof of structural invariance could be more explicit. In revision, we will add a lemma that formally proves the reduction preserves all four properties (planarity via planar embeddings of the symmetric graphs, bipartiteness by construction, 3-regularity by degree-matching, and simplicity by avoiding multiple edges), together with a restated theorem that isolates the new dichotomy conditions applicable to #GDS. revision: partial
Circularity Check
No circularity: derivation adapts external Holant framework to new #GDS setting
full rationale
The paper introduces the #GDS framework as a generalization encompassing #($σ,ρ$)-Set problems and then adapts gadget constructions and dichotomies from the established, independent Holant literature to prove #P-completeness of counting dominating sets and total dominating sets on 3-regular planar bipartite simple graphs. These steps rely on external prior results rather than any self-definitional equation, fitted parameter renamed as prediction, or load-bearing self-citation chain. No quoted claim reduces a claimed result to an input by construction; the reductions are presented as transferring hardness while preserving the required graph restrictions. The derivation chain therefore remains self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Gadget constructions from Holant can be directly adapted to #GDS while preserving exact counting equivalence.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.