Structural Parameterization of Cluster Deletion

In the weighted Cluster Deletion problem we are given a graph with non-negative integral edge weights and the task is to determine, for a target value k, if there is a set of edges of total weight at most k such that its removal results in a disjoint union of cliques. It is well-known that the problem is FPT parameterized by k, the total weight of edge deletions. In scenarios in which the solution size is large, naturally one needs to drop the constraint on the solution size. Here we study weighted Cluster Deletion where there is no bound on the size of the solution, but the parameter captures structural properties of the input graph. Our main contribution is to classify the parameterized complexity of weighted Cluster Deletion with three structural parameters, namely, vertex cover, twin cover and neighborhood diversity. We show that the problem is FPT when parameterized by the vertex cover, whereas it becomes paraNP-hard when parameterized by the twin cover or the neighborhood diversity. To illustrate the applicability of our FPT result, we use it in order to show that the unweighted variant of the problem, Cluster Deletion, is FPT parameterized by the twin cover. This is the first algorithm with single-exponential running time parameterized by the twin cover. Interestingly, we are able to achieve an FPT result parameterized by the neighborhood diversity that involves an ILP formulation. In fact, our results generalize the parameterized setting by the solution size, as we deduce that both parameters, twin cover and neighborhood diversity, are linearly bounded by the number of edge deletions.