Complexity and monotonicity results for domination games

详细信息    查看全文

• 作者：Stephan Kreutzer^a ; ^{stephan.kreutzer@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Sebastian Ordyniak^b ; ^{sordyniak@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph searching games ; Cops and robber games ; Domination search games ; Parameterized complexity ; Monotonicity
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：16 May 2016
• 年：2016
• 卷：628
• 期：Complete
• 页码：1-29
• 全文大小：1007 K

文摘

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.