Speaker: Prof. Dr. Oliver Schaudt (RWTH Aachen)

Title: A 7/3-Approximation Algorithm for Cluster Vertex Deletion

Abstract:
The cluster vertex deletion problem is to delete a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. In other words, the remaining graph is the disjoint union of complete graphs, so-called clusters. This problem is a special case of the vertex cover problem on a 3-uniform hypergraph, and thus has a straightforward 3-approximation algorithm. Very recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the problem.
Our main result is a 7/3-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp constrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee.

Joint work with Samuel Fiorini and Gwenael Joret.