Logo der Universität Wien

Polynomial-time Algorithms for Energy Games with Special Weight Structures

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 needs not help.

Grafik Top
Citation
Category
Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
20th Annual European Symposium on Algorithms (ESA 2012)
Divisions
Theory and Applications of Algorithms
Event Location
Ljubljana, Slovenia
Event Type
Conference
Event Dates
10-12 Sep 2012
Series Name
Lecture Notes in Computer Science
ISSN/ISBN
978-3-642-33089-6
Publisher
Springer
Page Range
pp. 301-312
Date
2012
Official URL
http://link.springer.com/chapter/10.1007/978-3-642...
Export
Grafik Top
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna