Technical Report 2003-017

An Improved Subexponential Algorithm for Parity Games

Henrik Björklund, Sven Sandberg, and Sergei Vorobyov

March 2003

We suggest a new algorithm for deciding parity games, a fundamental problem of unknown complexity (in NPcapcoNP, not known to belong to P) in game, automata, complexity theories, combinatorial optimization, temporal logic of programs, computer-aided verification. The novelty of the algorithm consists in exploiting a special form of parity games with retreats, where optimal retreat edges define absorbing facets (with better values than their neighbors on complementary facets) in the strategy space. A superset of such absorbing facets can be found by standard random iterative improvement algorithms in expected polynomial time. Additional dual techniques are used to minimize this superset. As a result, the dimension of the problem shrinks, to which we finally apply the Kalai-Matousek-Sharir-Welzl-Ludwig-style randomization techniques we recently adapted for games [Bjorklund, Sandberg, Vorobyov, STACS'2003 and TR-2003-002]

Available as compressed Postscript (271 kB) and Postscript (769 kB)

Download BibTeX entry.