An O(n2logn) algorithm for the weighted stable set problem in claw-free graphs.

A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three. Through this decomposition, the MWSS problem can be solved in O (| V | (| V | log | V | + | E |)) time. In this paper, we describe a direct decomposition of a claw-free graph into {claw, net}-free strips and strips with stability number at most three which can be performed in O (| V | 2) time. In two companion papers we showed that the MWSS problem can be solved in O (| E | log | V |) time in claw-free graphs with α (G) ≤ 3 and in O (| V | | E |) time in {claw, net}-free graphs with α (G) ≥ 4 . These results prove that the MWSS problem in a claw-free graph can be solved in O (| V | 2 log | V |) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs. [ABSTRACT FROM AUTHOR]