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.
Is the Cheeger constant $\mathsf{NP}$-hard?
reference request;graph theory;spectral graph theory
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.