Document Open Access Logo

6-Uniform Maker-Breaker Game Is PSPACE-Complete

Authors Md Lutfar Rahman, Thomas Watson

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.57.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Md Lutfar Rahman
  • University of Memphis, TN, USA
Thomas Watson
  • University of Memphis, TN, USA

Funding

This work was supported by NSF grants CCF-1657377 and CCF-1942742.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.57

Abstract

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains PSPACE-complete even when every set has size 6.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Game
  • Maker-Breaker
  • Complexity
  • Reduction
  • PSPACE-complete
  • NL-hard

Metrics

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

Related Versions

References

  1. Argimiro Arratia and Iain Stewart. A note on first-order projections and games. Theoretical Computer Science, 290(3):2085-2093, 2003. Google Scholar
  2. Bengt Aspvall, Michael Plass, and Robert Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979. Google Scholar
  3. Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, and Gabriel Renault. Complexity of the game domination problem. Theoretical Computer Science, 648:1-7, 2016. Google Scholar
  4. Jesper Byskov. Maker-Maker and Maker-Breaker games are PSPACE-complete. Technical Report RS-04-14, BRICS, Department of Computer Science, Aarhus University, 2004. Google Scholar
  5. Vasek Chvátal and Paul Erdös. Biased positional games. Annals of Discrete Mathematics, 2:221-229, 1978. Google Scholar
  6. Eurinardo Costa, Victor Lage Pessoa, Rudini Menezes Sampaio, and Ronan Soares. PSPACE-hardness of two graph coloring games. In Proceedings of the 10th Latin and American Algorithms, Graphs, and Optimization Symposium (LAGOS), pages 333-344. Elsevier, 2019. Google Scholar
  7. Erik Demaine and Robert Hearn. Constraint logic: A uniform framework for modeling computation as games. In Proceedings of the 23rd Conference on Computational Complexity (CCC), pages 149-162. IEEE, 2008. Google Scholar
  8. Eric Duchene, Valentin Gledel, Aline Parreau, and Gabriel Renault. Maker-breaker domination game. Discrete Mathematics, 343(9):111955, 2020. Google Scholar
  9. Paul Erdös and John Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3), 1973. Google Scholar
  10. Stephen Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, and Thomas Thierauf. Game values and computational complexity: An analysis via black-white combinatorial games. In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), pages 689-699. Springer, 2015. Google Scholar
  11. Aviezri Fraenkel and Elisheva Goldschmidt. PSPACE-hardness of some combinatorial games. Journal of Combinatorial Theory, Series A, 46(1):21-38, 1987. Google Scholar
  12. Valentin Gledel, Michael A Henning, Vesna Iršič, and Sandi Klavžar. Maker-breaker total domination game. Discrete Applied Mathematics, 282:96-107, 2020. Google Scholar
  13. Robert Hearn. Amazons, Konane, and Cross Purposes are PSPACE-complete. In Games of No Chance 3, Mathematical Sciences Research Institute Publications, pages 287-306. Cambridge University Press, 2009. Google Scholar
  14. Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional Games. Birkhäuser Basel (Springer), 2014. Google Scholar
  15. Martin Kutz. Weak positional games on hypergraphs of rank three. In Proceedings of the 3rd European Conference on Combinatorics, Graph Theory, and Applications (EuroComb), pages 31-36. Discrete Mathematics & Theoretical Computer Science, 2005. Google Scholar
  16. Alfred Lehman. A solution of the Shannon switching game. Journal of the Society for Industrial and Applied Mathematics, 12(4):687-725, 1964. Google Scholar
  17. Md Lutfar Rahman and Thomas Watson. Complexity of unordered CNF games. ACM Transactions on Computation Theory, 12(3):18:1-18:18, 2020. Google Scholar
  18. Md Lutfar Rahman and Thomas Watson. Tractable unordered 3-CNF games. In Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN). Springer, 2020. To appear. Google Scholar
  19. Thomas Schaefer. Complexity of decision problems based on finite two-person perfect-information games. In Proceedings of the 8th Symposium on Theory of Computing (STOC), pages 41-49. ACM, 1976. Google Scholar
  20. Thomas Schaefer. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185-225, 1978. Google Scholar
  21. Wolfgang Slany. The complexity of graph Ramsey games. In Proceedings of the 2nd International Conference on Computers and Games (CG), pages 186-203. Springer, 2000. Google Scholar
  22. Wolfgang Slany. Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. Theoretical Computer Science, 289(1):829-843, 2002. Google Scholar
  23. Larry Stockmeyer and Albert Meyer. Word problems requiring exponential time. In Proceedings of the 5th Symposium on Theory of Computing (STOC), pages 1-9. ACM, 1973. Google Scholar
  24. Sachio Teramoto, Erik Demaine, and Ryuhei Uehara. The Voronoi game on graphs and its complexity. Journal of Graph Algorithms and Applications, 15(4):485-501, 2011. Google Scholar
  25. Jan van Rijn and Jonathan Vis. Complexity and retrograde analysis of the game Dou Shou Qi. In Proceedings of the 25th Benelux Conference on Artificial Intelligence (BNAIC), 2013. 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