Maximum flow value obtained with augmenting paths in grid-like digraph

Question

Given the network flow $R = (G,s,t,c)$, where the digraph $G = (V,E)$ looks like this

and the grid $G - \{s,t\}$ has $n \times n$ vertices, north-south, west-east oriented with all the edges of capacity $1$, I need to prove that starting with a null flow and continuing with successive growths on augmenting paths only with forward arcs it is possible to reach only a flow value of $1$.

I am not sure about the vertical arcs that connects the "rows" of the grid in the digraph G, because these doesn't seem to be forward arcs or backward arcs.

The bottom question is... How should I begin to approach this? I think I get the question but I have no idea where to begin.

Answer 1

One cannot be 100% sure with regards to vocabulary in graph theory, so please verify with your professor (from your wording I guess this is a class assignment), but it seems to me that "augmenting paths only with forward arcs" means "augmenting paths whose direction aligns with the direction of the arrows in $R$".

In fact, if you could not use the vertical arcs, then any augmenting reasonable flow algorithm will find the maximum flow, that is, $n$. The reason is that then you have just $n$ disjoint paths which together constitute the maximum flow.

Assuming this understanding is correct, here are some pointers:

Hint:

1. In this graph there is only one maximum flow which consists of $n$ paths that use only horizontal edges. First, try to get any flow with a smaller value.
2. The above is already a small hint to the solution: you have to use the vertical edges to succeed in your task.

More hints:

3. You can block the maximum-flow paths by using their edges: as you cannot use backward arcs, the optimal path cannot claim that edge anymore.

4. Try to find one path of value $1$ which will block all the other paths.

Solution:

Let $A$ be an augmenting path be of this shape and value $1$:

then there is no other augmenting path that uses only forward edges. The reason is that $G' = (V, E(G) - E(A))$ is a graph in which $s$ and $t$ are in two different weakly connected components, in particular there is no path from $s$ to $t$.

I hope this helps $\ddot\smile$