11 papers
Kernelization of 2-Club Cluster Edge Deletion on Interval Graphs
Ajinkya Gaikwad
The \emph{-Club Cluster Edge Deletion} problem asks whether, given a graph and an integer , one can delete at most edges so that every remaining connected component h…
Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size
Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admit…
Parameterized Complexity of Edge-Constrained Graph Partitioning
Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We…
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…
On the Parameterized Complexity of -Club Cluster Edge Deletion
Ajinkya Gaikwad
We study the parameterized and kernelization complexity of the \emph{\textsc{-Club Cluster Edge Deletion}} problem, a distance-bounded generalization of \emph{\textsc{Cluster Ed…