# Proof that sparsest cut is NP-hard

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.

• 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 Sep 27, 2011 at 7:30
• @Jagadish answer? Sep 27, 2011 at 13:19

## 1 Answer

[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.

• 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. Sep 27, 2011 at 21:36