10
$\begingroup$

Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut problem?

I could not find any proof in Vazirani's book - Approximation Algorithms, which presents the Leighton Rao algorithm, or the book "Computers and Intractability" - which summarizes many NP-complete problems. I could not find it by searching (with obvious search strings) on Google. There is one paper by Chawla et al, which assumes Khot's UGC conjecture and proves the hardness of approximating the sparsest cut. I was hoping to see a proof that does not assume any conjecture.

The proof should just reduce a known NP-hard problem to sparsest cut.

Thank you,

Arpita Korwar.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ The paper "Sparsest cuts and bottlenecks in graphs" by David W. Matula, Farhad Shahrokhi gives a reduction from max-cut problem. Max-cut proof of hardness can be found in Garey Johnson. sciencedirect.com/science/article/pii/0166218X9090133W $\endgroup$
    – Jagadish
    Commented Sep 27, 2011 at 7:30
  • 2
    $\begingroup$ @Jagadish answer? $\endgroup$
    – Tyson Williams
    Commented Sep 27, 2011 at 13:19

1 Answer 1

Reset to default
11
$\begingroup$

[Moved from comment]

The paper "Sparsest cuts and bottlenecks in graphs" by David W. Matula, Farhad Shahrokhi gives a reduction from max-cut problem. Max-cut's proof of hardness can be found in Garey Johnson.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the reference. Want to mention that this is the uniform version of sparsest cut (basically expansion of the graph) and a few years ago I had a hard time finding a proper ref that contained a proof. Had to work it out from Max Cut. $\endgroup$
    – Chandra Chekuri
    Commented Sep 27, 2011 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.