The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
From MaRDI portal
(Redirected from Publication:477199)
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1670778 (Why is no real title available?)
- scientific article; zbMATH DE number 5869590 (Why is no real title available?)
- scientific article; zbMATH DE number 1500523 (Why is no real title available?)
- A deterministic subexponential algorithm for solving parity games
- A subexponential bound for linear programming
- A superpolynomial lower bound for strategy iteration based on snare memorization
- An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
- Clique-Width and Parity Games
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Digraph measures: Kelly decompositions, games, and orderings
- Entanglement and the complexity of directed graphs
- Fast mu-calculus model checking when tree-width is bounded.
- Handle-rewriting hypergraph grammars
- Logic for Programming, Artificial Intelligence, and Reasoning
- Non-oblivious strategy improvement
- On the clique-width of some perfect graph classes
- The dag-width of directed graphs
- Theoretical Properties of the Network Simplex Method
Cited in
(6)- Deciding Parity Games in Quasi-polynomial Time
- The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
- The complexity of all-switches strategy improvement
- scientific article; zbMATH DE number 1670778 (Why is no real title available?)
- The complexity of all-switches strategy improvement
- A superpolynomial lower bound for strategy iteration based on snare memorization
This page was built for publication: The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477199)
