  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 ${\sf NP} \cap {\sf co\mbox{-}NP}$, but are
not known to be in ${\sf 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.
