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.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ 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? $\endgroup$– Marc BuryMar 5, 2011 at 0:04
-
1$\begingroup$ 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. $\endgroup$– ipsofactoMar 5, 2011 at 1:02
-
1$\begingroup$ When you refer to other questions next time, please include links to make it easier to follow. Don’t be lazy! $\endgroup$– Tsuyoshi ItoMar 5, 2011 at 1:24
-
2$\begingroup$ 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). $\endgroup$– Standa ZivnyMar 5, 2011 at 13:46
-
1$\begingroup$ 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. $\endgroup$– András SalamonMar 6, 2011 at 21:38
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
0
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).
