Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are about lemma 2 and its proof, which is needed to find an approximation algorithm for the maximum 2-splittable flow problem.

  • My first question is about the problem definition on page 102. A flow in a network has different values along the arcs. They define a k-splittable $s$-$t$ flow $F$ as $k$ pairs $(P_1,f_1),\dots,(P_k,f_k)$, where $P_i$ is a simple $s$-$t$ path. Does the value of such an $f_i$ change along $P_i$? Since they say $(P_i,f_i)\in \mathcal{P}_{s,t}\times\mathbb{R}_{\ge 0}$ this would imply it does not change along $P_i$. However since natural flows do change along the arcs, I want to be sure, if my interpretation is correct.
  • This question is about lemma $2$ on page 105. I have never heard the definition of a thickest $s$-$t$ path. Also a web search was not successful. What does thickest $s$-$t$ path mean in this context and how can we conclude in the proof that the bottleneck edge $e$ has strictly positive residual capacity using the value of a maximum $s$-$t$ flow in $G'$?
  • If this bottleneck edge $e$ is a forward edge of $P_1$, why do both $P^*_1$ and $P^*_2$ contain this edge?
  • What is meant by a $D/k$ integral $s$-$t$ flow?
  • the last question is about approximation algorithms. So far I have never been in touch with approximation algorithms. I know that a $\rho$ approximation algorithm yields a feasible solution whose value is at most a factor of $\rho$ away from the optimum. So how exactly does lemma 2 imply that using the maximum capacity augmenting path algorithm yields a $\frac{2}{3}$-approximation algorithm?

Thank you for your help

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted
+50
  1. $f_i$ are constant real numbers. They stay the same over the entire path. But note that the paths are not necessarily edge-disjoint. So an edge could be present in multiple paths and hence the actual flow in that edge will be sum of all the corresponding path flows.

  2. For a path $P$, let $cap(P)$ denote the smallest edge capacity in the path. A thickest path is a path $P$ with largest $cap(P)$ (imagine the edges as pipes and capacity defining the thickness of pipe). A bottleneck edge of path $P$ would be an edge with capacity $cap(P)$. After sending a flow $f_1$ on $P_1$, in the corresponding residual graph, let $P_3$ be a thickest path. If the residual capacity of the bottleneck edge is $0$ (i.e., maximum $cap(P)$ value is $0$ over all paths), then no more flow can be sent from $s$ to $t$. But this implies $f_1 \geq f_1^* + f_2^*$ contradicting the assumption that $f_1 \lt f_1^* + f_2^*$.

  3. While constructing this new graph $G^\prime$, edge capacities were reduced to smallest values that allowed the flow $f_1$ to be feasible and the flows $f_1^*$, $f_2^*$ to be feasible. Suppose $e$ is not present in one of the two paths (say $P_1^*$). Then the capacity on edge $e$ must have been reduced to $f_1$ (as $f_1 \geq f_2^*$), resulting in zero residual capacity. So $e$ must be present in both the paths $P_1^*$ and $P_2^*$.

  4. When we say something is $(1/r)$-integral, it means the values involved are integral multiples of $1/r$ (so standard integral solution will be $1$-integral). Here, $D/k$ integral flow means that each edge has a flow which is an integral multiple of $D/k$.

  5. Using lemma $1$, if we have a flow $f_1+f_2$ obtained through two augmenting path iterations, then this flow can be written as sum of $3$ paths with flows $f_1^ \prime ,f_2^ \prime ,f_3^ \prime $. So we have $f_1^ \prime +f_2^ \prime +f_3^ \prime = f_1 + f_2 \geq f_1^* + f_2^*$, where $f_1^* + f_2^*$ is a maximum 2-splittable flow (from lemma 2). Suppose $f_3 ^\prime$ is smallest among $f_1^ \prime ,f_2^ \prime ,f_3^ \prime $. Then $f_3^\prime \leq (1/3) (f_1^ \prime +f_2^ \prime +f_3^ \prime )$. So taking the two paths corresponding to $f_1^\prime$ and $f_2^\prime$, the net flow is $f_1^ \prime +f_2^ \prime \geq (2/3)(f_1^ \prime +f_2^ \prime +f_3^ \prime ) \geq (2/3)(f_1^* + f_2^*)$. So this gives a $\frac{2}{3}$-approximation.

I am not able to see why lemma $1$ is true. Do you have any simple proof for that?

share|improve this answer
    
Thanks for you answer. In point 5, do you mean $f_3'\le (1/3)(f'_1+f'_2+f_3')$ instead of $f'_1$? If not, why is this inequality true and how do you conclude from there that $f'_1+f'_2\ge (2/3)(f_1'+f_2'+f_3')$? A proof of lemma 1 can be found here: link.springer.com/article/10.1007%2Fs00453-005-1167-9 but to see the complete article you need a special login (I have one from my university). If you can not get access, let me know. If you can figure out point 3,too, that would be very helpful. –  hulik Feb 26 '13 at 8:25
    
Thanks for the link! Yes, it was supposed to be $f_3^\prime$ in point $5$, not $f_1^\prime$. I have also added the explanation for point $3$. –  polkjh Feb 26 '13 at 13:36
    
thanks for adding the part about 3). However one small thing is not clear to me: This edge $e$ is, as you assumed, an edge of the two path $P_1$ and $P_2^*$. The flow over this edge is therefore $f_1+f_2^*$, hence the capacity should be reduced to this value. Why do you conclude that it is reduced to $f_1$? –  hulik Feb 26 '13 at 14:15
    
We are not considering the paths $P_1$ and $P_2^*$ together. The new capacities are defined so that the flow on $P_1$ is feasible and independently the flows $P_1^*$ and $P_2^*$ put together are feasible. That is, for each edge $e$, let $c_1(e)$ denote the smallest capacity such that the flow $f_1$ on $P_1$ is feasible. So $c_(e)$ is $f_1$ is $e$ is in $P_1$ and $c_1(e)=0$ otherwise. And let $c_2(e)$ denote the smallest capacity such that the flow formed by sending flows $f_1^*$ and $f_2^*$ on $P_1^*$ and $P_2^*$ respectively, is feasible. (continued in next comment) –  polkjh Feb 26 '13 at 15:50
    
So $c_2(e)$ is $f_1^*+f_2^*$ if $e$ is present in both $P_1^*$, $P_2^*$. If $e$ is present in only one of the paths, $c_2(e)$ will be $f_1^*$ or $f_2^*$ (based on the path it is in) and $c_2(e)=0$ if $e$ is in neither of the paths. The capacities in the new graph $G^\prime$ are now defined as $c(e) = \max \{c_1(e), c_2(e)\}$. So, in our case, if $e$ is present only in $P_2^*$ and not $P_1^*$, $c_2(e)=f_2^*$. S0 $c(e) = \max \{f_1, f_2^*\} = f_1$. –  polkjh Feb 26 '13 at 15:56
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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