Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 2 / b / Solution

Write flow balance using the positive-inflow conventionRemove the lower bounds on network flow by writing $f_{uv}={\ell }_{uv}+x_{uv}$, where only ${\ell }_{BC}=4$ is nonzero. Then $0\le x_{uv}\le c_{uv}-{\ell }_{uv}$, and its required flow balance isIn the order $A,B,C,D$, the lower-bound contribution is $(0,-4,4,0)$, soThe resulting flow network edge capacities areAdd a new source $s$ with an edge $s\to A$ of flow network edge capacity $6$, and a new sink $t$ with edges $B\to t$ and $D\to t$ of flow network edge capacities $1$ and $5$. A feasible flow saturating these new edges is equivalent to a solution for $x$: ordinary flow conservation in the enlarged flow network produces exactly the residual supplies and demands above. All source and sink edges must be saturated, requiring flow value $6$.

Start the Edmonds–Karp algorithm at zero flow. Repeated breadth-first search in the residual network permits the following shortest augmenting paths; when paths tie, choose the one through $B$ first.

The first augmenting path has three edges. Once $B\to t$ is saturated, the next shortest possibilities have four edges, so steps $2$ and $3$ respect the breadth-first search rule. Each augmentation adds the usual backward edges to the residual network, though these particular augmentations need only forward edges. Now $s\to A$ is saturated, so no further augmenting path exists. The cut of a flow network with source side $\{s\}$ has cut capacity $6$, proving that the obtained flow is a maximum flow.

The original-edge values for $x$ are $(4,2,0,3,2)$ in the order $AB,AC,BC,BD,CD$. Restore the lower bound to obtainAll original capacity constraints hold, and $f_{BC}=4$ meets its lower bound. The net inflows at $A,B,C,D$ are respectivelyThe original network therefore admits a feasible circulation with vertex demands.