20
$\begingroup$

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!

$\endgroup$
2
  • 3
    $\begingroup$ that's a nice question. Do the approximations have anything to do with sparsest cut methods ? $\endgroup$ – Suresh Venkat Oct 14 '11 at 3:32
  • 1
    $\begingroup$ 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? $\endgroup$ – yberman Apr 5 '16 at 14:59
11
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.