In this talk we will describe a Quasi Polynomial time algorithm for parity games given by Calude et al (STOC 2017). The runtime for the algorithm is O(n~((log)(m)+6)), where n is the number of nodes and m is the number of colours (priorities). The parameterised parity game - with n nodes and m distinct colours is proven to be in the class of fixed parameter tractable problems (FPT) when parameterised over m. The corresponding runtime is O(n~5 +g(m)), where g(m) can be taken to be m~(m+6). We will also discuss the next developments in the field which improved the above algorithm by making it simultaneously in near linear space by Jurdzinski and Lazic (LICS 2017) and Fearnley et al (SPIN 2017). Recently, Lehtinen (LICS 2018) introduced the notion of register index complexity and showed that this is logarithmic in the number of nodes; furthermore, a game with register index complexity k, the parity game can be solved in time m~(O(k)) . n~(O(1)) which provides another quasipolynomial time algorithm for parity games.
展开▼
