
Suppose that a minimum cost flow problem cost vector c and capacity vector u is solved optimally, and the optimal solution is x*. Suppose further that the optimal set of node potentials is y*. a) If the capacity of one of the arcs is increased by 1, show how to find the new optimal solution (x and y vector) by solving a shortest path problem. Clearly state the shortest path problem, and how to modify the solution as a result of the shortest path found. b) Suppose instead of the change in part a), the cost of one of the arcs is increased by 1. Show how to find the new optimal solution (x and y vector) by solving a max flow problem. Clearly state the max flow problem, and how to modify the solution as a result of it. 