0
$\begingroup$

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!

1 Answers 1

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.

  • 0
    Are you the same person as this guy: [Graph connectivity in sparsest cut](http://math.stackexchange.com/questions/90727/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](http://math.stackexchange.com/questions/90179/the-flow-cut-gap-theorem-for-multicommodity-flow).2011-12-12