11 papers
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…
Polynomial Kernels for Spanning Tree with Diversity Requirements
Petr A. Golovach, Diptapriyo Majumdar, Saket Saurabh
Given a connected undirected graph , a spanning tree is a subgraph of such that and is a tree. A collection of spanning trees $T_1,\ldots,T_\ell…
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
Susobhan Bandopadhyay, Suman Banerjee, Diptapriyo Majumdar +1
We study the SHORTEST PATH problem with positive disjunctive constraints from the perspective of parameterized complexity. For positive disjunctive constraints, there are certain p…
On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
Susobhan Bandopadhyay, Aritra Banik, Diptapriyo Majumdar +1
Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A.…