Inverse problem of minimum cuts

Given a networkN = (V,A,c), a sources V, a. sinkt V and somes —t cuts and suppose each element of the capacity vectorc 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 thoses —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.The author is grateful to the partial support of the Universities Grant Council of Hong Kong under the grant CITYU #9040189Work partially supported by the National Natural Science Foundation of China