License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.79
URN: urn:nbn:de:0030-drops-187324
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18732/
Liang, Zihui ;
Khoussainov, Bakh ;
Takisaka, Toru ;
Xiao, Mingyu
Connectivity in the Presence of an Opponent
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.
BibTeX - Entry
@InProceedings{liang_et_al:LIPIcs.ESA.2023.79,
author = {Liang, Zihui and Khoussainov, Bakh and Takisaka, Toru and Xiao, Mingyu},
title = {{Connectivity in the Presence of an Opponent}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {79:1--79:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18732},
URN = {urn:nbn:de:0030-drops-187324},
doi = {10.4230/LIPIcs.ESA.2023.79},
annote = {Keywords: Explicit M\"{u}ller games, games played on finite graphs, winning strategies, synthesis and analysis of games}
}
|
Keywords: |
|
Explicit Müller games, games played on finite graphs, winning strategies, synthesis and analysis of games |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
