An O(n2 log n) algorithm for the weighted stable set problem in claw-free graphs
成果类型：
Article
署名作者：
Nobili, Paolo; Sassano, Antonio
署名单位：
University of Salento; Sapienza University Rome
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01461-5
发表日期：
2021
页码：
409-437
关键词：
摘要：
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 alpha(G) <= 3 and in O(|V|root|E|) time in {claw, net}-free graphs with alpha(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.