# Max flow bottleneck approach flow after k iterations

This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why.

Given a network flow $$(G,c)$$ over graph $$G(V,E)$$.

Assume we run Edmonds-Karp algorithm to find the max flow with the Max Bottleneck approach.

After $$\frac{|E|}{2}$$ iterations we decide to stop the algorithm. What is true about the current flow?

1. The flow we found is a maximum flow.

2. The flow we found is at least $$\frac{3}{4}$$ of the max flow.

3. The flow we found is at least $$\frac{1}{2}$$ of the max flow.

4. The flow we found could be be as small as we like depending on $$c$$ and $$G$$.

5. all above answers are wrong.

In class we proved a lemma that says this ($$f^*$$ is the max flow) $$\left|f^{*}\right|-\left|f^{k}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{k}\left|f\right|\implies$$ $$\left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|$$ now we can use Taylor's approximation for the binomial function and get that: $$\left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\approx\left(1-\frac{1}{\left|E\right|}\cdot\frac{\left|E\right|}{2}\right)\left|f\right|=\frac{\left|f\right|}{2}\implies \\ \left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\frac{\left|f\right|}{2}$$ This means that we can improve our flow by as much as $$\frac{|f|}{2}$$. Why wouldn't answer C be correct?

• What is $f^k$ and what is $\left| f^k \right|$. Jul 18, 2022 at 19:00
• $|f^k|$ is the flow after k iterations of augmenting patha with FF Jul 18, 2022 at 20:20
• And how large must $k$ be to be guaranteed to reach $f^*$? (In EK, not FF.) Jul 18, 2022 at 21:40
• I'm not sure, I know that if we deal with integer capacities, then if $k>|E|\ln(|f^*|)$ But in the general case I am not sure. Jul 19, 2022 at 8:04

Let $$h(x)=(1-\frac1{x})^{\frac x2}$$ for $$x\ge2$$.
Claim: $$h(x)\gt\frac12$$ if $$x\gt2$$.

Proof: Let $$g(x)=\ln(1-x)+x$$ for $$0\le x\lt1$$.
Since $$g'(x)=-\frac1{1-x} + 1 \le 0$$, we have $$g(x)\ge g(0)=0$$.

$$h'(x)=\frac12(1-\frac1{x})^{\frac x2}\left(\ln(1-\frac1x)+\frac{1}{x-1}\right)=\frac12(1-\frac1{x})^{\frac x2}\left(g(\frac1x) + \frac1{x(x-1)}\right)\gt0$$ for $$x\ge2$$.
So $$h(x)\gt h(2)=\frac12$$ for $$x\gt2$$. $$\quad\checkmark$$

$$\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\approx\left(1-\frac{1}{\left|E\right|}\cdot\frac{\left|E\right|}{2}\right)\left|f\right|=\frac{\left|f\right|}{2}$$

The above approximation is misleading, as the claim above implies that $$\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\gt\frac{\left|f\right|}2$$ when $$|E|\gt2$$. Hence, it is impossible to obtain $$\left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\frac{\left|f\right|}{2}$$ from the lemma you learned in the class. So, you should not be able to ascertain answer C is correct.

• For example, $(1-\frac14)^{\frac42}=\frac9{16}\gt\frac12$. One such example is enough to show the reasoning in the question to show C is correct is flawed. Jul 23, 2022 at 17:19