The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs

DOI10.1016/J.TCS.2013.12.021zbMATH Open1303.68066arXiv1210.2459OpenAlexW1963571124MaRDI QIDQ477199FDOQ477199

Erich Grädel, Roman Rabinovich, Felix Canavoi

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1210.2459

Recommendations

• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
• scientific article; zbMATH DE number 1670778
• Parameterized Algorithms for Parity Games
• scientific article; zbMATH DE number 1962853
• The complexity of all-switches strategy improvement

zbMATH Keywords

treewidthparity gamesgraph complexity measures

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Entanglement and the complexity of directed graphs
• Handle-rewriting hypergraph grammars
• The dag-width of directed graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Logic for Programming, Artificial Intelligence, and Reasoning
• Digraph measures: Kelly decompositions, games, and orderings
• A subexponential bound for linear programming
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computer Aided Verification
• A deterministic subexponential algorithm for solving parity games
• Clique-Width and Parity Games
• A superpolynomial lower bound for strategy iteration based on snare memorization
• Non-oblivious Strategy Improvement
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Theoretical Properties of the Network Simplex Method

Cited In (2)

• Deciding Parity Games in Quasi-polynomial Time
• Title not available (Why is that?)

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)