Complexity of the game connected domination problem
The connected domination game is a variant of the domination game where the played vertices must form a connected subgraph at all stages of the game. In this paper we prove that deciding whether the game connected domination number is smaller than a given integer is PSPACE-complete using log-space reductions for both Dominator- and Staller-start connected domination game.
Authors
- Vesna Iršič Chenoweth
Publication Details
- Journal
- Theoretical Computer Science
- Published
- 2025-09-25
- DOI
- https://doi.org/10.1016/j.tcs.2025.115559
- Primary Topic
- Game Theory and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00