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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Complexity of the game connected domination problem

Vesna Iršič Chenoweth
Theoretical Computer Science
Game Theory and Applications
article

Complexity of the game connected domination problem

Vesna Iršič Chenoweth
article en

Abstract

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.

Theoretical Computer ScienceVol. 1057
Openalex Percentile: Top 69%
Game Theory and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Complexity of the game connected domination problem — Vesna Iršič Chenoweth · Theoretical Computer Science (2025) | TGRS Research Map | TGRS