What a Flow-Cut Certificate Shows
A maximum-flow calculation has two different tasks: find a flow with a large value, and show that no feasible flow can do better. A minimum-cut calculation also has two tasks: find a cut with small capacity, and show that no cut can have smaller capacity. A single pair of objects can settle both questions. If a feasible flow and an \(s\)-\(t\) cut have the same value, then the flow is maximum and the cut is minimum.
Here a network is a finite directed graph with distinct source \(s\) and sink \(t\), and a nonnegative capacity \(c(e)\) on each arc \(e\). Arcs in opposite directions, when present, are distinct arcs. A flow \(f\) assigns a number \(f(e)\) to each arc, with \(0\le f(e)\le c(e)\). At every vertex other than \(s\) and \(t\), total inflow equals total outflow. The flow value \(|f|\) is the net flow out of \(s\): flow on arcs leaving \(s\) minus flow on arcs entering \(s\).
A flow is maximum if no feasible flow has greater value. A cut is minimum if no \(s\)-\(t\) cut has smaller capacity. To certify optimality, we will compare the value of one feasible flow with the capacity of one cut. First, we derive the bound that makes this comparison work.
The Flow-Cut Bound
Proof. Sum, over the vertices in \(S\), the net outflow at each vertex. At every vertex of \(S\) except \(s\), conservation makes this net outflow zero. The source contributes \(|f|\), so the sum is \(|f|\). Each arc with both endpoints in \(S\) contributes once as outflow and once as inflow, and therefore cancels. Arcs with both endpoints outside \(S\) contribute nothing. An arc directed from \(S\) to \(\overline{S}\) contributes its flow positively; an arc directed from \(\overline{S}\) to \(S\) contributes its flow negatively. Thus \[ |f|=\sum_{e:S\to\overline{S}} f(e)-\sum_{e:\overline{S}\to S} f(e). \] \(\square\)
Proof. In the flow-cut identity, every flow on an arc from \(\overline{S}\) to \(S\) is nonnegative, so subtracting the sum of those flows cannot increase the expression. Also, for each arc from \(S\) to \(\overline{S}\), feasibility gives \(f(e)\le c(e)\). Therefore \[ |f| \le \sum_{e:S\to\overline{S}} f(e) \le \sum_{e:S\to\overline{S}} c(e) = c(S,\overline{S}). \] \(\square\)
The inequalities also describe what equality requires. Subtracting the flow value from the cut capacity gives \[ c(S,\overline{S})-|f| =\sum_{e:S\to\overline{S}}\bigl(c(e)-f(e)\bigr) +\sum_{e:\overline{S}\to S} f(e). \] Every term on the right is nonnegative. Thus equality holds precisely when every arc from \(S\) to \(\overline{S}\) is saturated and every arc from \(\overline{S}\) to \(S\) carries zero flow. This gives a useful additional check on a certificate.
Proof. Let \(g\) be any feasible flow. By weak duality applied to \(g\) and the given cut, \(|g|\le c(S,\overline{S})=|f|\). Hence no feasible flow has value greater than \(f\), so \(f\) is maximum. Now let \((R,\overline{R})\) be any \(s\)-\(t\) cut. Applying weak duality to \(f\) and this cut gives \(|f|\le c(R,\overline{R})\). Since \(|f|=c(S,\overline{S})\), no cut has capacity smaller than the given cut. Thus it is minimum. \(\square\)
This is a certificate, not necessarily a method for finding the flow or cut. It lets a reader verify optimality from the proposed objects alone: check that the flow is feasible, check that the set defines an \(s\)-\(t\) cut, and compare the two computed values.
Worked Flow-Cut Certificates
Worked Example: Two Disjoint Routes
Consider the directed network with \(V=\{s,a,b,t\}\) and arcs \(s\to a\) of capacity \(3\), \(s\to b\) of capacity \(2\), \(a\to t\) of capacity \(3\), \(b\to t\) of capacity \(2\), and \(a\to b\) of capacity \(1\). Assign flow \(3\) to \(s\to a\) and \(a\to t\), flow \(2\) to \(s\to b\) and \(b\to t\), and flow \(0\) to \(a\to b\).
| Arc | Capacity | Flow |
|---|---|---|
| \(s\to a\) | 3 | 3 |
| \(s\to b\) | 2 | 2 |
| \(a\to t\) | 3 | 3 |
| \(b\to t\) | 2 | 2 |
| \(a\to b\) | 1 | 0 |
Each flow is nonnegative and within its capacity: the listed comparisons are \(0\le3\le3\), \(0\le2\le2\), \(0\le3\le3\), \(0\le2\le2\), and \(0\le0\le1\). At \(a\), inflow is \(3\) and outflow is \(3+0=3\). At \(b\), inflow is \(2+0=2\) and outflow is \(2\). Thus conservation holds. The value is the net flow out of \(s\), \(3+2=5\).
Take \(S=\{s,a,b\}\), so \(\overline{S}=\{t\}\). The only arcs directed from \(S\) to \(\overline{S}\) are \(a\to t\) and \(b\to t\). The cut capacity is \(3+2=5\), equal to the flow value. The flow is therefore maximum and the cut is minimum.
Check: the cut arcs carry flows \(3\) and \(2\), which equal their capacities \(3\) and \(2\). There are no arcs directed from \(t\) into \(S\), so the equality conditions from the flow-cut identity are satisfied.
Worked Example: A Route That Uses an Internal Arc
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a\) of capacity \(5\), \(s\to b\) of capacity \(2\), \(a\to b\) of capacity \(2\), \(a\to t\) of capacity \(3\), and \(b\to t\) of capacity \(4\). Assign flows \(5,2,2,3,4\), respectively, in the same order as the arcs just listed.
The capacity checks are \(0\le5\le5\), \(0\le2\le2\), \(0\le2\le2\), \(0\le3\le3\), and \(0\le4\le4\). At \(a\), inflow is \(5\), while outflow is \(2+3=5\). At \(b\), inflow is \(2+2=4\), while outflow is \(4\). Hence the assignment is a feasible flow. Its value is \(5+2=7\), the net flow out of \(s\).
Choose \(S=\{s,a\}\) and \(\overline{S}=\{b,t\}\). The arcs directed across the cut are \(s\to b\), \(a\to b\), and \(a\to t\), with capacities \(2\), \(2\), and \(3\). Therefore \[ c(S,\overline{S})=2+2+3=7. \] The internal arc \(s\to a\) does not cross the cut, and \(b\to t\) lies wholly in \(\overline{S}\); neither contributes to this cut capacity. Since the capacity \(7\) equals the feasible flow value \(7\), both objects are optimal.
Check: the flow across the cut is \(2+2+3=7\). Each of these three arcs is saturated, and there is no arc directed from \(\overline{S}\) to \(S\), consistent with equality.
Worked Example: An Arc Directed Back Across the Cut
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a\) of capacity \(4\), \(s\to b\) of capacity \(2\), \(a\to t\) of capacity \(3\), \(a\to b\) of capacity \(1\), \(b\to t\) of capacity \(3\), and \(b\to a\) of capacity \(1\). Assign flows \(4,2,3,1,3,0\), respectively.
For the six arcs in order, the capacity checks are \(0\le4\le4\), \(0\le2\le2\), \(0\le3\le3\), \(0\le1\le1\), \(0\le3\le3\), and \(0\le0\le1\). At \(a\), inflow is \(4+0=4\) and outflow is \(3+1=4\). At \(b\), inflow is \(2+1=3\) and outflow is \(3+0=3\). The assignment is feasible, and its value is \(4+2=6\).
Use \(S=\{s,a\}\) and \(\overline{S}=\{b,t\}\). The arcs directed from \(S\) to \(\overline{S}\) are \(s\to b\), \(a\to b\), and \(a\to t\). Their capacities add to \(2+1+3=6\). The arc \(b\to a\) points in the opposite direction, so it is not part of the cut capacity. Its flow is \(0\), as the equality condition requires. The flow value and cut capacity agree at \(6\), certifying both as optimal.
Check: across the cut, the flow from \(S\) to \(\overline{S}\) is \(2+1+3=6\), and the reverse-direction flow is \(0\). The flow-cut identity gives \(6-0=6\), agreeing with the cut capacity.
How to Check a Proposed Certificate
List the vertices, directed arcs, capacities, source and sink. Treat opposite directions as separate arcs.
For every arc, check \(0\le f(e)\le c(e)\). At every vertex other than \(s\) and \(t\), add the incoming and outgoing flows and check that they agree.
Subtract the total flow into \(s\) from the total flow out of \(s\). Do not count only outgoing flow if the network has arcs entering \(s\).
Check that \(s\in S\) and \(t\notin S\), then add capacities only for arcs directed from \(S\) to \(\overline{S}\).
If the two values agree, weak duality proves both are optimal. If they do not agree, this pair does not certify optimality.
Common Pitfall: Counting the Wrong Arcs
A cut is directed: its capacity is not the sum of capacities of every arc with endpoints on different sides. In the third example, the arc \(b\to a\) crosses between the two vertex sets but points from \(\overline{S}\) into \(S\). Including its capacity would give the incorrect total \(2+1+3+1=7\). The correct capacity is \(2+1+3=6\), because only \(s\to b\), \(a\to b\), and \(a\to t\) point from \(S\) to \(\overline{S}\).
A second common error is to treat any feasible flow and any cut as a certificate. Weak duality only gives \(|f|\le c(S,\overline{S})\). If the inequality is strict, it is a valid bound but does not by itself prove either object optimal. Equality is the decisive condition: it closes the gap between the feasible value and the upper bound.
Check Your Understanding
For each question, distinguish the feasibility checks from the equality needed for an optimality certificate.
- For a feasible flow of value \(8\) and a cut of capacity \(8\), what two optimality conclusions follow, and why?
- Why are arcs directed from \(\overline{S}\) into \(S\) absent from the definition of cut capacity?
- Suppose a cut has capacity \(9\) and a feasible flow has value \(7\). What can weak duality tell you, and what does this pair fail to certify?
- In a proposed certificate, what must be checked at a vertex other than the source and sink?
- Use the equality expression \(c(S,\overline{S})-|f|\) to state the conditions on forward and reverse crossing arcs when the flow value equals the cut capacity.