10.1007/s00453-013-9843-7
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Henzinger, Monika
Monika
Henzinger
Krinninger, Sebastian
Sebastian
Krinninger
Nanongkai, Danupon
Danupon
Nanongkai
Polynomial time algorithms for energy games with special weight structures
Springer
2014
2018-12-11T11:47:01Z
2020-01-16T12:37:22Z
journal_article
https://research-explorer.app.ist.ac.at/record/535
https://research-explorer.app.ist.ac.at/record/535.json
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 NP∩co-NP, but are not known to be in P. 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.