@inproceedings{1f073fd1793e4bbd8184d0ba8d71fc20,
title = "New deterministic algorithms for solving parity games",
abstract = "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 n-kn-k other nodes of the game. Our main result is a fixed-parameter algorithm that solves bipartite parity games in time k o(k v ) ·o(n 3 ) ko(k)·o(n3)k^{o(\sqrt{k})}\cdot o(n^3) and general parity games in time (p+k) o(k v ) ·o(pnm) (p+k)o(k)·o(pnm)(p+k)^{o(\sqrt{k})} \cdot o(pnm), where p denotes the number of distinct priorities and m denotes the number of edges. For all games with k=o(n) k=o(n)k = o(n) this improves the previously fastest algorithm by jurdzinski, paterson, and zwick (sicomp 2008).we also obtain novel kernelization results and an improved deterministic algorithm for graphs with small average degree.",
author = "Matthias Mnich and Heiko R{\"o}glin and Clemens R{\"o}sner",
year = "2016",
doi = "10.1007/978-3-662-49529-2_47",
language = "English",
isbn = "978-3-662-49528-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "634--645",
booktitle = "LATIN 2016: Theoretical Informatics",
address = "United States",
}