<p>[Moved from comment]</p>

<p>The paper "<a href="http://sciencedirect.com/science/article/pii/0166218X9090133W">Sparsest cuts and bottlenecks in graphs</a>" 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.  </p>

CC BY-SA 3.0
2011-09-27T21:36:41.813Z
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.
Chandra Chekuri
CC BY-SA 3.0
2011-09-27T13:48:20.147Z
2011-09-27T13:48:20.147Z
Jagadish
<p>Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be <strong>NP</strong>-hard. Where can I find a proof of this? Which known <strong>NP</strong>-hard problem reduces to the sparsest cut problem?</p>

<p>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 <strong>NP</strong>-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.</p>

<p>The proof should just reduce a known <strong>NP</strong>-hard problem to sparsest cut.</p>

<p>Thank you,</p>

<p>Arpita Korwar.</p>

CC BY-SA 3.0
2011-09-27T07:30:31.793Z
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.

http://www.sciencedirect.com/science/article/pii/0166218X9090133W
Jagadish
CC BY-SA 3.0
2011-09-27T13:19:31.137Z
@Jagadish answer?
Tyson Williams
<cc.complexity-theory><reference-request><np-hardness>
Proof that sparsest cut is NP-hard
Arpita Korwar
# Proof that sparsest cut is NP-hard

(Asked by: username_0 on 2011-09-27)

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.

**Tags:** cc.complexity-theory, reference-request, np-hardness
> **Comments:**
> **username_1**: 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.  http://www.sciencedirect.com/science/article/pii/0166218X9090133W  
> **username_2**: @Jagadish answer?  

---

## 1 answers

### Answer by username_1 on 2011-09-27. Score: 11 | Accepted answer

[Moved from comment]

The paper "[Sparsest cuts and bottlenecks in graphs](http://sciencedirect.com/science/article/pii/0166218X9090133W)" 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.

> **Comments:**
> **username_3**: 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.  

---

