World's most popular travel blog for travel bloggers.

[Solved]: Maximum flow, where such paths as source$\to$node$\to$sink must be ignored

, , No Comments
Problem Detail: 

How can the maximum flow of a graph be computed when all nodes of the graph are connected to both sink and source nodes (two hypothetical nodes), and the maximum flow method should ignore such paths as $\text{source} \to \text{node} \to \text{sink}$, where $\to$ is a single edge?

A valid path containing a positive flow can be $source \to v$, $v \to w$, and $w \to sink$ where $v \neq{w}$.

I am not sure whether it's helpful, but the graph is a DAG (directed acyclic graph).

Asked By : beginner1010

Answered By : Dennis Kraft

Let $G=(V,E)$ be some directed graph where every node $v_i$, except for the source $s$ and sink $t$, has an in-edge $(s,v_i)$ and an out-edge $(v_i,t)$.

To compute the desired flow, we can reduce the problem to a new directed graph $G'=(V',E')$, where every node of the original Graph, except for $s$ and $t$, is replaced by two new nodes $v_i'$ and $v_i''$. The source is now connected to $v_i'$ and the sink to $v_i''$. Thus, we have new edges $(s,v_i')$ and $(v_i'',t)$. Furthermore, we connect every $v_i''$ with the corresponding $v_i'$ via an edge $(v_i'',v_i')$ of very high capacity. Finally, we add an edge $(v_i',v_j'')$ for every edge $(v_i,v_j)$ of the original graph. The capacity of every edge in $G'$ is equal to its counterpart in $G$, except for the edges $(v_i'',v_i')$, wich correspond to nodes in $G$ and therefore have arbitrary high capacity.

Note that flow that enters $v_i'$ via the source can not directly escape to the sink but must traverse an edge $(v_i',v_j'')$ to another vertex $v_j''$ first. From $v_j''$ the flow can either go to the sink, or continue onwards via $v_j'$. Thus, by computing a maximum flow in $G'$ we obtain a solution for $G$ where all flow that leaves the sink must traverse at least three edges before it reaches the sink.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48302

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback