Document Open Access Logo

Avoidance Games Are PSPACE-Complete

Authors Valentin Gledel , Nacim Oijid

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.34.pdf
  • Filesize: 0.79 MB
  • 19 pages

Document Identifiers

Author Details

Valentin Gledel
  • Department of Mathematics and Mathematical Statistics, Umeå University, Sweden
Nacim Oijid
  • Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France

Funding

  • Gledel, Valentin: supported by the Kempe Foundation Grant No. JCK-2022.1 (Sweden).
  • Oijid, Nacim: supported by the ANR project P-GASE (ANR-21-CE48-0001-01)

Acknowledgements

We want to thank Eric Duchêne, Marianne Fortin, Aline Parreau and the anonymous referees for their help in the writing of this article.

Cite AsGet BibTex

Valentin Gledel and Nacim Oijid. Avoidance Games Are PSPACE-Complete. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.34

Abstract

Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games have been studied since the introduction of the game of SIM in 1968, but only few complexity results have been found out about them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games correspond to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question has remained open since then. Here, we prove here that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete. Using the PSPACE-hardness of Avoider-Enforcer, we provide in appendix proofs that some particular Avoider-Enforcer games also are.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Games
  • Avoider-Enforcer
  • Maker-Breaker
  • Complexity
  • Avoider-Avoider
  • PSPACE-complete

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, József Balogh, Béla Bollobás, and Tamás Szabó. Game domination number. Discrete mathematics, 256(1-2):23-33, 2002. Google Scholar
  2. V Anuradha, Chinmay Jain, Jack Snoeyink, and Tibor Szabó. How long can a graph be kept planar? the electronic journal of combinatorics, 15(1), 2008. Google Scholar
  3. János Barát and Miloš Stojaković. On winning fast in Avoider-Enforcer games. the electronic journal of combinatorics, 17, 2008. Google Scholar
  4. József Beck. Ramsey games. Discrete mathematics, 249(1-3):3-30, 2002. Google Scholar
  5. József Beck. Combinatorial games: tic-tac-toe theory, volume 114. Cambridge University Press Cambridge, 2008. Google Scholar
  6. Edouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine. The Parameterized Complexity of Positional Games. In ICALP, Varsovie, Poland, July 2017. Google Scholar
  7. Boštjan Brešar, Sandi Klavžar, and Douglas F Rall. Domination game and an imagination strategy. SIAM Journal on Discrete Mathematics, 24(3):979-991, 2010. Google Scholar
  8. Jesper Makholm Byskov. Maker-Maker and Maker-Breaker games are PSPACE-complete. BRICS Report Series, 11(14), 2004. Google Scholar
  9. Erik D Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In International Symposium on Mathematical Foundations of Computer Science, pages 18-33. Springer, 2001. Google Scholar
  10. Eric Duchene, Valentin Gledel, Aline Parreau, and Gabriel Renault. Maker-Breaker domination game. Discrete Mathematics, 343(9):111955, 2020. Google Scholar
  11. P Erdös and J.L Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3):298-301, 1973. Google Scholar
  12. Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. Maker-Breaker is solved in polynomial time on hypergraphs of rank 3, 2022. Google Scholar
  13. Andrzej Grzesik, Mirjana Mikalački, Zoltán Lóránt Nagy, Alon Naor, Balázs Patkós, and Fiona Skerman. Avoider-Enforcer star games. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, pages 375-379. Springer, 2013. Google Scholar
  14. R.I. Hales and A.W. Jewett. Regularity and positional games. Trans. Am. Math. Soc, 106:222-229, 1963. Google Scholar
  15. Dan Hefetz. Positional games on graphs. PhD thesis, Citeseer, 2007. Google Scholar
  16. Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Fast winning strategies in positional games. Electronic Notes in Discrete Mathematics, 29:213-217, 2007. Google Scholar
  17. Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Avoider-Enforcer: The rules of the game. Journal of Combinatorial Theory, Series A, 117(2):152-163, 2010. Google Scholar
  18. Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional games, volume 44. Springer, 2014. Google Scholar
  19. Dan Hefetz, Michael Krivelevich, and Tibor Szabó. Avoider-Enforcer games. Journal of Combinatorial Theory, Series A, 114(5):840-853, 2007. Google Scholar
  20. Dan Hefetz, Michael Krivelevich, and Tibor Szabó. Bart-Moe games, JumbleG and discrepancy. European Journal of Combinatorics, 28(4):1131-1143, 2007. Google Scholar
  21. Gal Kronenberg, Adva Mond, and Alon Naor. h-games played on vertex sets of random graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1901.00351.
  22. Xiaoyun Lu. A matching game. Discret. Math., 94(3):199-207, 1991. URL: https://doi.org/10.1016/0012-365X(91)90025-W.
  23. Xiaoyun Lu. A note on biased and non-biased games. Discrete Applied Mathematics, 60(1):285-291, 1995. Google Scholar
  24. Tillmann Miltzow and Miloš Stojaković. Avoider-Enforcer Game is NP-hard. arXiv preprint, 2022. URL: http://arxiv.org/abs/2208.06687.
  25. Rajko Nenadov, Angelika Steger, and Miloš Stojaković. On the threshold for the Maker-Breaker H-game. Random Structures & Algorithms, 49(3):558-578, 2016. Google Scholar
  26. Md Lutfar Rahman and Thomas Watson. 6-Uniform Maker-Breaker Game Is PSPACE-Complete. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1-57:15, 2021. Google Scholar
  27. Thomas J. Schaefer. On the Complexity of Some Two-Person Perfect-Information Games. Journal of computer and system Sciences, 16:185-225, 1978. Google Scholar
  28. Gustavus J Simmons. The Game of SIM. In Mathematical Solitaires & Games, pages 50-50. Routledge, 1968. Google Scholar
  29. Wolfgang Slany. Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. Theoretical computer science, 289(1):829-843, 2002. Google Scholar
  30. Larry J Stockmeyer and Albert R Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 1-9, 1973. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact