Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs

Abstract The well-known Cluster Vertex Deletion problem (cluster-vd) 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 G - S is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H -free graphs is polynomially solvable and for which it is NP NP -complete. Moreover, in the NP NP -completeness cases, cluster-vd 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 cluster-vd, the Connected Cluster Vertex Deletion problem (connected cluster-vd), in which the set S has to induce a connected subgraph of G. It turns out that connected cluster-vd 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.