Robust partial inverse network flow problems

In this paper, a new model for inverse network flow problems, the robust partial inverse problem, is presented. For a given partial solution, the robust partial inverse problem is to modify the coefficients optimally such that all full solutions containing the partial solution become optimal with the new coefficients. It has been shown that the robust partial inverse spanning tree problem can be formulated as a combinatorial linear program, while the robust partial inverse minimum cut problem and the robust partial inverse assignment problem can be solved by combinatorial strongly polynomial algorithms.