文章基本信息

标题：Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
本地全文：下载
作者：Pawel Parys
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-13
DOI：10.4230/LIPIcs.MFCS.2019.10
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out that in practice they operate very slowly. On the other side there is Zielonka's recursive algorithm, which is very simple, exponential in the worst case, and the fastest in practice. We combine these two approaches: we propose a small modification of Zielonka's algorithm, which ensures that the running time is at most quasi-polynomial. In effect, we obtain a simple algorithm that solves parity games in quasi-polynomial time. We also hope that our algorithm, after further optimizations, can lead to an algorithm that shares the good performance of Zielonka's algorithm on typical inputs, while reducing the worst-case complexity on difficult inputs.
关键词：Parity games; Zielonka's algorithm; quasi-polynomial time