  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.
  We analyse the examples provided by Friedmann in terms of complexity measures
for directed graphs such as treewidth, DAG-width, Kelly-width, entanglement,
directed pathwidth, and cliquewidth. 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. It turns out that with respect to almost all of these
measures, the complexity of Friedmann's counterexamples is bounded, and indeed
in most cases by very small numbers. This analysis strengthens in some sense
Friedmann's results and shows that the discrete strategy improvement algorithm
is even more limited than one might have thought. Not only does it require
super-polynomial running time in the general case, where the problem of
polynomial-time solvability is open, it even has super-polynomial lower time
bounds on natural classes of parity games on which efficient algorithms are
known.
