Earlier Version

Polynomial-time algorithms for energy games with special weight structures

Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. Algorithms – ESA 2012. ESA: European Symposium on AlgorithmsLNCS vol. 7501, 301–312.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author
Chatterjee, KrishnenduISTA ; Henzinger, MonikaISTA ; Krinninger, Sebastian; Nanongkai, Danupon
Editor
Epstein, Leah; Ferragina, Paolo
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. While the existence of polynomial-time algorithms has been a major open problem for decades, 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 counter examples that show that many 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 graph structures need not help.
Publishing Year
Date Published
2012-10-01
Proceedings Title
Algorithms – ESA 2012
Acknowledgement
Supported by the Austrian Science Fund (FWF): P23499-N23, the Austrian Science Fund (FWF): S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award
Volume
7501
Page
301-312
Conference
ESA: European Symposium on Algorithms
Conference Location
Ljubljana, Slovenia
Conference Date
2012-09-10 – 2012-09-12
IST-REx-ID

Cite this

Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. In: Epstein L, Ferragina P, eds. Algorithms – ESA 2012. Vol 7501. LNCS. Berlin, Heidelberg: Springer; 2012:301-312. doi:10.1007/978-3-642-33090-2_27
Chatterjee, K., Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2012). Polynomial-time algorithms for energy games with special weight structures. In L. Epstein & P. Ferragina (Eds.), Algorithms – ESA 2012 (Vol. 7501, pp. 301–312). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-33090-2_27
Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” In Algorithms – ESA 2012, edited by Leah Epstein and Paolo Ferragina, 7501:301–12. LNCS. Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-33090-2_27.
K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” in Algorithms – ESA 2012, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312.
Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2012. Polynomial-time algorithms for energy games with special weight structures. Algorithms – ESA 2012. ESA: European Symposium on AlgorithmsLNCS vol. 7501, 301–312.
Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” Algorithms – ESA 2012, edited by Leah Epstein and Paolo Ferragina, vol. 7501, Springer, 2012, pp. 301–12, doi:10.1007/978-3-642-33090-2_27.

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1604.08234

Search this title in

Google Scholar
ISBN Search