9
$\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.

$\endgroup$
  • 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 Sep 27 '11 at 7:30
  • 2
    $\begingroup$ @Jagadish answer? $\endgroup$ – Tyson Williams Sep 27 '11 at 13:19
10
$\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.

$\endgroup$
  • $\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 Sep 27 '11 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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