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.