{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:58Z","timestamp":1753889818933,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,6,18]],"date-time":"2013-06-18T00:00:00Z","timestamp":1371513600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Parity games are a much researched class of games in NP intersect CoNP that\nare not known to be in P. Consequently, researchers have considered specialised\nalgorithms for the case where certain graph parameters are small. In this\npaper, we study parity games on graphs with bounded treewidth, and graphs with\nbounded DAG width. We show that parity games with bounded DAG width can be\nsolved in O(n^(k+3) k^(k + 2) (d + 1)^(3k + 2)) time, where n, k, and d are the\nsize, treewidth, and number of priorities in the parity game. This is an\nimprovement over the previous best algorithm, given by Berwanger et al., which\nruns in n^O(k^2) time. We also show that, if a tree decomposition is provided,\nthen parity games with bounded treewidth can be solved in O(n k^(k + 5) (d +\n1)^(3k + 5)) time. This improves over previous best algorithm, given by\nObdrzalek, which runs in O(n d^(2(k+1)^2)) time. Our techniques can also be\nadapted to show that the problem of solving parity games with bounded treewidth\nlies in the complexity class NC^2, which is the class of problems that can be\nefficiently parallelized. This is in stark contrast to the general parity game\nproblem, which is known to be P-hard, and thus unlikely to be contained in NC.<\/jats:p>","DOI":"10.2168\/lmcs-9(2:6)2013","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:39:25Z","timestamp":1385732365000},"source":"Crossref","is-referenced-by-count":1,"title":["Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width"],"prefix":"10.46298","volume":"Volume 9, Issue 2","author":[{"given":"John","family":"Fearnley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9093-9518","authenticated-orcid":false,"given":"Sven","family":"Schewe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2013,6,18]]},"reference":[{"key":"781:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/791\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/791\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:56:12Z","timestamp":1681242972000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/791"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,18]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(2:6)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1112.0221","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1112.0221","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1609.04085","asserted-by":"subject"},{"id-type":"doi","id":"10.4204\/eptcs.226.1","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1609.04085","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2013,6,18]]},"article-number":"791"}}