<p>The actual proof of the $NP$-hardness of computing Cheeger constant ( or edge expansion) was given by <a href="http://arxiv.org/pdf/math/0112146v1.pdf" rel="nofollow">Kaibel in a technical report</a> by a reduction from MAX Cut problem (See theorem 2). The proof is an extension of the proof of the $NP$-hardness of the equicut problem given by <a href="http://www.sciencedirect.com/science/article/pii/0304397576900591" rel="nofollow">Garey, Johnson, and Stockmeyer in Some simplified NP-complete
graph problems</a>.</p>

<p>V. Kaibel: On the expansion of graphs of 0/1-polytopes. Technical report
arXiv:math.CO/0112146, 2001</p>

<p><strong>EDIT</strong>: The argument below is <strong>incorrect</strong>, as pointed out by Chekuri, and left for educational purpose.</p>

<p>This is not a reference as you requested but it explain the folklore status of the hardness result.  </p>

<p>Here is a proof idea of the CoNP-completeness of deciding whether a connected cubic graph is edge-expander and therefore determining the Cheeger constant $h(G)$ is CoNP-hard.</p>

<p>The <a href="http://users.monash.edu/~normd/documents/Diaz-Do-Serna-Wormald-02.pdf" rel="nofollow">minimum bisection problem is $NP$-complete</a> for connected cubic graphs. Here we want to decide whether a graph $G$ with an integer $k$ can be partitioned into two equal size parts such that the number of cut edges is less than $k$.</p>

<p>Note the complement of this problem is equivalent to deciding whether the graph $G$ is expander or not ( every balanced partition of $V$ has cut edges more than $k$).</p>

<p>P.S. Arora in this seminar states that it's $CoNP$-hard to recognize $\alpha$-expander graph ( edge-expansion).  <a href="http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx" rel="nofollow">http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx</a></p>

