[Back]

S. Kreutzer, S. Ordyniak:
"Complexity and monotonicity results for domination games";
Theoretical Computer Science, 628 (2016), 1 - 29.

In this paper we study Domination Games, a class of games introduced by Fomin, Kratsch, and Müller in[8]. Domination games are a variant of the well-known graph searching games (also called cops and robber games), where a number of cops tries to capture a robber hiding on the vertices of a graph. Variants of these games are often used to provide a game-theoretic characterization of important graph parameters such as pathwidth, treewidth, and hypertreewidth.
We are primarily interested in questions concerning the complexity and monotonicity of these games. We show that dominating games are computationally much harder than standard cops and robber games and establish strong non-monotonicity results for various notions of monotonicity that arise naturally in the context of domination games. Answering a question of [8], we show that there are graphs where the shortest winning strategy for a minimal number of cops must necessarily be of exponential length.

http://dx.doi.org/10.1016/j.tcs.2016.03.003