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. 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.

GrafikTop
Citation
Category
Journal Paper
Divisions
Theory and Applications of Algorithms
Subjects
Theoretische Informatik
Journal or Publication Title
Algorithmica: an international journal in computer science
ISSN
0178-4617
Publisher
Springer
Page Range
pp. 457-492
Number
3
Volume
70
Date
2014
Export
GrafikTop
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna