Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

If we have a digraph $G=(V,A)$ with capacity $u_a\in \mathbb{N}$ for $a\in A$ and a source $s$ and sink $t$. I know the following theorem:

Let $f$ be a flow in the network above. Then there is a collection of feasible flows $f_1,\dots,f_k$ and $s$-$t$ paths $p_1,\dots,p_k$ such that

  • $k\le |A|$
  • the flow value of $f$ is equal the sum of the flow values of the $f_i$'s
  • the flow $f_i$ sends only positive flow on the edges of $p_i$

I am wondering if for a given flow $f$ and integer $n$ under additional assumption there is such a decomposition in exactly $n$ such paths?

Motivation: In our lecture notes there use two iteration of the Ford–Fulkerson algorithm and claim: the resulting flow can be decomposed in 3 paths and a circulation. Clearly, from the algorithm I get two path, but how can I decompose the flow in three path and a circulation? The only decomposition theorem we had, is the one I stated above. I guess it uses some other approach. However the question of decomposing in exactly $n$ paths is also of particular interest for me. Thanks in advance.

math

share|improve this question
    
Do you require the paths to be disjoint/distinct? Otherwise, you can take a flow and "split" it into two flows along the same path (as long as the flow is $>1$). –  Shaull Feb 23 '13 at 15:53
    
@Shaull Thanks for your comment. No, they do not have to be disjoint. You mean, if I have $P_1$ and $P_2$ (paths from the Ford-Fulkerson algorithm) with flow values $f_1$ and $f_2$, you would just define $P_3:=P_2$ with $f_3:=\frac{f_2}{2}$ and also use on $P_2$ the flow value $\frac{f_2}{2}$? Why do we need $>1$? However, why would the also mentioned this circulation? Again, thanks for your help. –  math Feb 23 '13 at 16:11
    
I assumed you wanted integral flows. Otherwise, you don't need $>1$. So, if you can decompose to 2 paths and a circulation, then you can decompose to exactly $n$ for all $n\ge 3$. –  Shaull Feb 23 '13 at 17:52
2  
The quoted theorem is false. Consider a non-trivial circulation that sends zero flow through every edge incident to $s$. Only acyclic flows can be decomposed into positive $(s,t)$-path flows. –  JɛffE Feb 25 '13 at 3:57
1  
The quoted theorem is ok I think. It does not explicitly say that $f$ is decomposed into $f_1,f_2,\ldots,f_k$, only that the value of $f$ is same as the sum of the values of the $f_i$s. To be more useful one should add an additional condition that for each edge $e$, $f(e) \ge \sum_i f_i(e)$. If one wants equality then we also need to use arbitrary cycles in the decomposition but only if one wants equality. –  Chandra Chekuri Feb 25 '13 at 15:34
show 3 more comments

1 Answer 1

up vote 1 down vote accepted

This is the proof given here, to show that the flow obtained after two iterations of Ford-Fulkerson algorithm can be decomposed into at most $3$ paths and a circulation. It is assumed that at each iteration, the algorithm picks the path that allows maximum flow.

Let the path obtained in first iteration be $P_1$ with flow $f_1$. And the path in the residual graph w.r.t this flow, picked by the algorithm in second iteration be $P_2$ with flow $f_2$. Clearly $f_1 \geq f_2$. Now consider the path $P_1$ with flow $f_1-f_2$. Removing this flow from the total flow, the remaining flow can be described as follows (for each edge $e$).

  1. If $e \notin P_1$ and $e \notin P_2$ then $f(e)=0$.
  2. If $e \in P_1$ and $e \notin P_2$ then $f(e)=f_2$.
  3. If $e \notin P_1$ and $e \in P_2$ then $f(e)=f_2$.
  4. If $e \in P_1$, $e \in P_2$ and $e$ is a forward edge in $P_1$, then $f(e)=2f_2$.
  5. If $e \in P_1$, $e \in P_2$ and $e$ is a backward edge in $P_1$, then $f(e)=0$.

So the remaining flow is now $f_2$-integral, with a total flow of $2f_2$ from $s$ to $t$. We can show in general that if a flow is $r$-integral with a total flow of $kr$ from $s$ to $t$, then this flow can be decomposed into at most $k$ $s$-$t$ paths and a circulation. We can just start from $s$ and move along any edge carrying some flow and reach $t$. This gives an $s$-$t$ path with flow $r$ (or some multiple of $r$). Remove this flow and repeat this process again (walk from $s$ to $t$ along flow carrying edges). Finally, when there is no net flow let from $s$ to $t$, the remaining flow is a circulation. That this process ends in $k$ steps can be shown formally using induction.

share|improve this answer
    
thanks for putting your comment into an answer. I have some question about the values $f(e)$. First this edge $e$ is an edge in the residual graph, right? I agree with 1./2./3. I do not see how do you get 4./5. especially 5., since $P_1$ should contain NO backward edges. And what is with the remaining cases, like $e$ is in both, $P_1$ and $P_2$? –  math Mar 1 '13 at 10:26
    
Sorry, that was a typo. The last two cases are when $e$ is both the paths. And the two cases are based on whether $e$ occurs in $P_2$ as a forward edge of $P_1$ or a backward edge of $P_1$. –  polkjh Mar 1 '13 at 15:20
    
thanks for the update. Again, I think in 5. it should be a a backward edge of $P_2$, since $P_1$ does not contain any backward edge. –  math Mar 2 '13 at 9:19
    
Yes, but I think you got the idea. What I mean there is that edge $e$ is used in $P_2$ in opposite direction compared to its original direction used in $P_1$. Thanks for pointing that out, it should probably be said as backward in $P_2$. –  polkjh Mar 2 '13 at 14:24
    
Any ideas about the general case (when can a flow be decomposed into at most $k$ paths)? –  polkjh Mar 2 '13 at 14:25
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.