Deciding Parity Games in Quasi-polynomial Time
Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Frank Stephan
Abstract
It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct values (a.k.a. colors or priorities)---is proven to be in the class of fixed parameter tractable problems when parameterized over $m$. Both results improve known bounds, from runtime $n^{O(\sqrt{n})}$ to $O(n^{\log(m)+6})$ and from an XP algorithm with runtime $O(n^{\Theta(m)})$ for fixed parameter $m$ to a fixed parameter tractable algorithm with runtime $O(n^5+2^{m\log(m)+6m})$. As an application, it is proven that colored Muller games with $n$ nodes and $m$ colors can be decided in time $O((m^m \cdot n)^5)$; it is also shown that this bound cannot be improved to $2^{o(m \cdot \log(m))} \cdot n^{O(1)}$ in the case that the exponential time hypothesis is true. Further investigations deal with memoryless Muller games and multidimensional parity games.