$G = (V, A)$ is a directed graph where all arcs in $A$ have a capacity of $1$. The shortest length path in $G$ from $s$ to $t$ consists of exactly $d$ arcs. G has a total of $m$ arcs and $n$ vertices.

(a) Prove that the maximum $s-t$ flow has value $O\left(\frac{m}{d}\right)$.

(b) Prove that the minimum capacity $s-t$ cut has value $O\left(\frac{n^2}{d^2}\right)$.

For part a), I was thinking that since there are going to be $m$ arcs total, the value would be in the order of $m$. I am thinking that by diving this $m$ by $d$, we get the total number of arcs used when gathering the maximum $s-t$ flow through the Ford-Fulkerson algorithm. But I am not entirely sure how to prove this or if this is actually the case.

For part b), I am also quite confused as I am not sure how I should go about finding either of the numerator or denominator. I was thinking about splitting the graph in two to represent the cut but that has not been helping me to compute the value.

I was also wondering that since all arcs have a capacity of $1$, wouldn't the value of the maximum flow and the minimum cut both just be $1$? So do I have to show that both $\frac{m}{d}$ and $\frac{n^2}{d^2}$ are equal to $1$?

I would greatly appreciate any help!

  • 1
    $\begingroup$ Neither of these questions are, as you've stated them, asking you for a run-time. $\endgroup$ – Misha Lavrov Feb 3 at 2:00
  • $\begingroup$ Yes sorry. My apologies. The question is asking me to compute the value. But I am not sure how to approach this using the big $O$. $\endgroup$ – esterrobson Feb 3 at 2:03
  • $\begingroup$ So, please edit your question so it doesn't mention runtime. $\endgroup$ – Gerry Myerson Feb 3 at 5:39
  • $\begingroup$ @GerryMyerson I have just edited it. $\endgroup$ – esterrobson Feb 3 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.