Technical Report 2003-002

On Combinatorial Structure and Algorithms for Parity Games

Henrik Björklund, Sven Sandberg, and Sergei Vorobyov

January 2003

In this paper we identify and systematically explore the combinatorial structure underlying parity and simple stochastic games. We introduce the class of Completely LG (local-global) functions with nice structural properties pertinent to games and allowing for efficient optimization by iterative improvement local search style algorithms. We demonstrate several important combinatorial properties of Completely LG functions, allowing for many optimization algorithms, and establish a relation with the subclass of Completely Unimodal functions, studied by Hammer et al. [1988] Williamson Hoke [1988], and Wiedemann [1985]. We also describe a new, compared to our recent [STACS'2003], subexponential randomized algorithm for CU-functions, CLG-functions, parity, and simple stochastic games, and establish a relation with the class of LP-type problems introduced and investigated by Sharir \& Welzl [1992] and Matousek, Sharir \& Welzl [1992].

Available as compressed Postscript (304 kB) and Postscript (870 kB)

Download BibTeX entry.