---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Monika
foaf_name: Henzinger, Monika
foaf_surname: Henzinger
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Krinninger, Sebastian
foaf_surname: Krinninger
- foaf_Person:
foaf_givenName: Danupon
foaf_name: Nanongkai, Danupon
foaf_surname: Nanongkai
bibo_doi: 10.1007/s00453-013-9843-7
bibo_issue: '3'
bibo_volume: 70
dct_date: 2014^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Polynomial time algorithms for energy games with special weight structures@
...