Karoliina Lehtinen ; Paweł Parys ; Sven Schewe ; Dominik Wojtczak - A Recursive Approach to Solving Parity Games in Quasipolynomial Time

lmcs:7387 - Logical Methods in Computer Science, January 12, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:8)2022
A Recursive Approach to Solving Parity Games in Quasipolynomial Time

Authors: Karoliina Lehtinen ; Paweł Parys ORCID-iD; Sven Schewe ORCID-iD; Dominik Wojtczak

    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.

    Volume: Volume 18, Issue 1
    Published on: January 12, 2022
    Accepted on: October 26, 2021
    Submitted on: April 21, 2021
    Keywords: Computer Science - Computer Science and Game Theory,Computer Science - Formal Languages and Automata Theory
      Source : OpenAIRE Graph
    • Solving Parity Games in Theory and Practice; Funder: UK Research and Innovation; Code: EP/P020909/1
    • Foundations of Composition; Funder: European Commission; Code: 892704

    1 Document citing this article

    Consultation statistics

    This page has been seen 1006 times.
    This article's PDF has been downloaded 693 times.