<p>Notice that approximating sparsest cut to within $\alpha$ gives a $2\alpha$ approximation for the Cheeger constant as defined. Here are some papers that give constant approximation algorithms for sparsest cut in restricted graphs:</p>

<ol>
<li><p>Bounded genus: <a href="http://dl.acm.org/citation.cfm?id=1873619" rel="nofollow">http://dl.acm.org/citation.cfm?id=1873619</a></p></li>
<li><p>Bounded treewidth: <a href="http://arxiv.org/abs/1006.3970" rel="nofollow">http://arxiv.org/abs/1006.3970</a></p></li>
</ol>

<p>Furthermore, <a href="http://arxiv.org/abs/1006.3970v2" rel="nofollow">http://arxiv.org/abs/1006.3970v2</a> proves that sparsest cut is NP-hard for graphs with pathwidth 2, and has quite a few more references to approximating sparsest cut on restricted instances.</p>

<p>I would assume that for all classes of graphs mentioned in the paper, no exact algorithms are known (as they're interested in approximations). In particular, if sparsest cut is NP-hard for graphs with pathwidth 2, it's also NP-hard for graphs of treewidth 2, and cutwidth 2. I suppose that doesn't give quite a lot of room.. maybe there is another better parameterization for sparsest cut.</p>

<p>I am pretty sure that sparsest cut is NP-hard on regular graphs but can't find a reference.</p>

<hr>

<p>Per noticed that I wasn't careful when I looked at the papers above. The hardness result is for nonuniform sparsest cut. Computing uniform sparsest cut or the Cheeger constant is easy on trees (WLOG the optimal cut separates a subtree). With a little more work that gives a dynamic programming algorithm for computing the Cheeger constant on bounded treewidth graphs. </p>

<p>Table 1 in paper 2 above also mentions a result that gives a constant approximation for graphs with an excluded minor.</p>

<p>For bounded genus graphs, the best that seems to be known is a constant approximation (paper 1 above gives $O(\sqrt{\log g})$ where $g$ is the genus.</p>

CC BY-SA 3.0
2011-10-14T20:40:56.917Z
Can't you just make any graph regular by adding self-loops?
Mahdi Cheraghchi
CC BY-SA 3.0
2011-10-15T16:29:43.807Z
@MCH that way odd degree vertices remain odd degree and even degree vertices remain even degree
Sasho Nikolov
CC BY-SA 3.0
2011-10-17T13:41:03.370Z
The hardness result you mention for pathwidth 2 is for *non-uniform* sparsest cut, which is not that relevant for the Cheeger constant.  Indeed, as far as I can see, computing either the uniform sparsest cut or the Cheeger constant exactly in graphs of bounded treewidth is easy.
Per Austrin
CC BY-SA 3.0
2011-10-14T03:39:30.697Z
2011-10-17T14:55:30.170Z
2011-10-17T14:55:30.170Z
Sasho Nikolov
<p>For exact solution in planar graphs, see <a href="http://dl.acm.org/citation.cfm?doid=167088.167284" rel="nofollow">Park and Phillips, STOC 93</a>. This is essentially for the uniform-demands sparsest-cut, with the minor difference that their denominator is |S| instead of |S|*|V-S|. As pointed out by Per, the case of non-uniform demands is different.</p>

CC BY-SA 3.0
2011-10-17T14:52:48.293Z
2011-10-17T16:33:44.717Z
2011-10-17T16:33:44.717Z
Robert Krauthgamer
<p>Computing the <a href="http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29" rel="noreferrer">Cheeger constant of a graph</a>, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated.  I am interested to learn if exact polynomial algorithms
are known for special classes of graphs.
For example, is it still NP-complete for <a href="http://en.wikipedia.org/wiki/Regular_graph" rel="noreferrer">regular graphs</a>?
For <a href="http://en.wikipedia.org/wiki/Distance-regular_graph" rel="noreferrer">distance-regular graphs</a>?
(I have not studied the existing NP-completeness proofs to examine their assumptions.)
Literature pointers appreciated&mdash;thanks!</p>

CC BY-SA 3.0
2011-10-14T03:32:36.103Z
that's a nice question. Do the approximations have anything to do with sparsest cut methods ?
Suresh Venkat
CC BY-SA 3.0
2016-04-05T14:59:18.817Z
I know this is an old question, but I was wondering if anyone knew of a polynomial time approximation for general graphs that get the constant within some fixed percentage?
yberman
<ds.algorithms><reference-request><graph-algorithms>
Computing the Cheeger constant: feasible for which classes?
Joseph O'Rourke
# Computing the Cheeger constant: feasible for which classes?

(Asked by: username_0 on 2011-10-14)

Computing the [Cheeger constant of a graph](http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29), also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated. I am interested to learn if exact polynomial algorithms
are known for special classes of graphs.
For example, is it still NP-complete for [regular graphs](http://en.wikipedia.org/wiki/Regular_graph)?
For [distance-regular graphs](http://en.wikipedia.org/wiki/Distance-regular_graph)?
(I have not studied the existing NP-completeness proofs to examine their assumptions.)
Literature pointers appreciated—thanks!

**Tags:** ds.algorithms, reference-request, graph-algorithms
> **Comments:**
> **username_1**: that's a nice question. Do the approximations have anything to do with sparsest cut methods ?  
> **username_2**: I know this is an old question, but I was wondering if anyone knew of a polynomial time approximation for general graphs that get the constant within some fixed percentage?  

---

## 2 answers

### Answer by username_3 on 2011-10-14. Score: 11

Notice that approximating sparsest cut to within $\alpha$ gives a $2\alpha$ approximation for the Cheeger constant as defined. Here are some papers that give constant approximation algorithms for sparsest cut in restricted graphs:

1. Bounded genus: <http://dl.acm.org/citation.cfm?id=1873619>
2. Bounded treewidth: <http://arxiv.org/abs/1006.3970>

Furthermore, <http://arxiv.org/abs/1006.3970v2> proves that sparsest cut is NP-hard for graphs with pathwidth 2, and has quite a few more references to approximating sparsest cut on restricted instances.

I would assume that for all classes of graphs mentioned in the paper, no exact algorithms are known (as they're interested in approximations). In particular, if sparsest cut is NP-hard for graphs with pathwidth 2, it's also NP-hard for graphs of treewidth 2, and cutwidth 2. I suppose that doesn't give quite a lot of room.. maybe there is another better parameterization for sparsest cut.

I am pretty sure that sparsest cut is NP-hard on regular graphs but can't find a reference.

---

Per noticed that I wasn't careful when I looked at the papers above. The hardness result is for nonuniform sparsest cut. Computing uniform sparsest cut or the Cheeger constant is easy on trees (WLOG the optimal cut separates a subtree). With a little more work that gives a dynamic programming algorithm for computing the Cheeger constant on bounded treewidth graphs.

Table 1 in paper 2 above also mentions a result that gives a constant approximation for graphs with an excluded minor.

For bounded genus graphs, the best that seems to be known is a constant approximation (paper 1 above gives $O(\sqrt{\log g})$ where $g$ is the genus.

> **Comments:**
> **username_4**: Can't you just make any graph regular by adding self-loops?  
> **username_3**: @MCH that way odd degree vertices remain odd degree and even degree vertices remain even degree  
> **username_5**: The hardness result you mention for pathwidth 2 is for *non-uniform* sparsest cut, which is not that relevant for the Cheeger constant.  Indeed, as far as I can see, computing either the uniform sparsest cut or the Cheeger constant exactly in graphs of bounded treewidth is easy.  

---

### Answer by username_6 on 2011-10-17. Score: 5

For exact solution in planar graphs, see [Park and Phillips, STOC 93](http://dl.acm.org/citation.cfm?doid=167088.167284). This is essentially for the uniform-demands sparsest-cut, with the minor difference that their denominator is |S| instead of |S|\*|V-S|. As pointed out by Per, the case of non-uniform demands is different.


---

