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$'sthe 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 FordFulkerson 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
Can a flow be decomposed in a given number of paths?
graph theory
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$).If $e \notin P_1$ and $e \notin P_2$ then $f(e)=0$.If $e \in P_1$ and $e \notin P_2$ then $f(e)=f_2$.If $e \notin P_1$ and $e \in P_2$ then $f(e)=f_2$.If $e \in P_1$, $e \in P_2$ and $e$ is a forward edge in $P_1$, then $f(e)=2f_2$.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.