Proof that sparsest cut is NP-hard

Question

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.

Answer 1

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