Capacity inverse minimum cost flow problem

Given a directed graph G = (N, A) with arc capacities u(ij) and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector (u) over cap for the arc set A such that a given feasible flow (x) over cap is optimal with respect to the modified capacities. Among all capacity vectors (u) over cap satisfying this condition, we would like to find one with minimum parallel to(u) over cap - u parallel to value. We consider two distance measures for parallel to(u) over cap - u parallel to, rectilinear (L-1) and Chebyshev (L-infinity) distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP-hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm. In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs. We also present computational results for this heuristic.