Minimax inverse problems of minimum cuts

Let G = (N, A) be a directed graph of n nodes and m arcs with an upper bound u ∈ ℤ^A. Given an s − t cut S⁰, the minimax inverse minimum-cut problem (MIMC) is to find a modified upper bound ũ ∈ ℝ^A such that S⁰ is a minimum cut for ũ and max {|uij − ũij‖(i,j) ∈ A} is minimum. This paper shows that the MIMC is closely related to the maximum mean-cut problem. By applying a parametric search for maximum mean-cut problems, the MIMC can be solved as a sequence of O(n) minimum s − t cut problems or in O(min {n^2/3,m^1/2}m log (n²/m) log n log (nU)) time, where U is the maximum value of u.