# Finding the perfomance ratio in a multicommodity-flow

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?

-

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?

-
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