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

CC BY-SA 2.5
2011-03-07T05:52:12.373Z
2011-03-07T05:52:12.373Z
Andrew D. King
<p>As an extension to the <a href="https://cstheory.stackexchange.com/questions/5269/sdp-relaxation-of-independent-set">question posed recently by Bulatov</a>, I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent set.</p>

CC BY-SA 2.5
2011-03-05T00:04:38.077Z
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
CC BY-SA 2.5
2011-03-05T01:02:42.010Z
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
CC BY-SA 2.5
2011-03-05T01:24:40.723Z
When you refer to other questions next time, please include links to make it easier to follow.  Don’t be lazy!
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-05T01:50:25.107Z
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
CC BY-SA 2.5
2011-03-05T02:01:09.377Z
Apologies. I'm still figuring out how to use this forum.
ipsofacto
CC BY-SA 2.5
2011-03-05T13:46:33.513Z
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
CC BY-SA 2.5
2011-03-06T21:38:27.043Z
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
<ds.algorithms><graph-theory><graph-algorithms>
Combinatorial Independent set Algorithms for sub-classes of perfect graphs
ipsofacto
# Combinatorial Independent set Algorithms for sub-classes of perfect graphs

(Asked by: username_0 on 2011-03-04)

As an extension to the [question posed recently by Bulatov](https://cstheory.stackexchange.com/questions/5269/sdp-relaxation-of-independent-set), I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent set.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: When you refer to other questions next time, please include links to make it easier to follow.  Don’t be lazy!  
> **username_1**: 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) :)  
> **username_0**: Apologies. I'm still figuring out how to use this forum.  
> **username_3**: 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).  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2011-03-07. Score: 4 | Accepted answer

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


---

