Complexity of the Game Domination Problem

2015/10/01 by Brešar, Boštjan, Dorbec, Paul, Klavžar, Sandi +2
#05C57 #05C69 #68Q15 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1510.00140

Abstract

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.

Related

• Complexity of the game connected domination problem
• Hardness of some variants of the graph coloring game
• Indicated domination game
• General upper bound on the game domination number
• The Normal Play of the Domination Game