Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$.

If I understand UGC correctly, the above result is tight for general graph under UGC.

Question: Can we obtain a better approximation if we have the promise - $mincut(G) = O(\log n )$?

  • $\begingroup$ what is $\lambda$? what is conductance? $\endgroup$
    – Saeed
    May 21, 2017 at 22:31
  • $\begingroup$ @Saeed: The 2nd largest value of the normalized Adjaceny matrix. $\endgroup$ May 22, 2017 at 6:03


Your Answer

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