Some generalized max-flow min-cut problems in the plane

The paper considers variants of the max-flow min-cut problems in the plane, motivated by models of damage, where certain sets of edges of the graph can be simultaneously removed, rather than one edge at a time as in the standard min-cut problem. The main contributions are: a polynomial algorithm for the generalized min-cut problem, an NP-completeness result for the generalized max-flow problem, and an ‘approximate’ generalized max-flow min-cut theorem.