Uppsala University
Department of Information Technology

### Technical Report 2002-026

# 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*^{3} · ( 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.