# Computing the Cheeger constant: feasible for which classes?

Computing the Cheeger constant of a graph, 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? For distance-regular graphs? (I have not studied the existing NP-completeness proofs to examine their assumptions.) Literature pointers appreciated—thanks!

• that's a nice question. Do the approximations have anything to do with sparsest cut methods ? Oct 14, 2011 at 3:32
• 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? Apr 5, 2016 at 14:59

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.

• Can't you just make any graph regular by adding self-loops? Oct 14, 2011 at 20:40
• @MCH that way odd degree vertices remain odd degree and even degree vertices remain even degree Oct 15, 2011 at 16:29
• 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. Oct 17, 2011 at 13:41

For exact solution in planar graphs, see Park and Phillips, STOC 93. 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.