Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset?

It looks like it should be a kind of fundamental theorem for sparsest cut. But I didn't remember something like this for multicut and multicommodity flow.

Can you give me a hint how to prove this?


share|cite|improve this question
up vote 1 down vote accepted

I am not sure I understand your question. The sparsest cut is a node set $S \subseteq V$ that minimizes the "sparcity" measure:

$$\Phi(S) = \frac{c(S, \bar{S})}{D(S, \bar{S})},$$

where $c(S, \bar{S})$ is the sum of the capacities of the edges having one endpoint in $S$ and the other in $\bar{S}$, and $D(S, \bar{S})$ is the demand from $S$ to $\bar{S}$. Since there is a finite number of different node sets $S\subseteq V$, a minimizer definitely exists and you could as well find it by, say, exhaustive search.

Hence I don't quite get your question.

share|cite|improve this answer
To be honest I am also don't completely understand what I need to prove. Immediately after receiving this task, I ask if we can formulate sparsest cut problem as linear problem we can solve it by ellipsoid algorithm and get optimal solution. The answer was NO, this is wrong way, first start with any optimal cut $S'$ and consider the connected component of $G/S'$. It's supposed to help me, but I neither get the hint to. – fog Dec 12 '11 at 4:51
Are you the same person as this guy: Graph connectivity in sparsest cut? He's asking the same question. If not, I'd like to point you to this discussion and the lecture notes therein: The flow/cut gap theorem for multicommodity flow. – Gabor Retvari Dec 12 '11 at 12:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.