7

As an extension to the question posed recently by Bulatov, I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent set.

Community
  • 1
ipsofacto
  • 348
  • 1
  • 5
  • The wikipedia article http://en.wikipedia.org/wiki/Perfect_graph says that for all perfect graphs there is a polynomial algorithm for the graph coloring problem, maximum clique problem, and maximum independent set problem. Is this you are looking for? – Marc Bury Mar 05 '11 at 00:04
  • 1
    Not quite. The algorithms known to solve maximum independent set use semidefinite programming. But, for a sub-class of perfect graphs, say chordal graphs, there is a simple combinatorial algorithm based on perfect-elimination orders. It is an open question to come up with a combinatorial algorithm to compute IS of perfect graphs. So the question is what are the maximal, by inclusion for which such algorithms are known -- that are purely combinatorial. – ipsofacto Mar 05 '11 at 01:02
  • 1
    When you refer to other questions next time, please include links to make it easier to follow. Don’t be lazy! – Tsuyoshi Ito Mar 05 '11 at 01:24
  • It is helpful if you post directly your current information background about your question. In particular for someone who isn't familiar with your topic (like me) :) – Marc Bury Mar 05 '11 at 01:50
  • Apologies. I'm still figuring out how to use this forum. – ipsofacto Mar 05 '11 at 02:01
  • 2
    I've recently thought about the same question, but haven't managed to google a list. Perhaps ISGCI (Information System on Graph Classes and their Inclusions) may be helpful. Here, http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_56.html, are all known maximal subclasses of perfect graphs, including whether the IS problem is in P or NP-C (with a reference to a paper from where one could dig out what algorithm has been used). – Standa Zivny Mar 05 '11 at 13:46
  • 1
    Some of the responses to http://cstheory.stackexchange.com/questions/2503/maximal-classes-for-which-largest-independent-set-can-be-found-in-polynomial-time might also be useful, for instance Ernst de Ridder's explanation of some of the less well known features of the ISGCI Java tool. – András Salamon Mar 06 '11 at 21:38

1 Answers1

4

One springs to mind and is listed as a maximal subclass in ISGCI, which surprised me: perfect claw-free graphs (a.k.a. perfect quasi-line graphs). This was done by Minty for all claw-free graphs around 1980. But a couple of other algorithms for claw-free graphs, one recently in SODA 2011 that is $O(n^3)$ by Faenza, Oriolo, and Stauffer, use the Chudnovsky-Seymour structural characterization of these graphs to reduce the problem to line graphs (and therefore maximum matching) in a fairly straightforward way. If you're only looking at perfect claw-free graphs, then the earlier characterization by Maffray and Reed is sufficient (and the reduction to line graphs is more obvious).

Andrew D. King
  • 1,573
  • 10
  • 19