---
_id: '10905'
abstract:
- lang: eng
  text: "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.\r\nIn 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."
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'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Sebastian
  full_name: Krinninger, Sebastian
  last_name: Krinninger
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
citation:
  ama: 'Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms
    for energy games with special weight structures. In: <i>Algorithms – ESA 2012</i>.
    Vol 7501. Springer; 2012:301-312. doi:<a href="https://doi.org/10.1007/978-3-642-33090-2_27">10.1007/978-3-642-33090-2_27</a>'
  apa: 'Chatterjee, K., Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2012).
    Polynomial-time algorithms for energy games with special weight structures. In
    <i>Algorithms – ESA 2012</i> (Vol. 7501, pp. 301–312). Ljubljana, Slovenia: Springer.
    <a href="https://doi.org/10.1007/978-3-642-33090-2_27">https://doi.org/10.1007/978-3-642-33090-2_27</a>'
  chicago: Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon
    Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.”
    In <i>Algorithms – ESA 2012</i>, 7501:301–12. Springer, 2012. <a href="https://doi.org/10.1007/978-3-642-33090-2_27">https://doi.org/10.1007/978-3-642-33090-2_27</a>.
  ieee: K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time
    algorithms for energy games with special weight structures,” in <i>Algorithms
    – ESA 2012</i>, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312.
  ista: '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 Algorithms, LNCS, vol. 7501, 301–312.'
  mla: Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games
    with Special Weight Structures.” <i>Algorithms – ESA 2012</i>, vol. 7501, Springer,
    2012, pp. 301–12, doi:<a href="https://doi.org/10.1007/978-3-642-33090-2_27">10.1007/978-3-642-33090-2_27</a>.
  short: K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, Algorithms
    – ESA 2012, Springer, 2012, pp. 301–312.
conference:
  end_date: 2012-09-12
  location: Ljubljana, Slovenia
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2012-09-10
date_created: 2022-03-21T08:01:45Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2023-09-05T14:09:30Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-33090-2_27
ec_funded: 1
external_id:
  arxiv:
  - '1604.08234'
intvolume: '      7501'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1604.08234
month: '10'
oa: 1
oa_version: Preprint
page: 301-312
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Algorithms – ESA 2012
publication_identifier:
  eisbn:
  - '9783642330902'
  eissn:
  - 1611-3349
  isbn:
  - '9783642330896'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
  record:
  - id: '535'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Polynomial-time algorithms for energy games with special weight structures
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7501
year: '2012'
...