***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday April 21st, 3:00 in Fine Hall 224.
 
Speaker: Oliver Schaudt (Köln)

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

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.

                       -----------

Next week: Sergey Norin

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)