Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 6 down vote favorite
1

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. Thanks in advance.

share|improve this question
The wikipedia article 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 Gillé Mar 5 '11 at 0: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 5 '11 at 1: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 5 '11 at 1:24
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, 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 5 '11 at 13:46
1  
Some of the responses to cstheory.stackexchange.com/questions/2503/… 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 6 '11 at 21:38
show 2 more comments

1 Answer

up vote 4 down vote accepted

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).

share|improve this answer
This sounds very interesting. thanks. – ipsofacto Mar 12 '11 at 2:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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