4
$\begingroup$

Suppose $G=(V,E)$ be a directed graph , and let $u,v,w$ be distinct vertices. Suppose there are $k$ edge disjoint paths from $u$ to $v$ in $G$, and $k$ edge disjoint paths from $v$ to $w$ in $G$. The paths from $u$ to $v$ van share edges with the paths from $v$ to $w$. Then, how to show that there are $k$ edge disjoint paths from $u$ to $w$ in $G$ using Menger's theorem or MaxFlow-MinCut.

Update: I have already proved the following statement: Given an integer $k>0$, $G$ has $k$ edge disjoint paths from $s$ to $t$ if and only if there is an $s,t$ flow of value $k$ in $G$.

By the above statement, we know that $G$ has a $u,v$ flow of value k, and $G$ has a $v,w$ flow of value k, but how can we show there is a $u,w$ flow of value $k$ in $G$? This means I have to prove the transitivity of a flow, my thought is to use the flow conservation property of internal vertex to prove that, the internal vertex which joins the $u,v$ flow and $v,w$ flow is $v$. Is this the right approach or there is a better way to approach this?

$\endgroup$

2 Answers 2

2
$\begingroup$

An $x,y$-flow of value $k$ is a flow with excess $-k$ at $x$ ($k$ more flow leaving than entering), excess $+k$ at $y$ ($k$ more flow entering than leaving) and excess $0$ at every other node (flow conservation).

So if you add together a $u,v$-flow of value $k$ and a $v,w$-flow of value $k$ (edge by edge), you get something that's almost like a $u,w$-flow of value $k$. The only problem is that some edges might be used twice in the sum, exceeding capacity.

Prove that if an edge $xy$ is used twice in the sum of the two flows, then the sum of the flows also contains a cycle containing $xy$. Then, we can subtract $1$ from the flow along each edge of the cycle, and avoid this problem. Repeat for every such edge, and you'll get an actual $u,w$-flow of value $k$.

$\endgroup$
3
  • $\begingroup$ I have drawn a picture of an instance where an edge $xy$ is used twice in the sum of two flows, it indeed must contain a cycle containing $xy$. But can you explain more about why we have to subtract 1 from the flow along each edge of the cycle? How can subtract 1 helps? Which problem it avoids specifically? Thanks. $\endgroup$
    – kkkkstein
    Commented Mar 29, 2021 at 16:51
  • $\begingroup$ let's say I have a $u,v$ flow of value $2$, where the flow is a simple path $(u,a,b,c,v)$, and I have a $v,w$ flow of value $2$, where the flow is simple path $(v,z,b,c,w)$. Then we have a common edge $bc$ being used twice, so $bc$ has carries flow of value $4$, but after subtracting $1$ from the cycle, the edge $bc$ still carries flow of value $3$, which means it is still used twice? So my question is why we should subtract $1$ or am I interpreting something wrong? $\endgroup$
    – kkkkstein
    Commented Mar 29, 2021 at 17:09
  • $\begingroup$ Your initial $u,v$-flow and $v,w$-flow should assign value at most $1$ to each edge, if they correspond to sets of edge-disjoint paths. $\endgroup$ Commented Mar 29, 2021 at 18:32
1
$\begingroup$

I would probably use Menger's Theorem. If there were a small $u$-$w$ cut, then $v$ is "on one side or the other" of the cut. But that seems like a problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .