A randomized subexponential algorithm for parity games
Viktor Petersson, Sergei G. Vorobyov · 2001
We describe a randomized algorithm for Parity Games (equivalent to the Mu-Calculus Model Checking), which runs in expected time 2 when k is \\Omega\\Gamma n ), n is the number of vertices, and 0 ! " 1=2. That is, our algorithm is subexponential in the number of colors k of the game graph provided that k is not too small. All previously known algorithms were exponential in the number of colors, with the best one taking time and space O(k \\Delta n \\Delta ). Our algorithm does not rely on Linear Programming subroutines and uses a low-degree polynomial space.