A reduction algorithm for the weighted stable set problem in claw-free graphs

In this article the Lovász–Plummer clique reduction   is extended to the weighted case and used to find a maximum weight stable set in a claw-free graph GG with nn nodes in O(n2(n2+L(n)))O(n2(n2+L(n))) time, where L(n)L(n) is the complexity of finding a maximum weight augmenting path in a line graph HH with nn nodes. The best algorithm known to date to solve the latter problem is Gabow’s maximum weight matching algorithm (applied to the root graph of HH) which has a complexity of O(n2logn)O(n2logn). It follows that our algorithm can produce a maximum weight stable set in a claw-free graph in O(n4logn)O(n4logn) time.