Some Generalized Max-Flow Min-Cut Problems in the Plane

Abstract

We consider 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. Our 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.