The Art Gallery Guardian

Network Transformations and Applications


There are so many variations of what minimum cost flow means. Sometimes an algorithm might state it only works if the costs are all positive. Here are some of the transforms, many are just from section 2.4 of [1].

In the most general formulation of the minimum cost flow problem

  1. Each vertex has a balance constraint.
  2. Each edge has lower bound(demand) and upper bound(capacity).

A flow is feasible if it’s within lower bound and upper bound and balance constraint must be satisfied at all vertices.

Min-cost flow problem finds the flow with minimum cost. Min-cost circulation is the min-cost flow problem with all balance 00. Min-cost transshipment is the min-cost flow problem with no edge capacities. (But there is a lower bound of 00 on all edges).

1 Remove all balance

This shows min-cost flow is equivalent to min-cost circulation. A common way to remove balance is add an new vertex ss. For each vertex vv with balance bvb_v, add edge svsv with lower and upper bound both bv-b_v.

However, this might make the graph no longer have certain structural properties. For example, the graph might no longer be planar.

One way to do this is solve two problems. First compute a spanning tree TT of the graph. Add parallel edges from TT to GG. Find flow only on those parallel edges(so it’s just a tree) that satisfies all the balance constraints. Let this flow be ff. Make sure the cost of the flow on the added edges are infinity, and consider the residue graph. Now, solve the min-cost circulation on the residual graph and then sum with the flow ff gives one the desired result. This idea was first used for max flow problem with balance constraints in [2].

2 Remove upper and lower bounds

This shows min-cost flow is equivalent to min-cost transshipment problem. All operations are local, therefore we establish the notation. There is an edge stst with lower bound ll, upper bound uu, cost cc. bsb_s and btb_t are the balances of ss and tt, respectively.

2.1 Remove non-zero lower bound

The idea is we just send the flow of value ll along the edge! We transform so the new balance for ss is bslb_s - l, new balance for tt is bt+lb_t+l, and the new upper bound on the edge is ulu-l. The low The cost doesn’t change.

2.2 Remove upper bounds

Here we assume l=0l=0. If not, first remove the non-zero lower bound. We create a new node ww with balance u-u. We remove the edge stst, and split it into swsw and twtw instead. swsw has infinite capacity and cost cc. twtw has infinite capacity and cost 00. Finally, let the balance of tt be bt+ub_t+u.

The idea is instead of sending flow on stst, now we send on swsw. Because the balance is u-u, we can’t send more than uu unit of flow. To cover the remaining balance, some flow is sent from tt to ww.

3 Applications

Let CC be a class of graphs. Let Sub(C)={GGH,HC}Sub(C)=\{G| G\subset H, H\in C\} be the set of subgraphs of graphs in class CC. If there is an algorithm that solves min-cost circulation/transshipment problem for CC, then there is an algorithm that solves min-cost flow problem on Sub(C)Sub(C). The running time of the algorithm is only the extra time spent on complete the graph to some graph in CC by adding edges of 00 capacity.

This directly implies min-cost flow on general series-parallel graphs can be solved in O(nlogn)O(n\log n) time using the algorithm for min-cost circulation on 22-terminal series-parallel graphs(Note the article solves the min-cost maximum flow problem, one can see it also works for min-cost circulation)[3]. As a corollary, one can solve min-cost flow problem on outerplanar graph in the same running time.

References

[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows: Theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.

[2] G.L. Miller, Flow in planar graphs with multiple sources and sinks, SIAM J. Comput. 24 (1995) 1002–1017 10.1137/S0097539789162997.

[3] H. Booth, R.E. Tarjan, Finding the minimum-cost maximum flow in a series-parallel network, Journal of Algorithms. 15 (1993) 416–446 10.1006/jagm.1993.1048.

Posted by Chao Xu on .
Tags: Algorithm.