5 papers
Hardness and Tractability of T_{h+1}-Free Edge Deletion
Ajinkya Gaikwad, Soumen Maity, Leeja R
We study the parameterized complexity of the T(h+1)-Free Edge Deletion problem. Given a graph G and integers k and h, the task is to delete at most k edges so that every connected…
Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
Ajinkya Gaikwad, Hitendra Kumar, S. Padmapriya +3
We study a family of graph modification problems called the F-Vertex Splitting problem. Given a graph G, the task is to determine whether G can be transformed into a graph G-prime…
Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
Ajinkya Gaikwad
We study the parameterized and kernelization complexity of the s-Club Cluster Edge Deletion problem, a distance-bounded generalization of Cluster Edge Deletion. Given a graph G = (…
MaxMin Separation Problems: FPT Algorithms for -Separator and Odd Cycle Transversal
Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity +2
In this paper, we study the parameterized complexity of the MaxMin versions of two fundamental separation problems: Maximum Minimal -Separator and Maximum Minimal Odd Cycle Tra…
Parameterized Algorithms for Editing to Uniform Cluster Graph
Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity
We study the parameterized complexity of transforming graphs into Uniform Cluster graphs, where each component is an equal-sized clique. We consider Uniform Cluster Vertex Deletion…