We consider domination games on graphs, their variants and the game
domination number, which is the number of moves made in a graph domi-
nation game assuming both players play optimally. We deal with the space
complexity the game domination number. We show that the game domina-
tion number can be calculated with an algorithm that runs in linear space
complexity, which means that the problem is in PSPACE. Finally, we prove
that the domination game on graphs problem is PSPACE-complete under
polynomial time reductions. We do that using the PSPACE-completeness
of the game problem on propositional formulas in conjunctive normal form
without negations (POS-CNF).
|
