Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence

Question

You are given an directed graph $G = (V , E)$ with positive edge capacities, a source vertex $s \in V$, and a target vertex $t \in V \setminus \{s\}$. $G$ is guaranteed to have the following additional property: The graph obtained by deleting $t$ from $G$ has exactly one path from $s$ to each other vertex in $V \setminus \{t\}$. How can we compute the maximum flow from $s$ to $t$ in $G$ in time $O(|V|+|E|)$?

First, I read this post, and i think start from $s$ then run BFS, when we visit each node then set it to minimum flow that we find from $s$ to that vertex. Do this until we achieve vertices that have edges to $t$ and push each flow inside that vertices to $t$ this way we have an algorithm with linear time. Is argument correct?

Answer 1

Construct a new graph $T=(V', E')$ by modifying $G=(V,E)$ as follows: for each edge $(u,t) \in E$ of capacity $c$ add a new vertex $t_u$ and an edge $(u, t_u)$ of capacity $c$, then delete $t$ and all its incident edges.

Notice that $T$ is an arborescence and that the maximum flow in $G$ from $s$ to $t$ is equal to the maximum total flow in $T$ from $s$ to the vertices in $L = \{ t_u \mid (u,t) \in E \}$.

We will now find $f^*$ in time $O(|E'|) = O(|E|)$.

In order to do so, explore $T$ with a postorder DFS from $s$ and, for each visited vertex $v \in V'$ keep track of the maximum amount of flow $f(v)$ that can be sent from $v$ to the vertices in $L$ (so that $f^* = f(s)$).

When a leaf $v$ of $T$ is visited we have $f(v) = \begin{cases}+\infty &\mbox{if } v \in L \\ 0 &\mbox{otherwise}\end{cases}$.

When an internal vertex $v$ of $T$ is visited, let $u_1, \dots, u_k$ be its out-neighbors in $T$, and let $c_i$ be the capacity of the edge $(v, u_i)$. We have:

$$ \begin{equation} f(v) = \sum_{i=1}^k \min\{f(u_i), c_i\} \tag{1} \end{equation} $$

Of course you don't actually need to construct $T$. A slight modification of a postorder DFS visit from $s$ in $G$ suffices. Here is a possible recursive implementation in pesudocode where $t$ is assumed to be a global variable, $c(u,v)$ is the capacity of $(u,v) \in E$, and the first call is $\mathrm{flow}(s)$.

flow(v):
  if v==t:
    return +infinity

  f=0
  for each out-neighbor u of v in G:
      f += min(c(v,u), flow(u))
  
  return f