Paper Info
Title
A subexponential lower bound for the random facet algorithm for parity games
Abstract
Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matoušek, Sharir and Welzl for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i.e., 2O(√n log n), where n is the number of vertices in the game. We focus in this paper on the algorithm of Matoušek, Sharir and Welzl and refer to it as the Random Facet algorithm. Matoušek constructed a family of abstract optimization problems such that the expected running time of the Random Facet algorithm, when run on a random instance from this family, is close to the subexponential upper bound given above. This shows that in the abstract setting, the 2O(√n log n) upper bound on the complexity of the Random Facet algorithm is essentially tight. It is not known, however, whether the abstract optimization problems constructed by Matoušek correspond to games of any of the families mentioned above. There was some hope, therefore, that the Random Facet algorithm, when applied to, say, parity games, may run in polynomial time. We show, that this, unfortunately, is not the case by constructing explicit parity games on which the expected running time of the Random Facet algorithm is close to the subexponential upper bound. The games we use mimic the behavior of a randomized counter. They are also the first explicit LP-type problems on which the Random Facet algorithm is not polynomial.
Year
DOI
Venue
2011
10.5555/2133036.2133055
SODA
Keywords
Field
DocType
parity game,randomized algorithm,fastest algorithm,random facet algorithm,abstract setting,deterministic mean payoff games,abstract generalization,abstract optimization problem,polynomial time,n log n,natural subclass,lower bound
Randomized algorithm,Discrete mathematics,Combinatorics,Open problem,Polynomial,Upper and lower bounds,Algorithm,Linear programming,Facet (geometry),Time complexity,Mathematics,Stochastic game
Conference
ISBN
Citations 
PageRank 
978-1-61197-251-1
10
0.57
References 
Authors
30
3
Name
Order
Citations
PageRank
Oliver Friedmann119814.29
Thomas Dueholm Hansen216113.77
Uri Zwick33586257.02