Parameterized Algorithms for Editing to Uniform Cluster Graph

Abstract

Graph modification problems, which involve transforming graphs through vertex or edge operations, are pivotal in theoretical computer science and parameterized complexity. Given a graph G=(V,E) and an integer k∈N, we study Uniform Cluster Vertex Deletion (resp. Uniform Cluster Edge Deletion), where the goal is to remove at most k vertices (resp. edges) such that the connected components of the resulting graph are equal-sized cliques. Graphs satisfying this property are referred to as uniform cluster graphs. We present a kernelization result with a vertex kernel of size O(k3) for Uniform Cluster Vertex Deletion (UCVD) and an FPT algorithm running in O∗(2k) time, improving upon the best-known results in the literature. We also provide a linear vertex kernel for Uniform Cluster Edge Deletion (UCED) of size 6k. Through this work, we resolve several open questions posed by Misra, Mittal, Saurabh & Thakkar [ISAAC 2023] regarding the parameterized complexity of these problems, thus offering a comprehensive view of the landscape surrounding uniform cluster graphs.