Timeline for Can a flow be decomposed in a given number of paths?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2017 at 12:04 | answer | added | Chao Xu | timeline score: 3 | |
| Apr 26, 2013 at 10:59 | history | tweeted | twitter.com/#!/StackCSTheory/status/327738795111874560 | ||
| Mar 2, 2013 at 15:22 | history | edited | math | CC BY-SA 3.0 |
deleted 11 characters in body
|
| Mar 2, 2013 at 9:21 | vote | accept | math | ||
| Mar 2, 2013 at 9:19 | vote | accept | math | ||
| Mar 2, 2013 at 9:20 | |||||
| Feb 28, 2013 at 16:10 | answer | added | polkjh | timeline score: 3 | |
| Feb 28, 2013 at 15:36 | comment | added | math | @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. | |
| Feb 27, 2013 at 13:16 | comment | added | polkjh | 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) | |
| Feb 27, 2013 at 13:08 | comment | added | polkjh | A proof for the particular case (decomposition into 3 paths and a circulation) is given in here. It discusses a little about the general case too. | |
| Feb 25, 2013 at 15:34 | comment | added | Chandra Chekuri | 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. | |
| Feb 25, 2013 at 3:57 | comment | added | Jeffε | 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. | |
| Feb 23, 2013 at 17:52 | comment | added | Shaull | 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$. | |
| Feb 23, 2013 at 16:11 | comment | added | math | @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. | |
| Feb 23, 2013 at 15:53 | comment | added | Shaull | 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$). | |
| Feb 23, 2013 at 13:35 | review | First posts | |||
| Feb 25, 2013 at 21:40 | |||||
| Feb 23, 2013 at 13:18 | history | asked | math | CC BY-SA 3.0 |