Given a network N = (V,A,c), a source s ∈ V, a sink t ∈ V and some s – t cuts and suppose each element of the capacity vector c can be changed with a cost proportional to the changes, the inverse problem of minimum cuts we study here is to change the original capacities with the least total cost under restrictions on the changes of the capacities, so that all those s – t cuts become minimum cuts with respect to the new capacities. In this paper we shall show that the inverse problem of minimum cuts can be directly transformed into a minimum cost circulation problem and therefore can be solved efficiently by strongly polynomial algorithms.
