Technical Report 2003-038

On Fixed-Parameter Complexity of Infinite Games

Henrik Björklund, Sven Sandberg, and Sergei Vorobyov

August 2003

Abstract:

We investigate and classify fixed parameter complexity of several infinite duration games, including Rabin, Streett, Muller, parity, mean payoff, and simple stochastic, using different natural parameterizations.

Most known fixed parameter intractable games are PSPACE- or EXP-complete classically, AW[*] or XP-hard parametrically, and are all finite duration games. In contrast, the games we consider are infinite duration, solvable in positional or finite memory strategies, and belong to "lower" complexity classes, like NP and/or coNP. However, the best known algorithms they possess are of complexity nf(k), i.e., XP is the only upper bound, with no known parametric lower bounds.

We demonstrate that under different parameterizations these games may have different or equivalent FPT-statuses, and present several tractable and intractable cases.

Available as Postscript (1.05 MB) and compressed Postscript (405 kB)

Download BibTeX entry.