Efficient Algorithms for Games Played on Trees with Back-edges

Article type: Research Article

Authors: Gandhi, Aniruddh | Khoussainov, Bakhadyr | Liu, Jiamou

Affiliations: Department of Computer Science, University of Auckland, Auckland, New Zealand. agan014@aucklanduni.ac.nz; bmk@cs.auckland.ac.nz | School of Computing and Mathematical Sciences, Auckland University of Technology, Auckland, New Zealand. jiamou.liu@aut.ac.nz

Note: [] Address for correspondence: Department of Computer Science, University of Auckland, Auckland, New Zealand

Abstract: This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Büchi games played on trees with back-edges in time O(min{r·m, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees with back-edges can be solved in time O(l + m).

Keywords: Büchi games, trees with back-edges, snares, parity games, experiment

DOI: 10.3233/FI-2011-569

Journal: Fundamenta Informaticae, vol. 111, no. 4, pp. 391-412, 2011