1 citations · 1 across the 18 of their papers we have counts for
19 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…
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…
Offensive Alliances in Graphs
Ajinkya Gaikwad, Soumen Maity
A set of vertices is an offensive alliance in an undirected graph if each has at least as many neighbours in as it has neighbours (includin…
Parameterized Complexity of Upper Edge Domination
Ajinkya Gaikwad, Soumen Maity
In this paper we study a maximization version of the classical Edge Dominating Set (EDS) problem, namely, the Upper EDS problem, in the realm of Parameterized Complexity. In this p…
Maximum Minimal Feedback Vertex Set: A Parameterized Perspective
Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity +2
In this paper we study a maximization version of the classical Feedback Vertex Set (FVS) problem, namely, the Max Min FVS problem, in the realm of parameterized complexity. In this…
Parameterized Algorithms for Locally Minimal Defensive Alliance
Ajinkya Gaikwad, Soumen Maity, Saket Saurabh
A set of vertices of a graph is a \emph{defensive alliance} if, for each element of , the majority of its neighbours are in . We consider the notion of local minimality i…
Globally Minimal Defensive Alliances: A Parameterized Perspective
Ajinkya Gaikwad, Soumen Maity
A defensive alliance in an undirected graph is a non-empty set of vertices satisfying the condition that every vertex has at least as many neighbours (includ…
Defensive Alliances in Graphs
Ajinkya Gaikwad, Soumen Maity
A set of vertices of a graph is a defensive alliance if, for each element of , the majority of its neighbours are in . We study the parameterized complexity of the Defens…
The Harmless Set Problem
Ajinkya Gaikwad, Soumen Maity
Given a graph , a threshold function and an integer , we study the Harmless Set problem, where the goal is to find a subset of vertic…
On Structural Parameterizations of the Offensive Alliance Problem
Ajinkya Gaikwad, Soumen Maity
The Offensive Alliance problem has been studied extensively during the last twenty years. A set of vertices is an offensive alliance in an undirected graph …
Parameterized Complexity of Locally Minimal Defensive Alliances
Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi
A set of vertices of a graph is a defensive alliance if, for each element of , the majority of its neighbours is in . We consider the notion of local minimality in this p…
Edge Deletion to Restrict the Size of an Epidemic
Ajinkya Gaikwad, Soumen Maity
Given a graph , a set of forbidden subgraphs, we study -Free Edge Deletion, where the goal is to remove minimum number of edges such that the re…
The Satisfactory Partition Problem
Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi
The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at l…