Complexity of the game domination problem
Copyright policy )Complexity of the game domination problem
The game domination number is a graph invariant that arises from a game, which is related to graph domination in a similar way as the game chromatic number is related to graph coloring. In this paper we show that verifying whether the game domination number of a graph is bounded by a given integer is PSPACE-complete. This contrasts the situation of the game coloring problem whose complexity is still unknown.
14 pages, 3 figures
FOS: Computer and information sciences, computational complexity, Analysis of algorithms and problem complexity, Games on graphs (graph-theoretic aspects), Computational Complexity (cs.CC), Computer Science - Computational Complexity, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), domination game, POS-CNF problem, 05C57, 68Q15, 05C69, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, PSPACE-complete problems, Combinatorics (math.CO)
FOS: Computer and information sciences, computational complexity, Analysis of algorithms and problem complexity, Games on graphs (graph-theoretic aspects), Computational Complexity (cs.CC), Computer Science - Computational Complexity, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), domination game, POS-CNF problem, 05C57, 68Q15, 05C69, FOS: Mathematics, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Mathematics - Combinatorics, PSPACE-complete problems, Combinatorics (math.CO)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).13 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!