The Counting General Dominating Set Framework
This work addresses computational complexity challenges in graph theory, particularly for combinatorial counting problems, but is incremental as it builds on existing Holant frameworks.
The authors tackled the problem of counting dominating sets and total dominating sets in specific graph classes by introducing the #GDS framework and proving #P-completeness for 3-regular planar bipartite simple graphs.
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 propose the technique of gadget construction under 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.