Deciding Parity Games in Quasipolynomial Time

20^th June 2017, 13:00 George Holt H223
Prof. Frank Stephan
Department of Mathematics and
School of Computing
National University of Singapore

Abstract

It is shown that the parity game can be solved in quasipolynomial
time. The parameterised parity game -- with n nodes
and m distinct values (aka colours or priorities) --
is proven to be in the class of fixed parameter tractable (FPT)
problems when parameterised over m.
Both results improve known bounds, from runtime
n^{O(sqrtn)}$ to O(n^{log(m)+6})
and from an XP-algorithm with runtime n^{m/3+O(1)}
for fixed parameter m to an FPT-algorithm with runtime O(n^5)+g(m),
for some function g depending on m only.
As an application it is proven that
coloured Muller games with $n$ nodes and $m$ colours can be decided
in time O((m^m * n)^5); it is also shown that this bound cannot be
improved to 2^{o(m * \log(m))} * Poly(n) unless FPT = W[1].
Further investigations deal with memoryless Muller games and
multi-dimensional parity games.