Document Open Access Logo

Connectivity in the Presence of an Opponent

Authors Zihui Liang , Bakh Khoussainov, Toru Takisaka , Mingyu Xiao

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.79.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Zihui Liang
  • University of Electronic Science and Technology of China, Chengdu, China
Bakh Khoussainov
  • University of Electronic Science and Technology of China, Chengdu, China
Toru Takisaka
  • University of Electronic Science and Technology of China, Chengdu, China
Mingyu Xiao
  • University of Electronic Science and Technology of China, Chengdu, China

Funding

  • Khoussainov, Bakh: Bakh Khoussainov acknowledges the National Science Foundation of China under Grant No.62172077.

Cite AsGet BibTex

Zihui Liang, Bakh Khoussainov, Toru Takisaka, and Mingyu Xiao. Connectivity in the Presence of an Opponent. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.79

Abstract

The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving Müller games. Müller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. The first contribution of this paper is our proof that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. The second contribution is that we non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem. Finally, based on the techniques developed, we recast Horn’s polynomial time algorithm that solves explicitly given Müller games and provide the first correctness proof of the algorithm. Our algorithms are more efficient than that of Horn’s algorithm. Our solution for connectivity games is used as a subroutine in the algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Explicit Müller games
  • games played on finite graphs
  • winning strategies
  • synthesis and analysis of games

Metrics

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

References

  1. Michael A Bender, Jeremy T Fineman, and Seth Gilbert. A new approach to incremental topological ordering. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 1108-1115. SIAM, 2009. Google Scholar
  2. Michael A Bender, Jeremy T Fineman, Seth Gilbert, and Robert E Tarjan. A new approach to incremental cycle detection and related problems. arXiv preprint, 2011. URL: https://arxiv.org/abs/1112.0784.
  3. Hans L Bodlaender, Michael J Dinneen, and Bakhadyr Khoussainov. On game-theoretic models of networks. In Algorithms and Computation: 12th International Symposium, ISAAC 2001 Christchurch, New Zealand, December 19-21, 2001 Proceedings 12, pages 550-561. Springer, 2001. Google Scholar
  4. Hans L Bodlaender, Michael J Dinneen, and Bakhadyr Khoussainov. Relaxed update and partition network games. Fundamenta Informaticae, 49(4):301-312, 2002. Google Scholar
  5. Cristian S Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 252-263, 2017. Google Scholar
  6. Krishnendu Chatterjee and Monika Henzinger. Efficient and dynamic algorithms for alternating büchi games and maximal end-component decomposition. Journal of the ACM (JACM), 61(3):1-40, 2014. Google Scholar
  7. Michael J Dinneen and Bakhadyr Khoussainov. Update networks and their routing strategies. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 127-136. Springer, 2000. Google Scholar
  8. Stefan Dziembowski, Marcin Jurdzinski, and Igor Walukiewicz. How much memory is needed to win infinite games? In Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, pages 99-110. IEEE, 1997. Google Scholar
  9. Aniruddh Gandhi, Bakhadyr Khoussainov, and Jiamou Liu. Efficient algorithms for games played on trees with back-edges. Fundamenta Informaticae, 111(4):391-412, 2011. Google Scholar
  10. Erich Grädel, Wolfgang Thomas, and Thomas Wilke. Automata, logics, and infinite games. lncs, vol. 2500, 2002. Google Scholar
  11. Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert E Tarjan. Incremental cycle detection, topological ordering, and strong component maintenance. ACM Transactions on Algorithms (TALG), 8(1):1-33, 2012. Google Scholar
  12. Florian Horn. Explicit muller games are ptime. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2008. Google Scholar
  13. Paul Hunter and Anuj Dawar. Complexity bounds for regular games. In International Symposium on Mathematical Foundations of Computer Science, pages 495-506. Springer, 2005. Google Scholar
  14. Paul Hunter and Anuj Dawar. Complexity bounds for muller games. Theoretical Computer Science (TCS), 2008. Google Scholar
  15. Hajime Ishihara and Bakhadyr Khoussainov. Complexity of some infinite games played on finite graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 270-281. Springer, 2002. Google Scholar
  16. Imran Khaliq, Bakhadyr Khoussainov, and Jiamou Liu. Extracting winning strategies in update games. In Models of Computation in Context: 7th Conference on Computability in Europe, CiE 2011, Sofia, Bulgaria, June 27-July 2, 2011. Proceedings 7, pages 142-151. Springer, 2011. Google Scholar
  17. Bakhadyr Khoussainov, Jiamou Liu, and Imran Khaliq. A dynamic algorithm for reachability games played on trees. In Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings 34, pages 477-488. Springer, 2009. Google Scholar
  18. Donald A Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975. Google Scholar
  19. Robert McNaughton. Infinite games played on finite graphs. Annals of Pure and Applied Logic, 65(2):149-184, 1993. Google Scholar
  20. Anil Nerode, Jeffrey B Remmel, and Alexander Yakhnis. Mcnaughton games and extracting strategies for concurrent programs. Annals of Pure and Applied Logic, 78(1-3):203-242, 1996. Google Scholar
  21. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146-160, 1972. Google Scholar
  22. Wieslaw Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science, 200(1-2):135-183, 1998. 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