Does the sparsest cut always have a solution?

Question

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!

Answer 1

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.