2024/02/07 by Hoàng-Oanh Le, Le, Hoang-Oanh, Van Bang Lê +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2402.04931
openalex publication_date 2024/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.