Solving the maximum weighted stable set problem in claw-free graphs via decomposition
Presented by Dr. Yuri FAENZA
Type: Oral presentation
Track: Algorithmic Graph Theory
We propose an algorithm for solving the maximum weighted stable set problem in 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 we also present in this talk. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is coupled with fast algorithm that actually produces the decomposition of the input graph.