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?

  • 1
    $\begingroup$ I don't think your approach is well defined enough for us to judge if it's correct or not (assuming you meant "maximum" where you put "minimum"), but the obvious implementation of the correct variants of that might not take linear time. That said, you can always route flow from $t$ back to $s$ along the reversed graph where there are no meaningful decisions to be made, and instead only bottlenecks to be heeded. $\endgroup$
    – Yonatan N
    Mar 22 '21 at 22:18
  • $\begingroup$ Dear @YonatanN, after removing $t$ our graph become tree, so we do like greedy approach and for each vertex save minumum flow from $s$ to that vertex. $\endgroup$
    – user133359
    Mar 22 '21 at 22:38
  • $\begingroup$ The problem is homework for many years ago of non-English resources. I spend much time to find an algorithm on this problem to be linear. $\endgroup$
    – user133359
    Mar 23 '21 at 9:07
  • $\begingroup$ I edited your question. Can you check if this is what you intended to ask? $\endgroup$
    – Steven
    Mar 23 '21 at 10:49

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)$.

  if v==t:
    return +infinity

  for each out-neighbor u of v in G:
      f += min(c(v,u), flow(u))
  return f
  • $\begingroup$ The graph is not undirected! $\endgroup$
    – user133359
    Mar 23 '21 at 18:09
  • $\begingroup$ The same approach works just fine for directed graphs. I'll edit the answer. $\endgroup$
    – Steven
    Mar 23 '21 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy