# Can a flow be decomposed in a given number of paths?

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

-
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
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ɛﬀE Feb 25 '13 at 3:57
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

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.

-
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