Akanksha Agrawal
  • Home
  • Publications
  • Group
  • Grants & Acad. Services
  • Teaching
    • Approximation Algorithms
    • Advanced Data Structures & Algorithms
    • Fine Grained Algorithms & Complexity
    • Kernelization
    • Parameterized Algorithms
  • Selected Talks
  • Education
  • Home
  • Publications
  • Group
  • Grants & Acad. Services
  • Teaching
    • Approximation Algorithms
    • Advanced Data Structures & Algorithms
    • Fine Grained Algorithms & Complexity
    • Kernelization
    • Parameterized Algorithms
  • Selected Talks
  • Education

Invited Surveys

Distance From Triviality 2.0: Hybrid Parameterizations
 Akanksha Agrawal and M.S. Ramanujan     
                - IWOCA 2022


Parameterized Analysis of Art Gallery and Terrain Guarding

 Akanksha Agrawal and Meirav Zehavi        
                - CSR 2020

2023

Computing Square Coloring on Bounded-Treewidth and Planar Graphs
 Akanksha Agrawal , Daniel Marx, Daniel Neuen and Jasper Slusallek
                - SODA 2023

2022

Deleting, Eliminating and Decomposing to Hereditary Graph Classes Are All FPT Equivalent
​​ Akanksha Agrawal,   Lawqueen Kanesh, Daniel Lokshtanov,   Fahad Panolan,   Ramanujan M S, Saket Saurabh and Meirav Zehavi
                - SODA 2022

On Finding Short Reconfiguration Sequences Between Independent Sets 
​​ Akanksha Agrawal,    Soumita Hait and Amer Mouawad
                - ISAAC 2022

Parameterized  Complexity of Perfectly Matched Sets 
​​ Akanksha Agrawal,    Sutanay Bhattacharjee, Satyabrata Jana and Abhishek Sahu
                - IPEC 2022

A Finite Algorithm for the Realizability of a Delaunay Triangulation 
​​ Akanksha Agrawal,    Saket Saurabh and Meirav Zehavi
                - IPEC 2022

Parameterized Complexity of Minimum Membership Dominating Set
​​ Akanksha Agrawal,   Pratibha Choudhary, Narayanaswamy N S,  Nisha K K and Vijayaraghunathan Ramamoorthi
                - WALCOM 2022

Fine-grained Complexity of Rainbow Coloring and its Variants
Akanksha Agrawal
             - To appear in Journal of Computer and System Sciences

             - A preliminary version of this article appeared in  MFCS 2017

2021

​​An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
​​ Akanksha Agrawal,   Lawqueen Kanesh,   Fahad Panolan,   Ramanujan M S and Saket Saurabh 
                - STACS 2021

Refuting FPT Algorithms for Some  Parameterized Problems Under Gap-ETH
​​ Akanksha Agrawal,   Ravi Kiran Allumalla and Varun Teja Dhanekula
                - IPEC 2021

​
A Polynomial Kernel for Deletion to Ptolemaic Graphs
​​ Akanksha Agrawal,   Aditya Anand and Saket Saurabh  
                - IPEC 2021

​​​Simultaneous Feedback Vertex Set: A Parameterized Perspective
​​ Akanksha Agrawal,   Fahad Panolan,   Saket Saurabh and   Meirav Zehavi
               - Algorithmica 
               - A preliminary version of this article appeared in  ISAAC 2019

Paths to Trees and Cacti
Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh and Prafullkumar Tale
             - Theoretical Computer Science 

             - A preliminary version of this article appeared in  CIAC 2019

2020

​​On the Parameterized Complexity of Clique Elimination Distance
​​ Akanksha Agrawal and M. S. Ramanujan
                - IPEC 2020

Parameterized Complexity of Maximum Edge Colorable Subgraphs
 Akanksha Agrawal, Madhumita Kundu, Abhishek Sahu, Saket Saurabh and Prafullkumar Tale
                - COCOON 2020


Parameterized Analysis of Guarding Terrains
 Akanksha Agrawal, Sudeshna Kolay and Meirav Zehavi        
                - SWAT 2020


The Parameterized Complexity of Guarding Almost Convex Polygons
 Akanksha Agrawal, Kristine Knudsen, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi        
                - SoCG 2020


Parameterized Complexity of Conflict-free Matchings and Paths ​
Akanksha Agrawal,   Pallavi Jain, Lawqueen Kanesh and Saket Saurabh    
​               -   Algorithmica
               - A preliminary version of this article appeared in  MFCS 2019  ​​

Path Contraction Faster than 2^n
 Akanksha Agrawal,  Fedor Fomin, Daniel Lokshtanov,   Saket Saurabh and Prafullkumar Tale       
​
               -   SIAM Journal on Discrete Mathematics  
               - A preliminary version of this article appeared in   ICALP 2019  ​​

Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi
​               -   Transactions on Algorithms   (to appear)
               - A preliminary version of this article appeared in   APPROX 2019  ​​​

2019

Parameterized Streaming Algorithms for Min-Ones d-SAT
Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman and Saket Saurabh         
                - FSTTCS 2019

Parameterized Dichotomy of Deletion to List Matrix-Partition for low-order Matrices 
Akanksha Agrawal,   Sudeshna Kolay, Jayakrishnan Madathil  and Saket Saurabh          
                - ISAAC 2019

