4 papers · 1 filter
On the Structural Parameterizations of 2-Club with Triangle Constraints
Ashwin Jacob, Diptapriyo Majumdar, Raghav Sakhuja
Given an undirected graph G = (V, E) and an integer k, the s-Club asks if Gcontains a vertex subset S of at least k vertices such that G[S] has diameter at most s. Recently, Vertex…
A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
Ashwin Jacob, Diptapriyo Majumdar, Meirav Zehavi
The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of…
A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar
Vertex deletion to hereditary graph class is well-studied in parameterized complexity. Vertex deletion to the scattered graph classes has gained attention in recent years. In this…
Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar +2
We consider structural parameterizations of the fundamental Dominating Set problem and its variants in the parameter ecology program. We give improved FPT algorithms and lower boun…