A Deterministic Subexponential Algorithm for Solving Parity Games
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (4) , 1519-1532
- https://doi.org/10.1137/070686652
Abstract
The existence of polynomial-time algorithms for the solution of parity games is a major open problem. The fastest known algorithms for the problem are randomized algorithms that run in subexponential time. These algorithms are all ultimately based on the randomized subexponential simplex algorithms of Kalai and of Matoušek, Sharir, and Welzl. Randomness seems to play an essential role in these algorithms. We use a completely different, and elementary, approach to obtain a deterministic subexponential algorithm for the solution of parity games. The new algorithm, like the existing randomized subexponential algorithms, uses only polynomial space, and it is almost as fast as the randomized subexponential algorithms mentioned above.Keywords
This publication has 12 references indexed in Scilit:
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff gamesDiscrete Applied Mathematics, 2007
- Quantitative solution of omega-regular gamesJournal of Computer and System Sciences, 2004
- The Random-Facet simplex algorithm on combinatorial cubesRandom Structures & Algorithms, 2002
- Deciding the winner in parity games is in UP ∩ co-UPInformation Processing Letters, 1998
- A Subexponential Bound for Linear ProgrammingAlgorithmica, 1996
- A SUBEXPONENTIAL RANDOMIZED ALGORITHM FOR THE SIMPLE STOCHASTIC GAME PROBLEMInformation and Computation, 1995
- On the complexity of the parity argument and other inefficient proofs of existenceJournal of Computer and System Sciences, 1994
- Infinite games played on finite graphsAnnals of Pure and Applied Logic, 1993
- The complexity of stochastic gamesInformation and Computation, 1992
- How easy is local search?Journal of Computer and System Sciences, 1988