Parameterized Complexity of Conflict-free Matchings and Paths 
Akanksha Agrawal,  Pallavi Jain, Lawqueen Kanesh and Saket Saurabh          
                - MFCS 2019

Path Contraction Faster than 2^n
 Akanksha Agrawal,  Fedor Fomin, Daniel Lokshtanov,   Saket Saurabh and Prafullkumar Tale          
               -  ICALP 2019

Connecting  the Dots (with Minimum Crossings)
 Akanksha Agrawal, Grzegorz Guspiel, Jayakrishnan Madathil,   Saket Saurabh and Meirav Zehavi           
                - SoCG 2019


Quadratic Vertex Kernel for Split Vertex Deletion
 Akanksha Agrawal, Sushmita Gupta, Pallavi Jain and R Krithika         
                - CIAC 2019 ​


Interval Vertex Deletion Admits a Polynomial Kernel
 Akanksha Agrawal, Pranabendu Misra, Saket Saurabh and Meirav Zehavi             
                - SODA 2019 ​


Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi 
                 - Transactions on Algorithms  

                 - A preliminary version of this article appeared in   SODA  2017

Split Contraction: The Untold Story
Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi
               -   Transactions on Computation Theory  

               - A preliminary version of this article appeared in   STACS 2017

On the Parameterized Complexity of Contraction to Generalization of Trees
Akanksha Agrawal, Saket Saurabh, and Prafullkumar Tale 
               -   Theory of Computing Systems   
               - A preliminary version of this article appeared in   IPEC 2017  ​

2018

​Parameterized algorithms for deletion to classes of acyclic digraphs
Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi
                - Theory of Computing Systems, 2018


Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi
                  -APPROX 2018


Erdos-Posa Property of Obstructions to Interval Graphs
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi
                  -STACS 2018


Conflict Free Feedback Vertex Set: A Parameterized Dichotomy 
Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Daniel Lokshtanov, and Saket Saurabh
                  -MFCS 2018


Exploring the Kernelization   Borders for Hitting Cycles
Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra, and Saket Saurabh
                  -IPEC 2018


Hitting and Covering Partially
Akanksha Agrawal, Pratibha Choudhary, Pallavi Jain, Lawqueen Kanesh, Vibha Shalot, and Saket Saurabh
                  -COCOON    2018


Kernels for Deletion to Classes of Acyclic Digraphs
Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi
                 - 
Journal of Computer and System Sciences 
                 -A preliminary version of this article appeared in   ISAAC 2016

Kernelization of Cycle Packing with Relaxed Disjointness Constraints
Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, Saket Saurabh
                 - SIAM Journal on Discrete Mathematics 
                 -A preliminary version of this article appeared in   ICALP 2016

Simultaneous Feedback Vertex Set: A Parameterized Perspective
Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh
               -
ACM Transactions on Computation Theory 
                 -A preliminary version of this article appeared in   STACS 2016

2017

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Daniel Lokshtanov
                  -SODA 2017


On the Parameterized Complexity of Simultaneous Deletion Problems
Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and Ramanujan M. S.
                  -FSTTCS 2017


On the Parameterized Complexity of Contraction to Generalization of Trees
Akanksha Agrawal, Saket Saurabh, and Prafullkumar Tale
               -IPEC 2017


Fine-grained Complexity of Rainbow Coloring and its Variants
Akanksha Agrawal
               - MFCS 2017


On the Parameterized Complexity of Happy Vertex Coloring
Akanksha Agrawal
               -IWOCA 2017


Critical node cut parameterized by treewidth and solution size is W[1]-hard
Akanksha Agrawal, Daniel Lokshtanov, and Amer Mouawad
               -WG 2017


Fast Exact Algorithms for Survivable Network Design with Uniform Requirements
Akanksha Agrawal, Pranabendu Misra, Fahad Panolan, Saket Saurabh
               -WADS 2017


Paths to Trees and Cacti
Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh and Prafullkumar Tale
               -CIAC 2017

 
Split Contraction: The Untold Story

Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi
               -STACS 2017

2016


Simultaneous Feedback Vertex Set: A Parameterized Perspective
Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh
               -STACS 2016


Simultaneous Feedback Edge Set: A Parameterized Perspective
Akanksha Agrawal, Fahad Panolan, Saket Saurabh, Meirav Zehavi
               -ISAAC 2016


Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
Akanksha Agrawal, Sushmita Gupta, Saket Saurabh and Roohani Sharma
               -IPEC 2016


Kernelizing Buttons and Scissors
Akanksha Agrawal, Sudeshna Kolay, Saket Saurabh and Roohani Sharma
               -CCCG 2016 


Kernelization of Cycle Packing with Relaxed Disjointness Constraints
Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, Saket Saurabh
               -ICALP 2016 


A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, Saket Saurabh
               -LATIN 2016 


Kernels for Deletion to Classes of Acyclic Digraphs
Akanksha Agrawal, Saket Saurabh, Roohani Sharma and Meirav Zehavi
                 -ISAAC 2016

2014

Vertex Cover gets   Faster and Harder on Low Degree
Akanksha Agrawal, Neeldhara Misra and Sathish Govindarajan
               -COCOON 2014
Powered by Create your own unique website with customizable templates.