Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time

Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games.

After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out that in practice they operate very slowly.

On the other side there is the Zielonka’s recursive algorithm, which is very simple, exponential in the worst case, and the fastest in practice.

We combine these two approaches: we propose a small modification of the Zielonka’s algorithm, which ensures that the running time is at most quasi-polynomial.

In effect, we obtain a simple algorithm that solves parity games in quasi-polynomial time.