<p><em><a href="http://dl.acm.org/citation.cfm?id=69876" rel="nofollow noreferrer">Theorem</a></em>: 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)}$.</p>

<p>If I understand <a href="https://en.wikipedia.org/wiki/Unique_games_conjecture" rel="nofollow noreferrer">UGC</a> correctly, the above result is tight for general graph under UGC. </p>

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

CC BY-SA 3.0
2017-05-21T22:31:24.270Z
what is $\lambda$? what is conductance?
Saeed
CC BY-SA 3.0
2017-05-22T06:03:58.503Z
@Saeed: The 2nd largest value of the normalized Adjaceny matrix.
Vivek Bagaria
<approximation-algorithms><spectral-graph-theory><max-flow-min-cut><unique-games-conjecture><promise-problems>
Sparse-cut approximation for well connected graphs
Vivek Bagaria
# Sparse-cut approximation for well connected graphs

(Asked by: username_0 on 2017-05-21)

*[Theorem](http://dl.acm.org/citation.cfm?id=69876)*: 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](https://en.wikipedia.org/wiki/Unique_games_conjecture) 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 )$?

**Tags:** approximation-algorithms, spectral-graph-theory, max-flow-min-cut, unique-games-conjecture, promise-problems

> **Comments:**
> **username_1**: what is $\lambda$? what is conductance?  
> **username_0**: @username_1: The 2nd largest value of the normalized Adjaceny matrix.  

---

## 0 answers

