Polynomial time algorithms for energy games with special weight structures

K. Chatterjee, M. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492.


Journal Article | Published | English
Author
; ; ;
Department
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 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.
Publishing Year
Date Published
2014-11-01
Journal Title
Algorithmica
Volume
70
Issue
3
Page
457 - 492
IST-REx-ID

Cite this

Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. Polynomial time algorithms for energy games with special weight structures. Algorithmica. 2014;70(3):457-492. doi:10.1007/s00453-013-9843-7
Chatterjee, K., Henzinger, M., Krinninger, S., & Nanongkai, D. (2014). Polynomial time algorithms for energy games with special weight structures. Algorithmica, 70(3), 457–492. https://doi.org/10.1007/s00453-013-9843-7
Chatterjee, Krishnendu, Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial Time Algorithms for Energy Games with Special Weight Structures.” Algorithmica 70, no. 3 (2014): 457–92. https://doi.org/10.1007/s00453-013-9843-7.
K. Chatterjee, M. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial time algorithms for energy games with special weight structures,” Algorithmica, vol. 70, no. 3, pp. 457–492, 2014.
Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2014. Polynomial time algorithms for energy games with special weight structures. Algorithmica. 70(3), 457–492.
Chatterjee, Krishnendu, et al. “Polynomial Time Algorithms for Energy Games with Special Weight Structures.” Algorithmica, vol. 70, no. 3, Springer, 2014, pp. 457–92, doi:10.1007/s00453-013-9843-7.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar