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?


Thank you for your help
$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.
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^*$.
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^*$.
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$.
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?