Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem   We give the first $2$-approximation algorithm for the cluster vertex deletion
problem. This is tight, since approximating the problem within any constant
factor smaller than $2$ is UGC-hard. Our algorithm combines the previous
approaches, based on the local ratio technique and the management of true
twins, with a novel construction of a 'good' cost function on the vertices at
distance at most $2$ from any vertex of the input graph.
  As an additional contribution, we also study cluster vertex deletion from the
polyhedral perspective, where we prove almost matching upper and lower bounds
on how well linear programming relaxations can approximate the problem.

7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
25
The categories of this paper are: patt-sol
16
The categories of this paper are: stat
34
The categories of this paper are: chem-ph
22
The categories of this paper are: chao-dyn
29
The categories of this paper are: funct-an
18
The categories of this paper are: econ
6
The categories of this paper are: astro-ph
9
The categories of this paper are: nlin
31
The categories of this paper are: ao-sci
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin
21
The categories of this paper are: adap-org
26
The categories of this paper are: bayes-an
3
The categories of this paper are: physics