Name
Abstract | ||
|---|---|---|
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(root 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) center dot n)(5)); it is also shown that this bound cannot be improved to 2(o(m center dot log(m))) center dot n(O(1)) in the case that the exponential time hypothesis is true. Further investigations deal with memoryless Muller games and multidimensional parity games. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/17M1145288 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
parity game, quasi-polynomial time algorithm, fixed parameter tractability, Muller game, lower bounds | Journal | 51 |
Issue | ISSN | Citations |
2 | 0097-5397 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristian S. Calude | 1 | 746 | 135.20 |
| Sanjay Jain | 2 | 1647 | 177.87 |
| Bakhadyr Khoussainov | 3 | 0 | 0.34 |
| Wei Li | 4 | 0 | 0.34 |
| Frank Stephan | 5 | 215 | 39.36 |