2 citations · 8 across the 13 of their papers we have counts for
16 papers · 1 filter
Packing Diverse Shortest Cycles
Akanksha Agrawal, Fedor V. Fomin, Petr A. Golovach +3
Bentert, Fomin, Golovach, Korhonen, Lochet, Panolan, Ramanujan, Saurabh, and Simonov (SODA 2025) initiated the parameterized study of Edge-Disjoint Shortest Cycle Packing: given a…
Path Contraction Faster than
Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov +2
A graph is contractible to a graph if there is a set , such that is isomorphic to . Here, is the graph obtained from by contracting all…
Odd Cycle Transversal on -free Graphs in Polynomial Time
Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov +3
An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycl…
Clustering What Matters: Optimal Approximation for Clustering with Outliers
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh +1
Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set of points and two integers and , the clustering with outliers aims…
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal, Dániel Marx, Daniel Neuen +1
A square coloring of a graph is a coloring of the square of , that is, a coloring of the vertices of such that any two vertices that are at distance at most in…
A Finite Algorithm for the Realizabilty of a Delaunay Triangulation
Akanksha Agrawal, Saket Saurabh, Meirav Zehavi
The \emph{Delaunay graph} of a point set is the plane graph with the vertex-set and the edge-set that contains if there exists a disc whos…
Parameterized Complexity of Minimum Membership Dominating Set
Akanksha Agrawal, Pratibha Choudhary, N. S. Narayanaswamy +2
Given a graph and an integer , the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set of such that for each ,…
Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov +4
For a graph class , the graph parameters elimination distance to (denoted by ) [Bulian and Dawar, Algorithmica, 2016], and -treewi…
FPT Algorithms for Conflict-free Coloring of Graphs and Chromatic Terrain Guarding
Akanksha Agrawal, Pradeesha Ashok, Meghana M Reddy +2
We present fixed parameter tractable algorithms for the conflict-free coloring problem on graphs. Given a graph , \emph{conflict-free coloring} of refers to coloring a…
On the Parameterized Complexity of Contraction to Generalization of Trees
Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale
For a family of graphs , the -Contraction problem takes as an input a graph and an integer , and the goal is to decide if there exists $S \subseteq E(G)…
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
Given a graph and a parameter , the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset of size at most that hits all induced cycl…
Polylogarithmic Approximation Algorithms for Weighted--Deletion Problems
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra +2
For a family of graphs , the canonical Weighted Vertex Deletion problem is defined as follows: given an -vertex undirected graph and a weight function $w: V…
Simultaneous Feedback Edge Set: A Parameterized Perspective
Akanksha Agrawal, Fahad Panolan, Saket Saurabh +1
In this paper we consider Simultaneous Feedback Edge Set (Sim-FES) problem. In this problem, the input is an -vertex graph , an integer and a coloring function ${\sf col}…
A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion
Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov +1
A graph is called a \emph{block graph} if each maximal -connected component of is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective o…
Simultaneous Feedback Vertex Set: A Parameterized Perspective
Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad +1
Given a family of graphs , a graph , and a positive integer , the -Deletion problem asks whether we can delete at most vertices from to obta…
Vertex Cover Gets Faster and Harder on Low Degree Graphs
Akanksha Agrawal, Sathish Govindarajan, Neeldhara Misra
The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set pr…