Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem is to prove that Sparsest cut is solvable on trees in polynomial time.

A short review, a sparsest cut is linear program

$$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$

where $c(S,\overline{S})$ - sum of edge weights for every edge that crosses the cut $S,\overline{S}$

and $D(S,\overline{S})$ - sum of demands between $s_{i}$ and $t_{i}$ are separated by $S,\overline{S}$

The proof is based on the claim.

There exists a sparsest cut $(S,\overline{S})$, such that the graphs $G[S]$ and $G[\overline{S}]$ are connected.

Proof of the claim:

Without loss of generality, assume $G[S]$ is not connected. Say it has components $C_{1}...C_{t}$. Let the total capacity of edges from $C_{i}$ to $\overline{C}_{i}$ be $c_{i}$ and the demand be $d_{i}$. The sparsity of cut $S$ is $\frac{c_{1}+\cdots+c_{t}}{d_{1}+\cdots+d_{t}}$. Now since all quantities $C_{i},d_{i}$ are non-negative, by simple arithmetic, there exists $i$ such that $\frac{c_{i}}{d_{i}} \leq \frac{c_{1}+\cdots+c_{t}}{d_{1}+\cdots+d_{t}}$. This implies that cut $C_{i}$ is at least as good as $S$.

Using this claim we know that the sparsest cut on trees will be exactly one edge. Therefore, the sparsest cut problem on trees becomes easy to solve in polynomial time.

The problem is I don't really understand how the claim was proved. I think it was proved by contradiction, firstly we assumed that $G[S]$ is not connected and found a better that $(S,\overline{S})$ cut for a component $C_{i}$, which is contradiction therefore $S$ is connected. Am I wrong? Secondly, how does this claim apply that sparsest cut is solvable on a tree. Just because as a component $C_{1}$ we can take a one edge of the tree? And how to show that it's solvable in polynomial time?

Thanks!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Actually, you understand more than you think :). The proof indeed goes by contradiction, in that if the optimal cut induced disconnected components, then one of the components would give a better cut value. The rest of the proof follows from the fact that you can now parametrize the set of candidate optimal solutions by edges from the tree (since each edge removal creates two connected subgraphs). There are n-1 edges, and for each edge you can compute the cut cost in poly time.

share|improve this answer
    
Thanks you very much for the answer! Actually I thought it's obvious that the cut separates a connected graph into two connected subgraph, otherwise it sounds like double cut. Wasn't it obvious? Why we need claim for this fact? Having proved this claims,we see that a tree partitioned from this graph is fully connected? Right? Therefore we can make finite number of arrangement of the cut, which is in the case of tree just an edge? Right so far? But looks like there should be something else that proves poly time solution on trees, I am not sure it's poly time solution –  pok Dec 9 '11 at 9:58

Your Answer

 
discard

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.