What Makes a Flow Feasible?
A capacity-constrained network assigns a limit to each directed arc. A proposed flow is not feasible merely because its numbers seem to travel from a source toward a sink: every arc must respect its own capacity, and every vertex other than the designated terminals must pass on exactly what it receives. These are separate tests. A capacity violation can occur even when all the conservation equations hold, and a conservation failure can occur even when every arc stays within its capacity.
Throughout, a network is a finite directed graph \(G=(V,E)\) with distinct designated vertices \(s\) and \(t\), called the source and sink. Each arc \(e\in E\) has a specified nonnegative capacity \(c(e)\). We consider networks without loops or multiple arcs. For a vertex \(v\), an arc is entering \(v\) if its head is \(v\), and leaving \(v\) if its tail is \(v\). The incoming and outgoing amounts must be summed separately: the direction of each arc matters.
- Capacity and nonnegativity: for every arc \(e\in E\), \(0\le f(e)\le c(e)\).
- Conservation: for every vertex \(v\in V\setminus\{s,t\}\), the total flow entering \(v\) equals the total flow leaving \(v\): $$ \sum_{\substack{e\in E\\\text{head}(e)=v}} f(e) = \sum_{\substack{e\in E\\\text{tail}(e)=v}} f(e). $$
The first condition applies to every arc, including arcs entering or leaving \(s\) and \(t\). The conservation equation applies only to vertices in \(V\setminus\{s,t\}\). In particular, these feasibility conditions do not impose conservation at either terminal. The special role of the terminals is not a reason to skip their incident arc-capacity checks.
A Systematic Feasibility Check
For a proposed assignment, check the constraints in two passes. First make a row for each arc and verify its lower and upper bounds. Then, for each nonterminal vertex, add the amounts on entering arcs and on leaving arcs and compare the totals. Writing the arc direction beside each amount helps prevent the common error of counting an entering arc as outgoing.
For each directed arc \(e\), record its proposed flow \(f(e)\) and capacity \(c(e)\), and test \(0\le f(e)\le c(e)\).
Exclude \(s\) and \(t\). For every remaining vertex, identify all entering and leaving arcs.
Add the entering flows and the leaving flows separately. The assignment is feasible exactly when every arc test and every nonterminal equation passes.
Proof. By definition, feasibility consists of the capacity and nonnegativity condition on every arc together with conservation at every vertex in \(V\setminus\{s,t\}\). If \(f\) is feasible, it therefore passes every listed test. Conversely, if it passes every listed test, it satisfies both defining conditions, so it is feasible. The tests impose no additional equation at \(s\) or \(t\), because neither is in \(V\setminus\{s,t\}\). \(\square\)
Worked Checks
Worked Example: Every Constraint Passes
Let \(V=\{s,a,b,t\}\), with directed arcs \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), and \(b\to t\). Give these arcs capacities \(5,4,2,3,6\), respectively. Consider the proposed flows \(4,3,1,3,4\), in the same order. Check feasibility.
Check each arc bound separately:
- On \(s\to a\), \(0\le 4\le 5\).
- On \(s\to b\), \(0\le 3\le 4\).
- On \(a\to b\), \(0\le 1\le 2\).
- On \(a\to t\), \(0\le 3\le 3\).
- On \(b\to t\), \(0\le 4\le 6\).
The nonterminals are \(a\) and \(b\). At \(a\), the only entering arc is \(s\to a\), so the entering total is \(4\). The leaving arcs are \(a\to b\) and \(a\to t\), with total \(1+3=4\). Thus conservation holds at \(a\). At \(b\), the entering total is \(3+1=4\), from \(s\to b\) and \(a\to b\); the leaving total is \(4\), from \(b\to t\). Conservation holds at \(b\).
Check: all five arc inequalities pass, and both nonterminal equations read \(4=4\). Hence the assignment is feasible. In particular, the flow \(3\) on \(a\to t\) equals that arc’s capacity, which is permitted because the upper bound is inclusive.
Worked Example: Conservation Does Not Fix an Over-Capacity Arc
Let \(V=\{s,u,v,t\}\), with directed arcs \(s\to u\), \(u\to v\), \(v\to t\), \(s\to v\), and \(u\to t\), having capacities \(4,2,4,1,3\), respectively. Assign flows \(3,3,3,0,0\), respectively.
At \(u\), the entering total is \(3\) on \(s\to u\), and the leaving total is \(3\) on \(u\to v\); the equation holds. At \(v\), the entering total is \(3+0=3\), from \(u\to v\) and \(s\to v\), and the leaving total is \(3\) on \(v\to t\); this equation also holds.
Now test all the capacity bounds. The flows on \(s\to u\), \(v\to t\), \(s\to v\), and \(u\to t\) satisfy \(0\le3\le4\), \(0\le3\le4\), \(0\le0\le1\), and \(0\le0\le3\). But on \(u\to v\), the required inequality would be \(0\le3\le2\), which is false because \(3>2\).
Check: both nonterminal balances hold, but one arc exceeds its capacity by \(3-2=1\). The assignment is therefore not feasible. Conservation equations cannot compensate for a failed capacity bound.
Worked Example: Capacity Bounds Do Not Fix a Balance Error
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a\), \(a\to b\), \(b\to t\), \(s\to b\), and \(a\to t\), having capacities \(4,3,4,2,2\), respectively. Assign flows \(3,1,2,1,1\), respectively.
Test the capacity constraints: the five comparisons are \(0\le3\le4\), \(0\le1\le3\), \(0\le2\le4\), \(0\le1\le2\), and \(0\le1\le2\). Every arc passes.
At \(a\), the entering total is \(3\), while the leaving total is \(1+1=2\). The conservation equation fails because \(3\ne2\). At \(b\), the entering total is \(1+1=2\), and the leaving total is \(2\), so conservation holds there.
Check: the only failed feasibility test is conservation at \(a\). The incoming amount exceeds the outgoing amount there by \(3-2=1\), so the assignment is not feasible even though no capacity is exceeded.
Feasible Assignments Can Be Combined
The constraints are linear: each capacity condition is an interval bound on one arc variable, and each conservation condition is an equality of sums. As a result, feasible assignments have a useful closure property. It gives a way to form another feasible assignment from two already checked ones, without repeating the argument separately at every vertex.
Proof. Let \(e\) be any arc. Since \(f\) and \(g\) are feasible, \(0\le f(e)\le c(e)\) and \(0\le g(e)\le c(e)\). The coefficients \(\theta\) and \(1-\theta\) are nonnegative and add to \(1\). Therefore $$ 0\le \theta f(e)+(1-\theta)g(e) \le \theta c(e)+(1-\theta)c(e)=c(e). $$ Thus \(h\) satisfies the capacity and nonnegativity bounds on every arc. Now let \(v\in V\setminus\{s,t\}\). The incoming sum for \(h\) is \(\theta\) times the incoming sum for \(f\), plus \(1-\theta\) times the incoming sum for \(g\). For each of \(f\) and \(g\), that incoming sum equals its outgoing sum at \(v\). Substituting those equalities shows that the incoming sum for \(h\) equals its outgoing sum for \(h\). Hence \(h\) satisfies conservation at every nonterminal and is feasible. \(\square\)
Worked Example: Averaging Two Feasible Flows
Take the network with \(V=\{s,a,t\}\) and arcs \(s\to a\) and \(a\to t\), each of capacity \(4\). Let \(f\) assign \(1\) to each arc and \(g\) assign \(3\) to each arc. Both flows satisfy the two arc bounds: \(0\le1\le4\) and \(0\le3\le4\). At the sole nonterminal \(a\), the entering and leaving amounts are equal for each assignment.
Set \(\theta=\tfrac12\). On each arc, the combined amount is \(h(e)=\tfrac12(1)+\tfrac12(3)=\tfrac12+ \tfrac32=2\). Thus the proposed flow assigns \(2\) to both arcs. The capacity checks are \(0\le2\le4\) on \(s\to a\) and \(0\le2\le4\) on \(a\to t\). At \(a\), the entering total is \(2\) and the leaving total is \(2\), so conservation holds.
Check: direct substitution gives the same result on both arcs, and the nonterminal balance is \(2=2\). The combined assignment is feasible, as the theorem predicts.
Common Pitfalls and a Practical Checklist
Wrong calculation: checking only that the flow is nonnegative. In the over-capacity example, the proposed amount \(3\) on \(u\to v\) is nonnegative, but the capacity is \(2\). The correct test is the full pair of bounds \(0\le f(e)\le c(e)\) on every arc; here, \(3\le2\) fails.
Wrong calculation: checking only vertices that seem to carry flow between terminals. A nonterminal must satisfy conservation wherever it lies in the network, regardless of how an assignment is described. Conversely, the source and sink are excluded from these conservation equations. Do not impose the nonterminal equation at a terminal as part of the feasibility test.
Wrong calculation: adding all incident flow amounts without regard to direction. At a vertex, an incoming amount belongs on the left side of the equation and an outgoing amount on the right. In the third example, vertex \(a\) has incoming flow \(3\) and outgoing flow \(1+1=2\); adding all three amounts together would not test conservation at all.
A reliable final check is to keep two separate records: one list of arc inequalities and one list of nonterminal equalities. The assignment is feasible only if every entry in both records is satisfied. If the network has no nonterminals, the conservation list is empty, but every arc still has to meet its capacity bounds.
Check Your Understanding
For each question, state which capacity or conservation conditions must be checked before deciding feasibility.
- In a network with terminals \(s,t\), which vertices require conservation equations, and which arcs require capacity checks?
- A proposed flow satisfies every conservation equation, but one arc has \(f(e)>c(e)\). Is the flow feasible? Explain using the defining conditions.
- At a nonterminal \(v\), the entering amounts are \(2\) and \(1\), while the leaving amounts are \(1\) and \(2\). Does conservation hold? Show the totals.
- Suppose a graph has no vertices other than \(s\) and \(t\). Which part of the feasibility test remains necessary?
- If \(f\) and \(g\) are feasible and \(0\le\theta\le1\), what assignment does the convex-combination theorem produce on an arc \(e\)?