Parity Games on Graphs with Medium Tree-Width

Abstract This paper studies the problem of solving parity games on graphs with bounded tree-width. Previous work by Obdržálek has produced an algorithm that uses \(n^{O(k^2)}\) time and \(n^{O(k^2)}\) space, where k is the tree-width of the graph that the game is played on. This paper presents an algorithm that uses n O ( k log n ) time and O ( n + k log n ) space. This is the fastest known algorithm for parity games whose tree-width k satisfies (in standard asymptotic notation) k ∈ ω (log n ) and \(k \in o(\sqrt{n}/\log n)\).

Authors

• John Fearnley
• Oded Lachish

Keywords

No keywords are indexed for this paper.