Improved complexity analysis of quasi-polynomial algorithms solving parity games

DOI10.1007/978-3-031-36978-0_22MaRDI QIDQ6149052zbMATH OpenOpenAlexFDO

Authors Paweł Parys, Aleksander Wiącek

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

parity gamesquasi-polynomial timeuniversal trees

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: We improve the complexity of solving parity games (with priorities in vertices) for $d=omega(logn)$ by a factor of $heta(d^2)$: the best complexity known to date was $O(md{n}^{1.45+lo{g}_2(d/lo{g}_2(n))})$, while we obtain $O(m{n}^{1.45+lo{g}_2(d/lo{g}_2(n))}/d)$, where $n$ is the number of vertices, $m$ is the number of edges, and $d$ is the number of priorities. We base our work on existing algorithms using universal trees, and we improve their complexity. We present two independent improvements. First, an improvement by a factor of $heta(d)$ comes from a more careful analysis of the width of universal trees. Second, we perform (or rather recall) a finer analysis of requirements for a universal tree: while for solving games with priorities on edges one needs an $n$-universal tree, in the case of games with priorities in vertices it is enough to use an $n/2$-universal tree. This way, we allow to solve games of size $2n$ in the time needed previously to solve games of size $n$; such a change divides the quasi-polynomial complexity again by a factor of $heta(d)$.

Recommendations

• A recursive approach to solving parity games in quasipolynomial time
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games
• Deciding Parity Games in Quasi-polynomial Time

Cites work

• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A Deterministic Subexponential Algorithm for Solving Parity Games
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• A recursive approach to solving parity games in quasipolynomial time
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• Alternating weak automata from universal trees
• An improved algorithm for the evaluation of fixpoint expressions
• Deciding parity games in quasipolynomial time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Exponential lower bounds for policy iteration
• Fast and simple nested fixpoints
• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• On model checking for the -calculus and its fragments
• On the Way to Alternating Weak Automata
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Solving parity games in big steps
• Solving parity games via priority promotion
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• Succinct progress measures for solving parity games
• Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games

Cited in

(1)

• Universal algorithms for parity games and nested fixpoints

This page was built for publication: Improved complexity analysis of quasi-polynomial algorithms solving parity games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149052)