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?

  • 1
    $\begingroup$ What is $f^k$ and what is $\left| f^k \right|$. $\endgroup$
    – Pål GD
    Jul 18, 2022 at 19:00
  • $\begingroup$ $|f^k|$ is the flow after k iterations of augmenting patha with FF $\endgroup$ Jul 18, 2022 at 20:20
  • $\begingroup$ And how large must $k$ be to be guaranteed to reach $f^*$? (In EK, not FF.) $\endgroup$
    – Pål GD
    Jul 18, 2022 at 21:40
  • $\begingroup$ 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. $\endgroup$ Jul 19, 2022 at 8:04

1 Answer 1


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$


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.

  • $\begingroup$ 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. $\endgroup$
    – John L.
    Jul 23, 2022 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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