Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi!

How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset.

Looks like it's 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!

share|improve this question
    
What is a sparset cut? Did you mean sparsest cut? –  Gilead Dec 10 '11 at 5:52
    
Thanks, corrected, of course sparsest cut –  gosm Dec 10 '11 at 8:26
    
WHat does the question mean? What is "the cut for some vertex subset"? –  Igor Rivin Dec 10 '11 at 15:48
    
I need to prove that there is always for any instance of the sparsest cut problem exists optimal solution which is cut $(S,\overline{S})$ for some vertex subset $S \subset V$ –  gosm Dec 10 '11 at 19:45
    
As opposed to what? What other kind of cuts are there? –  Igor Rivin Dec 11 '11 at 10:11

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.