Maximum cuts for a minimum flow

Abstract

In this paper, we resolve the following three problems. Given a minimum flow f in a network G = (N, A, l, u) determines: (1) the maximum cut [S, S̄] with the property that for every other maximum cut [X, X̄], S ⊆ X; (2) the maximum cut [T, T̄] with the property that for every other maximum cut [X, X̄ ], X ⊆ T, (3) whether the network G has a unique maximum cut.