2015/12/10 by Matthias Mnich, Mnich, Matthias, Heiko Röglin +3
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1512.03246
arxiv created 2015/12/10 · arxiv updated 2015/12/12
We study parity games in which one of the two players controls only a small number k of nodes and the other player controls the n-k other nodes of the game. Our main result is a fixed-parameter algorithm that solves bipartite parity games in time kO(√(k))⋅ O(n3), and general parity games in time (p+k)O(√(k)) ⋅ O(pnm), where p is the number of distinct priorities and m is the number of edges. For all games with k = o(n) this improves the previously fastest algorithm by Jurdziński, Paterson, and Zwick (SICOMP 2008). We also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree.