The Discrete Strategy Improvement Algorithm for Parity Games and Complexity Measures for Directed Graphs
Source: Creative Commons
For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time. However, it has recently been proved by Oliver Friedmann that the strategy improvement algorithm requires super-polynomially many iteration steps, for all popular local improvements rules, including switch-all (also with Fearnley's snare memorisation), switch-best, random-facet, random-edge, switch-half, least-recently-considered, and Zadeh's Pivoting rule. The authors analyze the examples provided by Friedmann in terms of complexity measures for directed graphs such as tree width, DAG-width, Kelly-width, entanglement, directed path width, and clique width. It is known that for every class of parity games on which one of these parameters is bounded, the winning regions can be efficiently computed.