A Recursive Approach to Solving Parity Games in Quasipolynomial Time
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of Zie...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2022-01-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/7387/pdf |
| Summary: | Zielonka's classic recursive algorithm for solving parity games is perhaps
the simplest among the many existing parity game algorithms. However, its
complexity is exponential, while currently the state-of-the-art algorithms have
quasipolynomial complexity. Here, we present a modification of Zielonka's
classic algorithm that brings its complexity down to
$n^{O\left(\log\left(1+\frac{d}{\log n}\right)\right)}$, for parity games of
size $n$ with $d$ priorities, in line with previous quasipolynomial-time
solutions. |
|---|---|
| ISSN: | 1860-5974 |