4
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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$). $\endgroup$
    – Shaull
    Commented Feb 23, 2013 at 15:53
  • $\begingroup$ @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. $\endgroup$
    – math
    Commented Feb 23, 2013 at 16:11
  • $\begingroup$ 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$. $\endgroup$
    – Shaull
    Commented Feb 23, 2013 at 17:52
  • 2
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Feb 25, 2013 at 3:57
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Feb 25, 2013 at 15:34

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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$? $\endgroup$
    – math
    Commented Mar 1, 2013 at 10:26
  • $\begingroup$ 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$. $\endgroup$
    – polkjh
    Commented Mar 1, 2013 at 15:20
  • $\begingroup$ 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. $\endgroup$
    – math
    Commented Mar 2, 2013 at 9:19
  • $\begingroup$ 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$. $\endgroup$
    – polkjh
    Commented Mar 2, 2013 at 14:24
  • $\begingroup$ Any ideas about the general case (when can a flow be decomposed into at most $k$ paths)? $\endgroup$
    – polkjh
    Commented Mar 2, 2013 at 14:25
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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