A Discrete Subexponential Algorithm for Parity Games

We suggest a new randomized algorithm for solving parity games with worst case time complexity roughly where n is the number of vertices and k the number of colors of the game. This is comparable with the previously known algorithms when the number of colors is small. However, the subexponential bound is an advantage when the number of colors is large, k /2(nl/2+)