Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width

Parity games are a much researched class of games in NP intersect CoNP thatare not known to be in P. Consequently, researchers have considered specialisedalgorithms for the case where certain graph parameters are small. In thispaper, we study parity games on graphs with bounded treewidth, and graphs withbounded DAG width. We show that parity games with bounded DAG width can besolved in O(n^(k+3) k^(k + 2) (d + 1)^(3k + 2)) time, where n, k, and d are thesize, treewidth, and number of priorities in the parity game. This is animprovement over the previous best algorithm, given by Berwanger et al., whichruns in n^O(k^2) time. We also show that, if a tree decomposition is provided,then parity games with bounded treewidth can be solved in O(n k^(k + 5) (d +1)^(3k + 5)) time. This improves over previous best algorithm, given byObdrzalek, which runs in O(n d^(2(k+1)^2)) time. Our techniques can also beadapted to show that the problem of solving parity games with bounded treewidthlies in the complexity class NC^2, which is the class of problems that can beefficiently parallelized. This is in stark contrast to the general parity gameproblem, which is known to be P-hard, and thus unlikely to be contained in NC