A Discrete Subexponential Algorithm for Parity Games

Henrik Björklund, Sven Sandberg, and Sergei Vorobyov

September 2002

Abstract:

We suggest a new randomized algorithm for solving Parity Games with the worst case time complexity roughly
min(O( n³ · ( n/k+1 )^k), 2^{O(sqrt(nlog n))}),
where n is the number of vertices and k the number of colors of the game. Comparable with the previously known algorithms, which are efficient when the number of colors is small, it is subexponential when the number of colors is large, k = Omega (n^{1/2 + varepsilon}).

Available as compressed Postscript (311 kB) and Postscript (904 kB)

Download BibTeX entry.