Parameterized Algorithms for Balanced Cluster Edge Modification Problems

We introduce Cluster Edge Modification problems with constraints on the size of the clusters and study their complexity. A graph G is a cluster graph if every connected component of G is a clique. In a typical Cluster Edge Modification problem such as the widely studied Cluster Editing, we are given a graph G and a non-negative integer k as input, and we have to decide if we can turn G into a cluster graph by way of at most k edge modifications -- that is, by adding or deleting edges. In this paper, we study the parameterized complexity of such problems, but with an additional constraint: The size difference between any two connected components of the resulting cluster graph should not exceed a given threshold. Depending on which modifications are permissible -- only adding edges, only deleting edges, both adding and deleting edges -- we have three different computational problems. We show that all three problems, when parameterized by k, admit single-exponential time FPT algorithms and polynomial kernels. Our problems may be thought of as the size-constrained or balanced counterparts of the typical Cluster Edge Modification problems, similar to the well-studied size-constrained or balanced counterparts of other clustering problems such as k-Means Clustering.