Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
<|reference_start|>Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs: The well-known Cluster Vertex Deletion problem (CVD) asks for a given graph $G$ and an integer $k$ whether it is possible to delete a set $S$ of at most $k$ vertices of $G$ such that the resulting graph $G-S$ is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs $H$ for which CVD on $H$-free graphs is polynomially solvable and for which it is NP-complete. Moreover, in the NP-completeness cases, CVD cannot be solved in sub-exponential time in the vertex number of the $H$-free input graphs unless the Exponential-Time Hypothesis fails. We also consider the connected variant of CVD, the Connected Cluster Vertex Deletion problem (CCVD), in which the set $S$ has to induce a connected subgraph of $G$. It turns out that CCVD admits the same complexity dichotomy for $H$-free graphs. Our results enlarge a list of rare dichotomy theorems for well-studied problems on $H$-free graphs.<|reference_end|>
@article{le2024complexity,
    title={Complexity of the (Connected) Cluster Vertex Deletion problem on
  $H$-free graphs},
    author={Hoang-Oanh Le, Van Bang Le},
    journal={arXiv preprint arXiv:2402.04931},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.04931},
    primaryClass={cs.DM cs.CC cs.DS math.CO}
}