In this problem, we consider a variant of the minimum-cost-flow problem from Section 29.2 in which we are not given a demand, a source, or a sink. Instead, we are given, as before, a flow network and edge costs a(u,v)a(u, v) flow is feasible if it satisfies the capacity constraint on every edge and flow conservation at every vertex. The goal is to find, among all feasible flows, the one of minimum cost. We call this problem the minimum-cost-circulation problem.

a. Formulate the minimum-cost-circulation problem as a linear program.

b. Suppose that for all edges (u,v)E(u, v) \in E, we have a(u,v)>0a(u, v) > 0. Characterize an optimal solution to the minimum-cost-circulation problem.

c. Formulate the maximum-flow problem as a minimum-cost-circulation problem linear program. That is given a maximum-flow problem instance G=(V,E)G = (V, E) with source ss, sink tt and edge capacities cc, create a minimum-cost-circulation problem by giving a (possibly different) network G=(V,E)G' = (V', E') with edge capacities cc' and edge costs aa' such that you can discern a solution to the maximum-flow problem from a solution to the minimum-cost-circulation problem.

d. Formulate the single-source shortest-path problem as a minimum-cost-circulation problem linear program.

a. This is exactly the linear program given in equations (29.51)\text{(29.51)}-(29.52)\text{(29.52)} except that the equation on the third line of the constraints should be removed, and for the equation on the second line of the constraints, uu should be selected from all of VV instead of from V\{s,t}V \backslash \{s, t\}.

b. If a(u,v)>0a(u, v) > 0 for every pair of vertices, then, there is no point in sending any flow at all. So, an optimal solution is just to have no flow. This obviously satisfies the capacity constraints, it also satisfies the conservation constraints because the flow into and out of each vertex is zero.

c. We assume that the edge (t,s)(t, s) is not in EE because that would be a silly edge to have for a maximum flow from ss to tt. If it is there, remove it and it won't decrease the maximum flow. Let V=VV' = V and E=E{(t,s)}E' = E \cup \{(t, s)\}. For the edges of EE' that are in EE, let the capacity be as it is in EE and let the cost be 00. For the other edge, we set c(t,s)=c(t, s) = \infty and a(t,s)=1a(t, s) = -1. Then, if we have any circulation in GG', it will be trying to get as much flow to go across the edge (t,s)(t, s) in order to drive the objective function lower, the other flows will have no affect on the objective function. Then, by Kirchhoff's current law (a.k.a. common sense), the amount going across the edge (t,s)(t, s) is the same as the total flow in the rest of the network from ss to tt. This means that maximizing the flow across the edge (t,s)(t, s) is also maximizing the flow from ss to tt. So, all we need to do to recover the maximum flow for the original network is to keep the same flow values, but throw away the edge (t,s)(t, s).

d. Suppose that ss is the vertex that we are computing shortest distance from. Then, we make the circulation network by first starting with the original graph, giving each edge a cost of whatever it was before and infinite capacity. Then, we place an edge going from every vertex that isn't ss to ss that has a capacity of 11 and a cost of E-|E| times the largest cost appearing among all the edge costs already in the graph. Giving it such a negative cost ensures that placing other flow through the network in order to get a unit of flow across it will cause the total cost to decrease. Then, to recover the shortest path for any vertex, start at that vertex and then go to any vertex that is sending a unit of flow to it. Repeat this until you've reached ss.