6.2. Decomposing Flows*

This section introduces a useful tool we will use in analyzing some of the algorithms in this chapter.

So far, we have viewed a flow as a collection of individual flow amounts sent along the edges of the graph, as a function \(f: E \rightarrow \mathbb{R}\). This function cannot be completely arbitrary. To be a flow, it needs to satisfy the capacity and flow conservation constraints. If you think back to augmenting path algorithms, we did not construct a maximum flow one edge at a time. Instead, we chose a set of paths from \(s\) to \(t\) and an amount of flow to be sent along each path. The final flow was then the sum of these "path flows".

When computing minimum-cost flows, we no longer have a single source or a single sink. Instead, we have supply vertices and demand vertices and, as we show in this section, we can once again obtain a feasible flow as the sum of a collection of path flows from supply vertices to demand vertices. The total flow along all paths starting at each supply vertex must match its supply. The total flow along all paths ending at a demand vertex must match its demand. Since we want to compute a minimum-cost flow, there is an added twist. Once we have found a feasible flow that routes flow along paths from supply vertices to demand vertices, we may be able to reduce its cost by sending some flow from a vertex back to itself along a negative-cost cycle. This does not alter the supply balance at any vertex, but it reduces the cost of the flow. Thus, in general, every flow can be decomposed into a collection of paths and cycles. The remainder of this section proves this formally.

• In Section 6.2.1, we introduce the concepts of circulations, cycle flows, and path flows.

• In Section 6.2.2, we prove that every pseudo-flow can be represented as the sum of a bounded number of path and cycle flows.

• Section 6.2.3 explores the relationship between pseudo-flows, flows, and circulations in their residual networks.