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 |
| _version_ | 1797268493534494720 |
|---|---|
| author | Karoliina Lehtinen Paweł Parys Sven Schewe Dominik Wojtczak |
| author_facet | Karoliina Lehtinen Paweł Parys Sven Schewe Dominik Wojtczak |
| author_sort | Karoliina Lehtinen |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:33:21Z |
| format | Article |
| id | doaj.art-59bbc12a8f7f4e2ba59f098689485645 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:33:21Z |
| publishDate | 2022-01-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-59bbc12a8f7f4e2ba59f0986894856452024-03-08T10:36:53ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742022-01-01Volume 18, Issue 110.46298/lmcs-18(1:8)20227387A Recursive Approach to Solving Parity Games in Quasipolynomial TimeKaroliina LehtinenPaweł Paryshttps://orcid.org/0000-0001-7247-1408Sven Schewehttps://orcid.org/0000-0002-9093-9518Dominik WojtczakZielonka'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.https://lmcs.episciences.org/7387/pdfcomputer science - computer science and game theorycomputer science - formal languages and automata theory |
| spellingShingle | Karoliina Lehtinen Paweł Parys Sven Schewe Dominik Wojtczak A Recursive Approach to Solving Parity Games in Quasipolynomial Time Logical Methods in Computer Science computer science - computer science and game theory computer science - formal languages and automata theory |
| title | A Recursive Approach to Solving Parity Games in Quasipolynomial Time |
| title_full | A Recursive Approach to Solving Parity Games in Quasipolynomial Time |
| title_fullStr | A Recursive Approach to Solving Parity Games in Quasipolynomial Time |
| title_full_unstemmed | A Recursive Approach to Solving Parity Games in Quasipolynomial Time |
| title_short | A Recursive Approach to Solving Parity Games in Quasipolynomial Time |
| title_sort | recursive approach to solving parity games in quasipolynomial time |
| topic | computer science - computer science and game theory computer science - formal languages and automata theory |
| url | https://lmcs.episciences.org/7387/pdf |
| work_keys_str_mv | AT karoliinalehtinen arecursiveapproachtosolvingparitygamesinquasipolynomialtime AT pawełparys arecursiveapproachtosolvingparitygamesinquasipolynomialtime AT svenschewe arecursiveapproachtosolvingparitygamesinquasipolynomialtime AT dominikwojtczak arecursiveapproachtosolvingparitygamesinquasipolynomialtime AT karoliinalehtinen recursiveapproachtosolvingparitygamesinquasipolynomialtime AT pawełparys recursiveapproachtosolvingparitygamesinquasipolynomialtime AT svenschewe recursiveapproachtosolvingparitygamesinquasipolynomialtime AT dominikwojtczak recursiveapproachtosolvingparitygamesinquasipolynomialtime |