The Counting General Dominating Set Framework
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916023817469952 |
|---|---|
| author | Zheng, Jiayi Meng, Boning |
| author_facet | Zheng, Jiayi Meng, Boning |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14749 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Counting General Dominating Set Framework Zheng, Jiayi Meng, Boning Computational Complexity 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. |
| title | The Counting General Dominating Set Framework |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2603.14749 |