{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:14:50Z","timestamp":1790813690286,"version":"4.1.0"},"reference-count":80,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100009193","name":"Marsden Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2016-T2-1-019\/R146-000-234-112"],"award-info":[{"award-number":["MOE2016-T2-1-019\/R146-000-234-112"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["C252-000-087-001"],"award-info":[{"award-number":["C252-000-087-001"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct values (a.k.a. colors or priorities)---is proven to be in the class of fixed parameter tractable problems when parameterized over $m$. Both results improve known bounds, from runtime $n^{O(\\sqrt{n})}$ to $O(n^{\\log(m)+6})$ and from an XP algorithm with runtime $O(n^{\\Theta(m)})$ for fixed parameter $m$ to a fixed parameter tractable algorithm with runtime $O(n^5+2^{m\\log(m)+6m})$. As an application, it is proven that colored Muller games with $n$ nodes and $m$ colors can be decided in time $O((m^m \\cdot n)^5)$; it is also shown that this bound cannot be improved to $2^{o(m \\cdot \\log(m))} \\cdot n^{O(1)}$ in the case that the exponential time hypothesis is true. Further investigations deal with memoryless Muller games and multidimensional parity games.<\/jats:p>","DOI":"10.1137\/17m1145288","type":"journal-article","created":{"date-parts":[[2020,1,15]],"date-time":"2020-01-15T10:16:19Z","timestamp":1579083379000},"page":"STOC17-152-STOC17-188","source":"Crossref","is-referenced-by-count":17,"title":["Deciding Parity Games in Quasi-polynomial Time"],"prefix":"10.1137","volume":"51","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bakhadyr","family":"Khoussainov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9152-1706","authenticated-orcid":true,"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,1,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320614"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228289"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2002013"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1147-5"},{"key":"atypb5","unstructured":"H. Bj\u00f6rklund, S. Sandberg, and S. Vorobyov,\n                      On Fixed-Parameter Complexity of Infinite Games\n                      , Technical report 2003-038, Uppsala University, Uppsala, Sweden, 2003."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00427-4"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, M. J. Dinneen, and B. Khoussainov,\n                      On game-theoretic models of networks\n                      , in Proceedings of the Twelfth International Symposium on Algorithms and Computation, ISAAC 2001, Christchurch, New Zealand, 2001, Lecture Notes in Comput. Sci. 2223, Springer, 2001, pp. 550-561.","DOI":"10.1007\/3-540-45678-3_47"},{"key":"atypb8","first-page":"301","volume":"49","author":"Bodlaender H. L.","year":"2002","journal-title":"Fund. Inform."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00228-9"},{"key":"atypb10","unstructured":"V. Bruy\u00e8re, Q. Hautem, and J.F. Raskin,\n                      Games with Lexicographically Ordered $\\omega$-Regular Objectives\n                      , preprint,https:\/\/arxiv.org\/abs\/1707.05968, 2017."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"C. S. Calude, S. Jain, B. Khoussainov, W. Li, and F. Stephan,\n                      Deciding parity games in quasipolynomial time\n                      , in STOC 2017 Theory Fest: Forty-Ninth Annual ACM Symposium on Theory of Computing, Montreal, Canada, ACM, 2017, pp. 252-263.","DOI":"10.1145\/3055399.3055409"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.12.021"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"atypb14","unstructured":"K. Chatterjee,\n                      Comments on the Quasipolynomial Time Algorithm\n                      , private communication, 2017."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_42"},{"key":"atypb16","first-page":"178","author":"Chatterjee K.","year":"2005","journal-title":"IEEE"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71389-0_12"},{"key":"atypb18","first-page":"121","author":"Chatterjee K.","year":"2004","journal-title":"SIAM"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-013-0182-6"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40184-8_35"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"S. A. Cook,\n                      Path systems and language recognition\n                      , in Proceedings of the Second Annual ACM Symposium on Theory of Computing, STOC 1970, Northampton, MA, ACM, 1970, pp. 70-72.","DOI":"10.1145\/800161.805151"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"S. A. Cook,\n                      The complexity of theorem proving procedures\n                      , in Proceedings of the Third Annual ACM Symposium on the Theory of Computing, STOC 1971, Shaker Heights, OH, ACM, 1971, pp. 151-158.","DOI":"10.1145\/800157.805047"},{"key":"atypb24","unstructured":"A. Dawar, F. Horn, and P. Hunter,\n                      Complexity Bounds for Muller Games\n                      , manuscript, 2011."},{"key":"atypb25","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/978-3-319-40946-7_6","volume":"9705","author":"Stasio A. Di","year":"2016","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.044"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterised Complexity\n                      , Springer, Heidelberg, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity Theory\n                      , Springer, Heidelberg, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb29","first-page":"99","author":"Dziembowski S.","year":"1997","journal-title":"IEEE"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15648-8_7"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"E. A. Emerson and C. S. Jutla,\n                      The complexity of tree automata and logics of programs\n                      , in Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, IEEE, pp. 328-337.","DOI":"10.1109\/SFCS.1988.21949"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"E. A. Emerson and C. S. Jutla,\n                      Tree automata, $\\mu$-calculus and determinacy\n                      , in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, IEEE, pp. 368-377.","DOI":"10.1109\/SFCS.1991.185392"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00034-7"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-019-00509-3"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.2478\/s11533-010-0014-7"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1327068708"},{"key":"atypb37","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Springer, 2006."},{"key":"atypb38","first-page":"145","volume":"2009","author":"Friedmann O.","year":"2009","journal-title":"LICS"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04761-9_15"},{"key":"atypb40","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/978-3-662-48054-0_28","volume":"9235","author":"Gajarsk\u00fd J.","year":"2015","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2011-569"},{"key":"atypb42","unstructured":"H. Gimbert and R. Ibsen-Jensen,\n                      A Short Proof of Correctness of the Quasi-Polynomial Time Algorithm for Parity Games\n                      , preprint,https:\/\/arxiv.org\/abs\/1702.01953, 2017."},{"key":"atypb43","unstructured":"E. Gr\u00e4del, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema, and S. Weinstein,\n                      Finite Model Theory and Its Applications\n                      , Springer, 2007."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.11.032"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"Y. Gurevich and L. Harrington,\n                      Trees, automata and games\n                      , in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC 1982, San Francisco, CA, 1982, pp. 60-65.","DOI":"10.1145\/800070.802177"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.04.010"},{"key":"atypb47","unstructured":"F. Horn,\n                      Explicit Muller games are \\bf PTIME\n                      , in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2008, pp. 235-245."},{"key":"atypb48","unstructured":"P. W. Hunter,\n                      Complexity and Infinite Games on Finite Graphs\n                      , Ph.D. thesis, University of Cambridge, 2007."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_43"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90039-8"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36379-3_24"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00150-1"},{"key":"atypb53","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/3-540-46541-3_24","volume":"1770","author":"Jurdzi\u0144ski M.","year":"2000","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u0144ski and R. Lazi\u0107,\n                      Succinct progress measures for solving parity games\n                      , in Logic in Computer Science, LICS 2017; preprint,https:\/\/arxiv.org\/abs\/1702.05051, 2017.","DOI":"10.1109\/LICS.2017.8005092"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1137\/070686652"},{"key":"atypb56","first-page":"129","author":"Khaliq I.","year":"2016","journal-title":"DE"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"B. Khoussainov and A. Nerode,\n                      Automata Theory and Its Applications\n                      , Birkh\u00e4user, 2001.","DOI":"10.1007\/978-1-4612-0171-7"},{"key":"atypb58","doi-asserted-by":"crossref","unstructured":"D. Kuske, J. Liu, and M. Lohrey,\n                      The isomorphism problem for omega-automatic trees\n                      , in Proceedings of Computer Science Logic, CSL 2010, Lecture Notes in Comput. Sci. 6247, Springer, 2010, pp. 396-410.","DOI":"10.1007\/978-3-642-15205-4_31"},{"key":"atypb59","first-page":"639","author":"Lehtinen K.","year":"2018","journal-title":"UK"},{"key":"atypb60","first-page":"115","volume":"3","author":"Levin L. A.","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90036-D"},{"key":"atypb62","unstructured":"A. W. Mostowski,\n                      Games with Forbidden Positions\n                      , Technical report 78, Uniwersytet Gdanski, Instytut Matematyki, 1991."},{"key":"atypb63","unstructured":"J. Obdrzalek,\n                      Algorithmic Analysis of Parity Games\n                      , Ph.D. thesis, University of Edinburgh, 2006."},{"key":"atypb64","first-page":"324","volume":"8","author":"Petersson V.","year":"2001","journal-title":"Nordic J. Comput."},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(3:5)2007"},{"key":"atypb66","first-page":"528","author":"Piterman N.","year":"2006","journal-title":"IEEE Computer Society"},{"key":"atypb67","unstructured":"G. Point,\n                      The Synthesis Toolbox: From Modal Automata to Controller Synthesis\n                      , Research report 1342-05, LaBRI - UMR CNRS 5800, 2005."},{"key":"atypb68","first-page":"319","author":"Safra S.","year":"1988","journal-title":"Proceedings of the Twenty-Ninth IEEE Symposium on Foundations of Computer Science, IEEE"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798332518"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77050-3_37"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_57"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.10.002"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00130-5"},{"key":"atypb74","unstructured":"F. Stephan,\n                      Methods and Theory of Automata and Languages\n                      , Lecture Notes, School of Computing, National University of Singapore, 2016,http:\/\/www.comp.nus.edu.sg\/ fstephan\/fullautomatatheory-nov2016.ps."},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/7.1.103"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59042-0_57"},{"key":"atypb77","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2015.03.001"},{"key":"atypb78","first-page":"261","volume":"36","author":"Walukiewicz I.","year":"2001","journal-title":"Inform. and Comput."},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.36045\/bbms\/1102714178"},{"key":"atypb80","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00009-7"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1145288","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:31Z","timestamp":1787337331000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1145288"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,14]]},"references-count":80,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1137\/17M1145288"],"URL":"https:\/\/doi.org\/10.1137\/17m1145288","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,14]]}}}