CC BY-SA 3.0
2015-03-12T07:29:06.257Z
This proof doesn't work either, because the size of the min bisection does not say anything about the edge expansion by itself. For example, a disconnected graph on $2n$ vertices can have minimum bisection $(n-2)^2$.
Sasho Nikolov
CC BY-SA 3.0
2015-03-12T07:30:59.050Z
The graph $G$ is connected cubic graph and for this class minimum bisection problem is NP-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-12T09:11:52.200Z
@SashoNikolov I never seen anyone interested in the expansion of disconnected graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-12T13:12:33.637Z
Aurora in this seminar states that it's $CoNP$-hard to recognize $\alpha$-expander graph ( edge-expansion).  http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-12T14:16:25.087Z
Arora, not Aurora. I do not doubt that deciding $h(G) \geq \alpha$ is coNP hard. But in two answers you have given neither a reference with proof, nor a proof. The disconnected graphs are only to show you that your arguments are bogus. Your "fix" dosn't work either. I can easily show you a connected cubic graph with large minimum bisection and Cheeger constant arbitrarily close to zero. The two problems are related but **not** in the trivial way you are suggesting.
Sasho Nikolov
CC BY-SA 3.0
2015-03-12T14:37:04.847Z
@SashoNikolov Please show me those connected bridgeless cubic graphs and I will send you $100 if I get convinced.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-12T14:56:53.247Z
@MohammadAl-Turkistany: Take two connected bridgeless cubic graphs that are expanders, one with 2n vertices and the other with n vertices and connect them with three edges by adding some 3 new vertices on each side via sub-dividing 3 edges. Now the min-bisection is going to be large ($\Omega(n)$) because you have to cut off a good chunk of the larger expander but the expansion is small because you can split the two expanders by cutting just 3 edges.
Chandra Chekuri
CC BY-SA 3.0
2015-03-12T15:03:05.893Z
@ChandraChekuri Thank you. I am convinced and I will modify the answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-12T17:07:11.863Z
Does Chandra get my $100 now?
Sasho Nikolov
CC BY-SA 3.0
2015-03-12T17:17:41.737Z
You can not give him what you did not win :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-03-12T18:12:32.373Z
To be fair, Kaibel's writeup proves that the Garey, Johnson and Stockmeyer reduction from Max Cut to Min Bisection produces a graph in which the sparsest cuts are bisections.
Sasho Nikolov
CC BY-SA 3.0
2015-03-12T07:12:31.987Z
2015-03-12T16:44:27.903Z
2015-03-12T16:44:27.903Z
Mohammad Al-Turkistany
<p>I too encountered this issue when I was writing a paper that required a citation to hardness of edge expansion (or Cheeger constant) defined as $\min_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$. The classic paper of Leighton and Rao on separators ( <a href="http://dl.acm.org/citation.cfm?id=331526">http://dl.acm.org/citation.cfm?id=331526</a> ) mentions that this is a hard problem and refers to the paper of Garey, Johnson and Stockmeyer (<a href="http://www.sciencedirect.com/science/article/pii/0304397576900591">http://www.sciencedirect.com/science/article/pii/0304397576900591</a>). I could not figure out for a while what they were referring to since there is no mention of edge expansion in the referred to paper. I communicated with Avi Wigderson about this. It finally transpired that one can use the hardness of Max-Cut as shown in the Garey et al paper to relatively easily show that edge-expansion is hard. I forget the details now but it should not be hard to recreate. The paper of Blum etal on hardness of checking whether a graph is a superconcentrator does not directly imply hardness of edge expansion. They are technically not the same problem.</p>

CC BY-SA 3.0
2015-03-12T03:15:03.967Z
My paper which uses the edge expansion hardness is the one below http://onlinelibrary.wiley.com/doi/10.1002/net.20165/abstract. We refer to the Leighton-Rao paper and that of Garey, Johnson, Stockmeyer for hardness of edge expansion.
Chandra Chekuri
CC BY-SA 3.0
2015-03-12T18:59:40.630Z
Thanks! So technically speaking the hardness of determining the Cheeger constant is unproven in the literature?
Delio M.
CC BY-SA 3.0
2015-03-12T23:49:33.777Z
@DelioM. the Kaibel reference in one of Mohammad's answers has a complete proof. It's just the Garey-Johnson-Stockmeyer reduction from unweighted max cut to min bisection, with a short proof that in the graphs produced by the reduction the sparsest cut is a bisection.
Sasho Nikolov
CC BY-SA 3.0
2015-04-04T01:21:26.627Z
Although, I must confess I am lost. I always thought that max-cut is related to the issue of characterising "how bipartite" a graph is. How can this help to find "how connected" a graph is? Equivalently, how can the second lowest eigenvalue of the signless Laplacian bound the second lowest eigenvalue of the laplacian? That a lower bound hold is obvious, but an upper bound?
Delio M.
CC BY-SA 4.0
2018-08-18T21:41:33.340Z
@DelioM. Max Cut is first reduced to Min Bisection by adding more $n$ vertices and taking the complement of the resulting graph. So this reduction relates how close to bipartite one graph is to how connected another graph (related to the complement of the first).
Sasho Nikolov
CC BY-SA 3.0
2015-03-12T03:13:22.527Z
2015-03-12T03:13:22.527Z
Chandra Chekuri
<p>I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for this statement. Whom should I give credit for it? In an old paper (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar only proves this assertion "for graphs with multiple edges".</p>

<reference-request><graph-theory><spectral-graph-theory>
Is the Cheeger constant $\mathsf{NP}$-hard?
Delio M.
# Is the Cheeger constant $\mathsf{NP}$-hard?

(Asked by: username_0 on 2015-03-11)

I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for this statement. Whom should I give credit for it? In an old paper (Isoperimetric Numbers of Graphs, J. Comb. Theory B, 1989) Mohar only proves this assertion "for graphs with multiple edges".

**Tags:** reference-request, graph-theory, spectral-graph-theory

---

## 2 answers

### Answer by username_3 on 2015-03-12. Score: 14 | Accepted answer

I too encountered this issue when I was writing a paper that required a citation to hardness of edge expansion (or Cheeger constant) defined as $\min\_{S \subset V, |S| \leq |V|/2} |\delta(S)|/|S|$. The classic paper of Leighton and Rao on separators ( <http://dl.acm.org/citation.cfm?id=331526> ) mentions that this is a hard problem and refers to the paper of Garey, Johnson and Stockmeyer (<http://www.sciencedirect.com/science/article/pii/0304397576900591>). I could not figure out for a while what they were referring to since there is no mention of edge expansion in the referred to paper. I communicated with Avi Wigderson about this. It finally transpired that one can use the hardness of Max-Cut as shown in the Garey et al paper to relatively easily show that edge-expansion is hard. I forget the details now but it should not be hard to recreate. The paper of Blum etal on hardness of checking whether a graph is a superconcentrator does not directly imply hardness of edge expansion. They are technically not the same problem.

> **Comments:**
> **username_3**: My paper which uses the edge expansion hardness is the one below http://onlinelibrary.wiley.com/doi/10.1002/net.20165/abstract. We refer to the Leighton-Rao paper and that of Garey, Johnson, Stockmeyer for hardness of edge expansion.  
> **username_0**: Thanks! So technically speaking the hardness of determining the Cheeger constant is unproven in the literature?  
> **username_2**: @DelioM. the Kaibel reference in one of Mohammad's answers has a complete proof. It's just the Garey-Johnson-Stockmeyer reduction from unweighted max cut to min bisection, with a short proof that in the graphs produced by the reduction the sparsest cut is a bisection.  
> **username_0**: Although, I must confess I am lost. I always thought that max-cut is related to the issue of characterising "how bipartite" a graph is. How can this help to find "how connected" a graph is? Equivalently, how can the second lowest eigenvalue of the signless Laplacian bound the second lowest eigenvalue of the laplacian? That a lower bound hold is obvious, but an upper bound?  
> **username_2**: @DelioM. Max Cut is first reduced to Min Bisection by adding more $n$ vertices and taking the complement of the resulting graph. So this reduction relates how close to bipartite one graph is to how connected another graph (related to the complement of the first).  

---

### Answer by username_1 on 2015-03-12. Score: 0

The actual proof of the $NP$-hardness of computing Cheeger constant ( or edge expansion) was given by [Kaibel in a technical report](http://arxiv.org/pdf/math/0112146v1.pdf) by a reduction from MAX Cut problem (See theorem 2). The proof is an extension of the proof of the $NP$-hardness of the equicut problem given by [Garey, Johnson, and Stockmeyer in Some simplified NP-complete
graph problems](http://www.sciencedirect.com/science/article/pii/0304397576900591).

V. Kaibel: On the expansion of graphs of 0/1-polytopes. Technical report
arXiv:math.CO/0112146, 2001

**EDIT**: The argument below is **incorrect**, as pointed out by Chekuri, and left for educational purpose.

This is not a reference as you requested but it explain the folklore status of the hardness result.

Here is a proof idea of the CoNP-completeness of deciding whether a connected cubic graph is edge-expander and therefore determining the Cheeger constant $h(G)$ is CoNP-hard.

The [minimum bisection problem is $NP$-complete](http://users.monash.edu/~normd/documents/Diaz-Do-Serna-Wormald-02.pdf) for connected cubic graphs. Here we want to decide whether a graph $G$ with an integer $k$ can be partitioned into two equal size parts such that the number of cut edges is less than $k$.

Note the complement of this problem is equivalent to deciding whether the graph $G$ is expander or not ( every balanced partition of $V$ has cut edges more than $k$).

P.S. Arora in this seminar states that it's $CoNP$-hard to recognize $\alpha$-expander graph ( edge-expansion). <http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx>

> **Comments:**
> **username_2**: This proof doesn't work either, because the size of the min bisection does not say anything about the edge expansion by itself. For example, a disconnected graph on $2n$ vertices can have minimum bisection $(n-2)^2$.  
> **username_1**: The graph $G$ is connected cubic graph and for this class minimum bisection problem is NP-complete.  
> **username_1**: @SashoNikolov I never seen anyone interested in the expansion of disconnected graphs.  
> **username_1**: Aurora in this seminar states that it's $CoNP$-hard to recognize $\alpha$-expander graph ( edge-expansion).  http://www.cs.princeton.edu/~zdvir/apx11slides/arora-slides.pptx  
> **username_2**: Arora, not Aurora. I do not doubt that deciding $h(G) \geq \alpha$ is coNP hard. But in two answers you have given neither a reference with proof, nor a proof. The disconnected graphs are only to show you that your arguments are bogus. Your "fix" dosn't work either. I can easily show you a connected cubic graph with large minimum bisection and Cheeger constant arbitrarily close to zero. The two problems are related but **not** in the trivial way you are suggesting.  
> **username_1**: @SashoNikolov Please show me those connected bridgeless cubic graphs and I will send you $100 if I get convinced.  
> **username_3**: @MohammadAl-Turkistany: Take two connected bridgeless cubic graphs that are expanders, one with 2n vertices and the other with n vertices and connect them with three edges by adding some 3 new vertices on each side via sub-dividing 3 edges. Now the min-bisection is going to be large ($\Omega(n)$) because you have to cut off a good chunk of the larger expander but the expansion is small because you can split the two expanders by cutting just 3 edges.  
> **username_1**: @ChandraChekuri Thank you. I am convinced and I will modify the answer.  
> **username_2**: Does Chandra get my $100 now?  
> **username_1**: You can not give him what you did not win :)  
> **username_2**: To be fair, Kaibel's writeup proves that the Garey, Johnson and Stockmeyer reduction from Max Cut to Min Bisection produces a graph in which the sparsest cuts are bisections.  

---

