Shooting at seagulls - the problem of hitting induced three-vertex-paths in a graph

Shooting at seagulls - the problem of hitting induced three-vertex-paths in a graph

-
Oliver Schaudt , Universität zu Köln
Fine Hall 224

I'll talk about the problem of hitting all induced three-vertex-paths in a graph by a minimum weight vertex subset. This is the so-called cluster vertex deletion problem, as a graph without any induced three-vertex-path is just the disjoint union of complete graphs. While this problem has been studied intensively regarding fixed-parameter tractability, not much was known about approximation algorithms. Only recently You et al. showed that there is a 2.5-approximation algorithm in the unweighted case. We push this factor down to 2.25, even in the weighted setting. Our method uses a combination of local ratio and primal-dual techniques, and graph theory. This brings us closer to the factor of 2, which would be optimal assuming the unique-games conjecture holds. I'll also mention the problem of hitting longer paths in graphs and related conjectures. Joint work with Samuel Fiorini and Gwenael Joret.