1
$\begingroup$

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 )$?

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

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.