×

Complexity and monotonicity results for domination games. (English) Zbl 1338.68112

Summary: In this paper we study Domination Games, a class of games introduced by F. V. Fomin et al. [Discrete Appl. Math. 127, No. 3, 565–580 (2003; Zbl 1019.68076)]. 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 [loc. cit.], we show that there are graphs where the shortest winning strategy for a minimal number of cops must necessarily be of exponential length.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C57 Games on graphs (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
91A43 Games involving graphs

Citations:

Zbl 1019.68076
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bodlaender, H., A partial k-arboretum of graphs with bounded tree-width, Theoret. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148
[2] Bodlaender, H.; Kloks, T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, 21, 2, 358-402 (1996) · Zbl 0861.68036
[3] Bodlaender, H. L., Treewidth: algorithmic techniques and results, (Proc. of Mathematical Foundations of Computer Science. Proc. of Mathematical Foundations of Computer Science, MFCS. Proc. of Mathematical Foundations of Computer Science. Proc. of Mathematical Foundations of Computer Science, MFCS, LNCS, vol. 1295 (1997)), 19-36 · Zbl 0941.05057
[4] Diestel, R., Graph Theory (2005), Springer-Verlag · Zbl 1074.05001
[5] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity (2014), Springer · Zbl 1358.68006
[6] Fedor, F.; Thilikos, D. M., An annotated bibliography on guaranteed graph searching, Theoret. Comput. Sci., 399, 3, 236-245 (2008) · Zbl 1160.68007
[7] Flum, Jörg; Grohe, Martin, Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, vol. XIV (2006), Springer Verlag: Springer Verlag Berlin · Zbl 1143.68016
[8] Fomin, F.; Kratsch, D.; Müller, H., On the domination search number, Discrete Appl. Math., 127, 3, 565-580 (2003) · Zbl 1019.68076
[9] Franklin, M. K.; Galil, Z.; Yung, M., Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, J. ACM, 47, 2, 225-243 (2000) · Zbl 1133.68469
[10] Kirousis, L. M.; Papadimitriou, C. H., Searching and pebbling, Theoret. Comput. Sci., 47, 3, 205-218 (1986) · Zbl 0616.68064
[11] Kloks, T.; Kratsch, D.; Müller, H., On the structure of graphs with bounded asteroidal number, Graphs Combin., 17, 2, 295-306 (2001) · Zbl 0989.05059
[12] Kreutzer, Stephan; Ordyniak, Sebastian, Distance d-domination games, (Christophe, Paul; Habib, Michel, Graph-Theoretic Concepts in Computer Science, 35th International Workshop, Revised Papers. Graph-Theoretic Concepts in Computer Science, 35th International Workshop, Revised Papers, WG 2009, Montpellier, France, June 24-26, 2009. Graph-Theoretic Concepts in Computer Science, 35th International Workshop, Revised Papers. Graph-Theoretic Concepts in Computer Science, 35th International Workshop, Revised Papers, WG 2009, Montpellier, France, June 24-26, 2009, Lecture Notes in Computer Science, vol. 5911 (2009)), 308-319 · Zbl 1200.68172
[13] Niedermeier, Rolf, Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and Its Applications (2006), Oxford University Press: Oxford University Press Oxford · Zbl 1095.68038
[14] Seymour, P. D.; Thomas, R., Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B, 58, 1, 22-33 (1993) · Zbl 0795.05110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.