Polynomial-Time Algorithms for Energy Games with Special Weight Structures
arXiv:1604.08234 · doi:10.1007/s00453-013-9843-7
Abstract
Energy games belong to a class of turn-based two-player infinite-duration games}played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in ${\sf NP} \cap {\sf co\mbox{-}NP}$, but are not known to be in . The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.
arXiv commentThis paper appeared in the ESA 2012 special issue of Algorithmica. A preliminary version was presented at the 20th Annual European Symposium on Algorithms (ESA 2012)
References in corpus (1)
Cited by in corpus (4)
- A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions
- A Convex Programming-based Algorithm for Mean Payoff Stochastic Games with Perfect Information
- Optimizing the Expected Mean Payoff in Energy Markov Decision Processes
- Fast Algorithms for Energy Games in Special Cases