16 citations · 25 across the 21 of their papers we have counts for
22 papers · 1 filter
On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs
Sourav Das, Ashwin Jacob, Arpit Kumar +1
In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges t…
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 the hereditary graph class has been well-studied in parameterized complexity. Vertex deletion in scattered graph classes has attracted attention in recent years.…
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 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.…
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…
Structural Parameterization of Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate structural parameterizations of two identification problems: LOCATING-DOMINATING SET and TEST COVER. In the first problem, an input is a graph on vertices an…
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…
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…
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar +1
We investigate fine-grained algorithmic aspects of identification problems in graphs and set systems, with a focus on Locating-Dominating Set and Test Cover. We prove the (tight) c…
Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G), and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists a set S \supseteq X with…
Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
Christian Komusiewicz, Diptapriyo Majumdar
Enumeration kernelization was first proposed by Creignou et al. [TOCS 2017] and was later refined by Golovach et al. [JCSS 2022] into two different variants: fully-polynomial enume…
Expansion Lemma -- Variations and Applications to Polynomial-Time Preprocessing
Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman
In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel - an instance equivalent to the input instanc…
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
We study the CONNECTED η-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subsete…
Deletion to Scattered Graph Classes II -- Improved FPT Algorithms for Deletion to Pairs of Graph Classes
Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman
Let be a hereditary graph class. The problem of deletion to , takes as input a graph and asks for a minimum number (or a fixed integer ) of vertices to be deleted fro…
Valued Authorization Policy Existence Problem: Theory and Experiments
Jason Crampton, Eduard Eiben, Gregory Gutin +2
Recent work has shown that many problems of satisfiability and resiliency in workflows may be viewed as special cases of the authorization policy existence problem (APEP), which re…
Deletion to Scattered Graph Classes I -- case of finite number of graph classes
Ashwin Jacob, Jari J. H. de Kroon, Diptapriyo Majumdar +1
Graph-modification problems, where we modify a graph by adding or deleting vertices or edges or contracting edges to obtain a graph in a {\it simpler} class, is a well-studied opti…
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
Carl Einarson, Gregory Gutin, Bart M. P. Jansen +2
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the -Edge-Connected and -Vertex-Connected VC problem (where is a fixe…
Parameterized Pre-coloring Extension and List Coloring Problems
Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak +1
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by : (1) Given a graph , a clique modu…
On the Approximate Compressibility of Connected Vertex Cover
Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh
The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundam…
Bounded and Approximate Strong Satisfiability in Workflows
Jason Crampton, Gregory Gutin, Diptapriyo Majumdar
There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specificat…
Tractability of Konig Edge Deletion Problems
Diptapriyo Majumdar, Rian Neogi, Venkatesh Raman +1
A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if in a given graph t…
Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels
R. Krithika, Diptapriyo Majumdar, Venkatesh Raman
The CONNECTED VERTEX COVER problem asks for a vertex cover in a graph that induces a connected subgraph. The problem is known to be fixed-parameter tractable (FPT), and is unlikely…