Restricted Power - Computational Complexity Results for Strategic Defense Games

Open Access
Authors
Publication date 06-2018
Host editors
  • H. Ito
  • S. Leonardi
  • L. Pagli
  • G. Prencipe
Book title 9th International Conference on Fun with Algorithms
Book subtitle FUN 2018, June 13-15, 2016, La Maddalena Island, Italy
ISBN (electronic)
  • 9783959770675
Series Leibniz International Proceedings in Informatics
Event 9th International Conference on Fun with Algorithms
Article number 17
Number of pages 14
Publisher Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract We study the game Greedy Spiders, a two-player strategic defense game, on planar graphs and show PSPACE-completeness for the problem of deciding whether one player has a winning strategy for a given instance of the game. We also generalize our results in metatheorems, which consider a large set of strategic defense games. We achieve more detailed complexity results by restricting the possible strategies of one of the players, which leads us to Σp2- and Πp2-hardness results.
Document type Conference contribution
Language English
Published at https://doi.org/10.4230/LIPIcs.FUN.2018.17
Downloads
LIPIcs-FUN-2018-17 (Final published version)
Permalink to this page
Back