# Does the sparsest cut always have a solution?

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?

Thanks!

-

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.
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