Inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow x0, an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x0 form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n · m2).