Polynomial-Time Solvability of Parity Games

A parity game is played forever on a finite directed graph whose vertices belong to two players and carry integer priorities; the winner is determined by the parity of the least priority seen infinitely often. Positional strategies suffice, and the winner problem lies in $\mathrm{UP}\cap\mathrm{coUP}$, as developed through the progress-measure approach of Jurdziński [Jurdzinski1998Parity]. The conjectured polynomial-time algorithm remains one of the central open problems for graph games and verification.

Calude and collaborators broke the long-standing exponential barrier by giving a quasipolynomial-time algorithm [CaludeEtAl2017Quasipolynomial]. Many later algorithms reach comparable quasipolynomial bounds, but none has removed the remaining quasipolynomial overhead in the worst case.

A 2025 preprint by van der Heijden claims a polynomial-time algorithm [VanDerHeijden2025ParityClaim]. The proof presently lacks a justified invariant needed for its key dominion argument and has not been independently validated, so it is tracked as an unestablished claim. Until that gap is closed or another polynomial algorithm appears, parity games in P remains open.