Akanksha Agrawal

Dr. Akanksha Agrawal

orcid

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
8 December 2018 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PDF file
AAAkanksha Agrawal
Akanksha Agrawal
DLDaniel Lokshtanov
Daniel Lokshtanov
PMPranabendu Misra
Pranabendu Misra
SSSaket Saurabh
Saket Saurabh
MZMeirav Zehavi
Meirav Zehavi
Given a graph G and a parameter k , the C hordal V ertex D eletion (CVD) problem asks whether there exists a subset U ⊆ V ( G ) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O ( k 161 log 58 k ) and asked whether one can design a kernel of size O ( k 10 ) [Jansen an Pilipczuk, SODA 2017]. While we do not completely resolve this question, we design a significantly smaller kernel of size O ( k 12 log 10 k ), inspired by the O ( k 2 ) -size kernel for F eedback V ertex S et [Thomassé, TALG 2010]. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.

22 March 2016
Verified
Book Chapter
Closed access
PDF file
AAAkanksha Agrawal
Akanksha Agrawal
SKSudeshna Kolay
Sudeshna Kolay
DLDaniel Lokshtanov
Daniel Lokshtanov
SSSaket Saurabh
Saket Saurabh

2 January 2019
Verified
Book Chapter
Closed access
AAAkanksha Agrawal
Akanksha Agrawal
PMPranabendu Misra
Pranabendu Misra
SSSaket Saurabh
Saket Saurabh
MZMeirav Zehavi
Meirav Zehavi
Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S ⊆ V(G) of size at most k such that G–S is an interval graph. This problem is known to be NP-complete [Yannakakis, STOC’78]. Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10knO(1) [Cao and Marx, SODA’14]. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this paper, we settle this problem in the affirmative. We also introduce a “bounded intersection” variant of the classical Two Families theorem of Bollobás. We believe this result will find further applications in combinatorics and algorithm design.

1 March 2018 in Journal of Computer and System Sciences
Verified
Journal Article
Closed access
AAAkanksha Agrawal
Akanksha Agrawal
SSSaket Saurabh
Saket Saurabh
RSRoohani Sharma
Roohani Sharma
MZMeirav Zehari
Meirav Zehari

10 February 2020 in Algorithmica
Verified
Journal Article
Closed access
PDF file
AAAkanksha Agrawal
Akanksha Agrawal
PJPallavi Jain
Pallavi Jain
LKLawqueen Kanesh
Lawqueen Kanesh
SSSaket Saurabh
Saket Saurabh

4 January 2017
Verified
Conference Paper
Closed access
AAAkanksha Agrawal
Akanksha Agrawal
DLDaniel Lokshtanov
Daniel Lokshtanov
PMPranabendu Misra
Pranabendu Misra
SSSaket Saurabh
Saket Saurabh
MZMeirav Zehari
Meirav Zehari