<p>This is the proof given <a href="http://link.springer.com/article/10.1007%2Fs00453-005-1167-9" rel="nofollow">here</a>, 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.</p>

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

<ol>
<li>If $e \notin P_1$ and $e \notin P_2$ then $f(e)=0$.</li>
<li>If $e \in P_1$ and $e \notin P_2$ then $f(e)=f_2$.</li>
<li>If $e \notin P_1$ and $e \in P_2$ then $f(e)=f_2$.</li>
<li>If $e \in P_1$, $e \in P_2$ and $e$ is a forward edge in $P_1$, then $f(e)=2f_2$.</li>
<li>If $e \in P_1$, $e \in P_2$ and $e$ is a backward edge in $P_1$, then $f(e)=0$.</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2013-03-01T10:26:34.867Z
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
CC BY-SA 3.0
2013-03-01T15:20:11.587Z
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
CC BY-SA 3.0
2013-03-02T09:19:38.410Z
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
CC BY-SA 3.0
2013-03-02T14:24:19.143Z
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
CC BY-SA 3.0
2013-03-02T14:25:52.700Z
Any ideas about the general case (when can a flow be decomposed into at most $k$ paths)?
polkjh
CC BY-SA 3.0
2013-03-02T15:24:46.790Z
So far, I do not see how we could adapt this to the general case and also which additional assumption would be necessary.
math
CC BY-SA 3.0
2013-02-28T16:10:49.897Z
2013-03-01T15:18:07.970Z
2013-03-01T15:18:07.970Z
polkjh
<p>It is strongly NP-hard to decompose the flow into a minimum number of path flows. There is a simple reduction from 3-partition. </p>

<p>See <a href="http://www.sciencedirect.com/science/article/pii/S0377221706006552" rel="nofollow noreferrer">http://www.sciencedirect.com/science/article/pii/S0377221706006552</a></p>

CC BY-SA 3.0
2017-05-04T12:04:45.860Z
2017-05-04T12:04:45.860Z
Chao Xu
<p>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:</p>

<blockquote>
  <p>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</p>
  
  <ul>
  <li>$k\le |A|$</li>
  <li>the flow value of $f$ is equal the sum of the flow values of the $f_i$'s</li>
  <li>the flow $f_i$ sends only positive flow on the edges of $p_i$</li>
  </ul>
</blockquote>

<p>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?</p>

<p>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.</p>

<p>math</p>

CC BY-SA 3.0
2013-02-23T15:53:03.673Z
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
CC BY-SA 3.0
2013-02-23T16:11:36.033Z
@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
CC BY-SA 3.0
2013-02-23T17:52:57.093Z
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
CC BY-SA 3.0
2013-02-25T03:57:59.240Z
**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.
Jeffε
CC BY-SA 3.0
2013-02-25T15:34:19.687Z
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
CC BY-SA 3.0
2013-02-27T13:08:30.453Z
A proof for the particular case (decomposition into 3 paths and a circulation) is given in [here](http://link.springer.com/article/10.1007%2Fs00453-005-1167-9). It discusses a little about the general case too.
polkjh
CC BY-SA 3.0
2013-02-27T13:16:02.177Z
Note that the path given in the second iteration of Ford-Fulkerson algorithm is not a path in original graph. It is a path in the residual graph with respect to the flow obtained in the first iteration. So we do not directly have a decomposition of the flow into two paths. Also the statement is that it can be decomposed into 'at most' 3 paths and a circulation (we can do trivial things like add zero flow paths or break some path etc to make it equal if necessary)
polkjh
CC BY-SA 3.0
2013-02-28T15:36:18.200Z
@polkjh Thanks for the link. I think you mean Lemma 1. I have a question about this proof: 1. if we reduce the flow value along $P_1$ by $f_2$, why is the remaining flow $f_2$ integral and has flow value $2f_2$? 2. How exactly do you get this 3 paths? Maybe you can turn this into an answer such that I can upvote and accept it.
math
<graph-theory>
Can a flow be decomposed in a given number of paths?
math
# Can a flow be decomposed in a given number of paths?

(Asked by: username_0 on 2013-02-23)

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

**Tags:** graph-theory
> **Comments:**
> **username_1**: 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$).  
> **username_0**: @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.  
> **username_1**: 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$.  
> **username_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.  
> **username_3**: 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.  
> **username_4**: A proof for the particular case (decomposition into 3 paths and a circulation) is given in [here](http://link.springer.com/article/10.1007%2Fs00453-005-1167-9). It discusses a little about the general case too.  
> **username_4**: Note that the path given in the second iteration of Ford-Fulkerson algorithm is not a path in original graph. It is a path in the residual graph with respect to the flow obtained in the first iteration. So we do not directly have a decomposition of the flow into two paths. Also the statement is that it can be decomposed into 'at most' 3 paths and a circulation (we can do trivial things like add zero flow paths or break some path etc to make it equal if necessary)  
> **username_0**: @polkjh Thanks for the link. I think you mean Lemma 1. I have a question about this proof: 1. if we reduce the flow value along $P_1$ by $f_2$, why is the remaining flow $f_2$ integral and has flow value $2f_2$? 2. How exactly do you get this 3 paths? Maybe you can turn this into an answer such that I can upvote and accept it.  

---

## 2 answers

### Answer by username_4 on 2013-02-28. Score: 3 | Accepted answer

This is the proof given [here](http://link.springer.com/article/10.1007%2Fs00453-005-1167-9), 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.

> **Comments:**
> **username_0**: 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$?  
> **username_4**: 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$.  
> **username_0**: 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.  
> **username_4**: 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$.  
> **username_4**: Any ideas about the general case (when can a flow be decomposed into at most $k$ paths)?  
> **username_0**: So far, I do not see how we could adapt this to the general case and also which additional assumption would be necessary.  

---

### Answer by username_5 on 2017-05-04. Score: 3

It is strongly NP-hard to decompose the flow into a minimum number of path flows. There is a simple reduction from 3-partition.

See <http://www.sciencedirect.com/science/article/pii/S0377221706006552>


---

