Solving infinite games on trees with back-edges
Aniruddh Gandhi, Bakhadyr Khoussainov, Jiamou Liu · 2012
We study the computational complexity of solving the following problem: Given a game G played on a fi-nite directed graph G, output all nodes in G from which a specific player wins the game G. We pro-vide algorithms for solving the above problem when the games have Büchi and parity winning conditions and the graph G is a tree with back-edges. The running time of the algorithm for Büchi games is O(min{r ·m, ℓ+m}) where m is the number of edges, ℓ is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. The algorithm for parity has a running time of O(ℓ +m). 1