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".
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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.
-
2$\begingroup$ My paper which uses the edge expansion hardness is the one below 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. $\endgroup$ Commented Mar 12, 2015 at 3:15
-
$\begingroup$ Thanks! So technically speaking the hardness of determining the Cheeger constant is unproven in the literature? $\endgroup$– Delio M.Commented Mar 12, 2015 at 18:59
-
3$\begingroup$ @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. $\endgroup$ Commented Mar 12, 2015 at 23:49
-
$\begingroup$ 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? $\endgroup$– Delio M.Commented Apr 4, 2015 at 1:21
-
$\begingroup$ @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). $\endgroup$ Commented Aug 18, 2018 at 21:41
$\begingroup$
$\endgroup$
11
The actual proof of the $NP$-hardness of computing Cheeger constant ( or edge expansion) was given by Kaibel in a technical report 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.
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 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
answered Mar 12, 2015 at 7:12
-
$\begingroup$ 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$. $\endgroup$ Commented Mar 12, 2015 at 7:29
-
$\begingroup$ The graph $G$ is connected cubic graph and for this class minimum bisection problem is NP-complete. $\endgroup$ Commented Mar 12, 2015 at 7:30
-
1$\begingroup$ @SashoNikolov I never seen anyone interested in the expansion of disconnected graphs. $\endgroup$ Commented Mar 12, 2015 at 9:11
-
1$\begingroup$ 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. $\endgroup$ Commented Mar 12, 2015 at 14:16
-
4$\begingroup$ @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. $\endgroup$ Commented Mar 12, 2015 at 14:56