I feel like I can never remember what min-cost circulation (MCC) is, or what the basic facts about it are. So here is a short blog post where I remind myself of what MCC is.

Based on some scribed notes for Karger’s Advanced Algorithms course

Definition. Let \(G\) be a graph, where each edge \(e\) has a capacity \(u(e)\ge 0\) and a cost \(c(e)\in \mathbb{R}\). Identify source and sink vertices \(s,t\) in \(G\).

A min-cost max-flow is a flow on \(G\) of minimum cost. That is, it is an assignment of values \(f(e) \in [0, u(e)]\) subject to “conservation of flow” at all but the source and sink vertices, i.e., so that \(\sum_{u\to v}f(u\to v) - \sum_{w\to u} f(w\to u) = 0\) for all vertices \(u\notin \left\{ s,t\right\}\), which minimizes \[\sum_e f(e) c(e).\]

Remark. flow can be decomposed into paths and cycles.

Definition. Min-cost circulation: again you have a capacitated graph with edge costs. The only difference is that there is no source / sink. The goal is to choose a flow, called a circulation in this context that of course satisfies the capacities and conservation of flow, which makes the cost of the flow minimized.

Theorem. Algorithms for min-cost max-flow and algorithms for min-cost circulation are easily interchangable.

Proof.

Given a min-cost circulation instance you can add a dummy source and sink vertex not connected to anything to obtain a min-cost max-flow instance.

Here are two ways to turn a min-cost max-flow instance into a min-cost circulation instance:

  1. Add an edge \(t\to s\) with \(\infty\) capacity and \(-\infty\) cost.
  2. Find an arbitrary \(s,t\) max-flow, and then find a min-cost circulation in the residual graph.

Theorem. A circulation is a minimum-cost circulation iff the residual graph has no negative cycles.

Proof. If residual graph has negative cycle you can augment to obtain lower cost.

If we have a sub-optimal circulation, then consider the difference between our sub-optimal circulation and an optimal circulation. It is a circulation with a negative-weight cycle.

So you could do Bellman Ford.

Theorem. Some super crazy algorithm can solve MCC in \(O(m^{1+o(1)})\) ish.

Definition. Price functions are maybe good for more elementary algorithms for computing the min-cost circulation.

A feasible price function is \(p: V\to \mathbb{R}\) with

  • \(p(s) = 0\),
  • For each edge \(v\to w\) we have \(p(w) \ge p(v)+c(v\to w)\)

Reduced cost: \(c(v\to w) +p(v)-p(w)\). It’s like you pay \(p(v)\) dollars to pick up the item, and earn \(p(w)\) for delivering it, and pay \(c(v\to w)\) for travelling. If reduced cost is negative there is economic incentive to move flow around.

So, a price function is feasible for a residual graph if no residual edge has negative reduced cost.

Observation: the min-cost circulation in the graph of reduced costs is the same as in the actual graph: because when you add the reduced costs in a cycle it is the same as if you add the real costs in a cycle.

Theorem. Circulation is optimal iff feasible price function in residual graph.

Proof. If feasible price function then no negative weights, and in particular no negative cost cycles in residual graph. Discussed earlier this is sufficient condition.

If circulation is minimum cost then we assign prices as follows: add a vertex \(s\) with cost \(0\) edges to all other vertices. Compute the prices as the distance from \(s\). This graph has no negative cost cycles due to being optimal so the distances will all be finite. It is clear that distances satisfy the feasibility condition.