21

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!

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Joseph O'Rourke
  • 3,753
  • 23
  • 41
  • 3
    that's a nice question. Do the approximations have anything to do with sparsest cut methods ? – Suresh Venkat Oct 14 '11 at 03:32
  • 1
    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 Apr 05 '16 at 14:59

2 Answers2

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.

Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115
  • Can't you just make any graph regular by adding self-loops? – Mahdi Cheraghchi Oct 14 '11 at 20:40
  • 2
    @MCH that way odd degree vertices remain odd degree and even degree vertices remain even degree – Sasho Nikolov Oct 15 '11 at 16:29
  • 1
    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 Oct 17 '11 at 13:41
5

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.

Aaron Sterling
  • 6,994
  • 6
  • 42
  • 74
Robert Krauthgamer
  • 51
  • 1