Parameterized algorithms for editing to uniform cluster graph

Abstract

This paper investigates the parameterized complexity of transforming graphs into Uniform Cluster graphs, where every component is an equal-sized clique. We consider several different graph editing operations and study multiple variants of this problem, including Uniform Cluster Vertex Deletion (UCVD), Uniform Cluster Edge Deletion (UCED), Uniform Cluster Exclusive Vertex Splitting (UCEVS) and Uniform Cluster Inclusive Vertex Splitting (UCIVS).For UCVD, we provide a vertex kernel of size O(k3) and an FPT algorithm with running time 2k·nO(1) improving upon the 3k·nO(1) time algorithm known in the literature. We obtain linear vertex kernels of size 6k for UCED. In addition to kernelization result, we present a 1.47k·nO(1)-time algorithm for UCED, which improves the existing 2k·nO(1)-time algorithm. This algorithm is heavily inspired by the approach of Bo¨cker and Damaschke [IPL 2011] for Cluster Edge Deletion. Collectively, these results improve upon existing work and answer multiple open questions posed by Misra, Mittal, Saurabh, and Thakkar [ISAAC 2023]. We also construct a subexponential algorithm for UCED on graphs with minimum degree αn. We also explore a relatively new graph editing operation known as vertex splitting. Based on two variants of this operation, we study Uniform Cluster Inclusive Vertex Splitting (UCIVS) and Uniform Cluster Exclusive Vertex Splitting (UCEVS). A vertex split is an operation in which a vertex v is replaced by two copies, with the combined neighborhood of these copies being identical to the original neighborhood of v. We provide vertex kernels of size 4k for both UCEVS and UCIVS.