Why Decompose a Flow?
A flow is specified by a number on every directed arc, subject to capacity limits and conservation at intermediate vertices. A decomposition gives those numbers a more concrete interpretation: the flow can be accounted for by units sent along directed paths, together with units circulating around directed cycles. The paths determine the net flow value; the cycles do not. This distinction is useful when checking what a flow accomplishes and when reasoning about flow algorithms.
We work with a finite directed network with distinct source \(s\) and sink \(t\), arc set \(A\), and nonnegative capacities \(c(a)\) for \(a\in A\). Oppositely directed arcs, if present, are treated as distinct arcs. A feasible flow \(f\) satisfies \(0\le f(a)\le c(a)\) on every arc. At each vertex other than \(s,t\), the total flow entering equals the total flow leaving. The value is the net flow leaving the source: outgoing flow from \(s\) minus incoming flow to \(s\). A directed path has no repeated vertices; a directed cycle is a closed directed walk with no repeated vertices other than its first and last.
In particular, a flow value need not be positive. If arcs entering the source carry more flow than arcs leaving it, then \(|f|<0\). The decomposition statement must allow paths in either terminal direction to cover this case.
These path and cycle flows are used as algebraic pieces of a given flow. A piece need not, by itself, satisfy the capacity constraints of the network when added to other pieces; the relevant claim is that their sum equals the feasible flow on every arc.
The Decomposition Theorem
- If \(|f|>0\), the path flows are on directed \(s\)-to-\(t\) paths, and their weights sum to \(|f|\).
- If \(|f|<0\), the path flows are on directed \(t\)-to-\(s\) paths, and their weights sum to \(-|f|\).
- If \(|f|=0\), there are no path-flow terms; the flow is a sum of directed cycle flows.
The theorem does not say that a decomposition is unique. Different choices of paths or cycles can give different decompositions of the same arc values. We prove existence by repeatedly subtracting a path flow and then decomposing what remains into cycles.
Proof. Let \(S\) be the set of vertices reachable from \(s\) by directed paths using only arcs \(a\) with \(g(a)>0\). If \(t\notin S\), no positive-flow arc leaves \(S\), since its head would also be reachable. Summing the net outflow over vertices in \(S\) cancels the contributions of arcs internal to \(S\). All vertices in \(S\) other than \(s\) satisfy conservation, and \(t\notin S\), so the sum equals \(|g|\). Thus \[ |g|=\sum_{\substack{a\text{ leaves }S}}g(a) -\sum_{\substack{a\text{ enters }S}}g(a). \] The first sum is zero, and the second is nonnegative, so \(|g|\le0\), contradicting \(|g|>0\). Therefore \(t\in S\). A positive-flow directed walk from \(s\) to \(t\) can be shortened to a path by deleting segments between repeated vertices; all remaining arcs still have positive flow. \(\square\)
Proof of the theorem. First suppose \(|f|>0\). As long as the current flow has positive value, the Lemma supplies a directed \(s\)-to-\(t\) path all of whose arcs have positive current flow. Let \(w\) be the smaller of the current value and the minimum flow on the arcs of that path. Subtract the path flow of weight \(w\). Each path arc remains nonnegative; no other arc changes. At an internal path vertex, one entering and one leaving arc have both been reduced by \(w\), so conservation remains true. The value decreases by exactly \(w\), since the path leaves \(s\) once and enters \(t\) once. If the value does not yet reach zero, \(w\) is the minimum flow on a path arc, so at least one arc becomes zero. No later subtraction can make a zero arc positive. There are finitely many arcs, so after finitely many such steps the remaining value is zero. The extracted path weights sum to the original value because each subtraction reduced it by exactly the weight extracted.
Call the remaining flow \(h\). It is nonnegative and has value zero. It satisfies conservation at \(s\) as well as at every other vertex: the net outflow at \(s\) is zero. Since the sum of net outflows over all vertices is zero (each arc contributes once positively and once negatively), the net outflow at \(t\) is also zero. Thus \(h\) is a circulation: it satisfies conservation at every vertex.
If a circulation has any positive-flow arc, follow that arc and continue from its head along a positive-flow outgoing arc. Such an outgoing arc always exists: positive incoming flow at a vertex, together with conservation, requires positive outgoing flow. Because the network has finitely many vertices, this walk repeats a vertex. The segment between repetitions contains a directed cycle; by choosing the first repetition, we obtain a cycle with no repeated internal vertices. Subtract the minimum flow on its arcs from every arc of that cycle. This preserves nonnegativity and conservation, and makes at least one positive arc zero. Repeating must stop after finitely many steps, leaving no positive-flow arcs. The circulation has therefore been written as a finite sum of cycle flows. Together with the path flows already extracted, these terms sum to \(f\) arc by arc.
If \(|f|<0\), reverse the roles of \(s\) and \(t\) in the path-extraction argument: equivalently, apply the positive-value argument with source \(t\) and sink \(s\). The value measured from \(t\) is \(-|f|>0\). It yields \(t\)-to-\(s\) path flows whose weights sum to \(-|f|\), followed by cycle flows. If \(|f|=0\), the circulation argument applies immediately and gives only cycle flows. This proves all three cases. \(\square\)
Reading the Value from a Decomposition
A path flow of weight \(w\) on an \(s\)-to-\(t\) path contributes \(w\) to the flow value; a path flow of weight \(w\) on a \(t\)-to-\(s\) path contributes \(-w\). A cycle flow contributes zero, because every vertex on the cycle has equal incoming and outgoing cycle flow. Thus, in each case of the theorem, the sum of the correctly oriented path weights gives the magnitude of the flow value, and the cycle terms affect arc values but not the value.
Worked Example: Extracting Paths and a Cycle
Let the directed network have vertices \(V=\{s,a,b,t\}\) and arcs \(A=\{s\to a,a\to t,s\to b,b\to t,a\to b,b\to a\}\). Give these arcs capacities \(c(s\to a)=4\), \(c(a\to t)=2\), \(c(s\to b)=3\), \(c(b\to t)=5\), \(c(a\to b)=3\), and \(c(b\to a)=1\). Consider the flow values \(f(s\to a)=4\), \(f(a\to t)=2\), \(f(s\to b)=3\), \(f(b\to t)=5\), \(f(a\to b)=3\), and \(f(b\to a)=1\). These values are within capacity. At \(a\), inflow is \(4+1=5\) and outflow is \(2+3=5\); at \(b\), inflow is \(3+3=6\) and outflow is \(5+1=6\). The source value is \(4+3=7\).
Extract \(s\to a\to t\) first. Its weight is the minimum of the arc flows \(4,2\) and the current value \(7\), namely \(2\). The remaining arc flows, in the order \(s\to a,a\to t,s\to b,b\to t,a\to b,b\to a\), are \((2,0,3,5,3,1)\), and the remaining value is \(7-2=5\).
Next use \(s\to a\to b\to t\). The minimum of its arc flows \(2,3,5\) and the current value \(5\) is \(2\). The remaining arc flows are now \((0,0,3,3,1,1)\), and the remaining value is \(5-2=3\). Then use \(s\to b\to t\) with weight \(\min(3,3,3)=3\). The remaining value is \(3-3=0\), and the only positive arcs left are \(a\to b\) and \(b\to a\), each with flow \(1\). They form a directed cycle, so the remaining flow is a cycle flow of weight \(1\) on \(a\to b\to a\).
Check: On the six arcs in the stated order, the decomposition gives \(2+2=4\), \(2\), \(3\), \(2+3=5\), \(2+1=3\), and \(1\), respectively. These equal the original arc flows. The path weights total \(2+2+3=7\), matching the source value \(4+3=7\); the cycle contributes zero to that value.
Worked Example: A Negative Flow Value
Let \(V=\{s,t,a,b\}\) and \(A=\{t\to a,a\to s,a\to b,b\to a\}\). Set capacities equal to the listed flows: \(f(t\to a)=2\), \(f(a\to s)=2\), \(f(a\to b)=1\), and \(f(b\to a)=1\). At \(a\), inflow is \(2+1=3\) and outflow is \(2+1=3\); at \(b\), inflow and outflow are both \(1\). The source has no outgoing flow and has incoming flow \(2\), so \(|f|=0-2=-2\).
The path \(t\to a\to s\) with weight \(2\) accounts for the two arcs \(t\to a\) and \(a\to s\). The cycle \(a\to b\to a\) with weight \(1\) accounts for the other two arcs. Thus this decomposition uses a \(t\)-to-\(s\) path, not an \(s\)-to-\(t\) path. Its path weight is \(2=-|f|\), as required in the negative-value case.
Check: The reconstructed arc flows are \(2,2,1,1\), in the order \(t\to a,a\to s,a\to b,b\to a\). The path contributes \(-2\) to the value measured at \(s\), while the cycle contributes \(0\), giving \(|f|=-2\).
Worked Example: Decomposing a Zero-Value Circulation
Let \(V=\{s,t,p,q,r\}\), with \(s,t\) isolated, and arcs \(p\to q,q\to p,q\to r,r\to p\). Set capacities and flows to \(f(p\to q)=3\), \(f(q\to p)=1\), \(f(q\to r)=2\), and \(f(r\to p)=2\). At \(p\), inflow is \(1+2=3\) and outflow is \(3\); at \(q\), inflow is \(3\) and outflow is \(1+2=3\); at \(r\), inflow and outflow are both \(2\). Since no arc meets \(s\), the value is \(0\).
One cycle is \(p\to q\to p\), with weight \(\min(3,1)=1\). Subtracting it leaves \(p\to q\) with flow \(2\), \(q\to r\) with flow \(2\), and \(r\to p\) with flow \(2\); the arc \(q\to p\) now has flow \(0\). These remaining arcs form the cycle \(p\to q\to r\to p\) with weight \(2\).
Check: The two cycle flows reconstruct \(p\to q\) as \(1+2=3\), \(q\to p\) as \(1\), \(q\to r\) as \(2\), and \(r\to p\) as \(2\). There are no terminal paths, so the value remains \(0\).
What Decomposition Does—and Does Not—Say
The path terms record net transport between the terminals, while cycle terms record flow that circulates. A circulation can be present even when the flow value is zero, as the example shows. Conversely, a positive flow value does not mean every arc flow belongs to a source-to-sink path without any cycle terms: in the first example, the cycle is needed to account for the flow on both \(a\to b\) and \(b\to a\).
A common mistake is to equate flow value with the sum of all flow leaving the source, without subtracting flow entering it. The formula is net outflow. In the negative-value example, the source has outgoing flow \(0\) and incoming flow \(2\), so the value is \(0-2=-2\), not \(0\). A related mistake is to define path flows only for \(s\)-to-\(t\) paths and then claim the same decomposition for negative values. The \(t\)-to-\(s\) path in that example shows why the definition must allow a directed path in either direction.
When checking any proposed decomposition, verify both parts of the claim: each arc’s original flow must equal the sum of the weights of the terms using that arc, and the terminal path directions and weights must agree with the stated flow value. Checking only the value can miss a cycle; checking only a few arcs can miss a flow that has been assigned to the wrong direction.
Check Your Understanding
For each question, state the relevant path directions and check any numerical claims against the arc flows.
- Why does subtracting a weighted \(s\)-to-\(t\) path reduce a positive flow’s value by exactly the path weight?
- A feasible flow has value \(0\). What conservation property does it satisfy at \(s\) and \(t\), and what types of terms suffice in its decomposition?
- Explain why the positive-flow arcs must contain an \(s\)-to-\(t\) path when the current flow value is positive.
- Can a cycle flow change the net flow value at \(s\)? Justify your answer using the incoming and outgoing arcs of the cycle.
- Suppose a flow has value \(-5\). What direction must the terminal path flows have in the theorem, and what must their weights sum to?