×

Games on interval and permutation graph representations. (English) Zbl 1331.05151

Summary: We describe combinatorial games on graphs in which two players antagonistically build a representation of a subgraph of a given graph. We show that for a large class of these games, determining whether a given instance is a winning position for the next player is PSPACE-hard. In contrast, we give polynomial time algorithms for solving some versions of the games on trees.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91A43 Games involving graphs
91A46 Combinatorial games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aichholzer, Oswin; Bremner, David; Demaine, Erik D.; Hurtado, Ferran; Kranakis, Evangelos; Krasser, Hannes; Ramaswami, Suneeta; Sethia, Saurabh; Urrutia, Jorge, Games on triangulations, Theoret. Comput. Sci., 343, 42-71 (2005) · Zbl 1079.68100
[2] Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David, Lessons in Play: An Introduction to the Combinatorial Theory of Games (2007), A.K. Peters · Zbl 1184.91001
[3] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K., Winning Ways for Your Mathematical Plays (2001), Academic Press: A.K. Peters · Zbl 1005.00004
[4] Bodlaender, Hans L., Complexity of path-forming games, Theoret. Comput. Sci., 110, 215-245 (1993) · Zbl 0776.90100
[5] Bodlaender, Hans L.; Kratsch, Dieter, Kayles and nimbers, J. Algorithms, 43, 106-119 (2002) · Zbl 1005.68112
[6] Bodlaender, Hans L.; Kratsch, Dieter; Timmer, Sjoerd T., Exact algorithms for Kayles, Theoret. Comput. Sci., 562, 165-176 (2015) · Zbl 1305.05143
[7] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland · Zbl 1226.05083
[8] Brandstädt, Andreas; Van Le, Bang; Spinrad, Jeremy P., Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), SIAM · Zbl 0919.05001
[9] Conway, John H., On Numbers and Games (2001), Academic Press: A K Peters · Zbl 0972.11002
[10] Fleischer, Rudolf; Trippen, Gerhard, Kayles on the way to the stars, (van den Herik, H. Jaap; Björnsson, Yngvi; Netanyahu, Nathan S., Computers and Games. Computers and Games, Lecture Notes in Computer Science, vol. 3846 (2006)), 232-245
[11] Schaefer, Thomas J., On the complexity of some two-person perfect-information games, J. Comput. System Sci., 16, 185-225 (1978) · Zbl 0383.90112
[12] Spinrad, Jeremy P., Efficient Graph Representations, Fields Institute Monographs, vol. 19 (2003), American Mathematical Society · Zbl 1033.05001
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.