Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time
Minty has shown that the Maximum Weight Stable Set (MWS) Problem can be solved in polynomial time when restricted to claw-free graphs. We show that the structure of graphs being both claw-free and co-claw-free is very simple which implies bounded clique width for this graph class. It is known that for graph classes of bounded clique width (assuming that k-expressions can be determined in linear time), there are linear time algorithms for all problems expressible in Monadic Second Order Logic with quantification only over vertex sets. The problems MWS, Maximum Clique, Domination and Steiner Tree, for example, are expressible in this way. Moreover, we describe the structure of prime graphs being both H- and (H) over bar -free for any four-vertex graph H and obtain bounded clique width for these graph classes except the 2K(2)- and C-4-free graphs. (C) 2002 Elsevier Science B.V. All rights reserved.
linear time algorithms monadic second order logic prime graphs modules in graphs modular decomposition clique width of graphs maximum stable set computational complexity