An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem
We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also intioduced in the present paper. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is, on the other hand, algorithmic, i.e. it is coupled with an O(n^3)-time procedure that actually produces the decomposition. We also believe that our algorithmic decomposition result is interesting on its own and might be also useful to solve othei' kind of problems on claw-free graphs.
soda11.pdf
Preprint
openaccess
490.77 KB
Adobe PDF
db57da619d5e42a5089795c6e3bb7c93