Dipartimento di Ingegneria informatica, automatica e gestionale

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|2log|V|) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs.