1
$\begingroup$

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?

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\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.
    Commented Jul 23, 2022 at 17:19

Your Answer

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