1 citations · 1 across the 10 of their papers we have counts for
12 papers · 1 filter
Eccentricity Shortest Path: the structural parameter landscape
Anand Babu, Ashwin Jacob, Hitendra Kumar +1
The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer , whether some shortest path is within distance of every vertex. We study its…
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.…
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…
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…
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study the parameterized complexity of two classic problems on directed graphs: Hamiltonian Cycle and its generalization {\sc Longest Cycle}. Since 2008, it is known that Hamilto…
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…
Long Directed Detours: Reduction to -Disjoint Paths
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study an "above guarantee" version of the {\sc Longest Path} problem in directed graphs: We are given a graph , two vertices and of , and a non-negative integer $k…
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…
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…
Structural Parameterizations with Modulator Oblivion
Ashwin Jacob, Fahad Panolan, Venkatesh Raman +1
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems i…