  We refine existing general network optimization techniques, give new
characterizations for the class of problems to which they can be applied, and
show that they can also be used to solve various two-player games in almost
linear time. Among these is a new variant of the network interdiction problem,
where the interdictor wants to destroy high-capacity paths from the source to
the destination using a vertex-wise limited budget of arc removals. We also
show that replacing the limit average in mean payoff games by the maximum
weight results in a class of games amenable to these techniques.
