Research Publications/Reports
Listing last 25 publications. (View All) View/Hide Filter- Approximately interpolating between uniformly and non-uniformly polynomial kernels
Akanksha Agrawal, Ramanujan M S, Appeared in 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2023.
- Recognizing Well-Dominated Graphs is NP-complete
Akanksha Agrawal, Henning Fernau, Mann Kevin, Philipp Kindermann, Uéverton S. Souza, Appeared in Information Processing Letters, Oct 2023.
- Polynomial Kernel for Interval Vertex Deletion
Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Appeared in ACM Transactions on Algorithms, Vol 19, No.2, pp.11:1-11:68, Apr 2023.
- Erdős-Pósa property of obstructions to interval graphs
Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Appeared in Journal of Graph Theory, Vol 102, No.4, pp.702-727, Apr 2023.
- Clustering What Matters: Optimal Approximation for Clustering with Outliers
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue, Appeared in The 37th AAAI Conference On Artificial Intelligence, Feb 2023.
- Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal, Daniel Marx, Daniel Neuen, Jasper Slusallek, Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Jan 2023.
- On finding short reconfiguration sequences between independent sets
Akanksha Agrawal, Soumita Hait, Amer E. Mouawad, Appeared in The 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Dec 2022.
- Parameterized Complexity of Perfectly Matched Sets
Akanksha Agrawal, Sutanay Bhattacharjee, Abhishek Sahu, Satyabrata Jana, Appeared in The 17th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022.
- A Finite Algorithm for the Realizability of a Delaunay Triangulation
Akanksha Agrawal, Saket Saurabh, Meirav Zehavi, Appeared in The 17th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022.
- Distance From Triviality 2.0: Hybrid Parameterizations
Akanksha Agrawal, M.S. Ramanujan, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), Jun 2022.
- Fine-grained complexity of rainbow coloring and its variants
Akanksha Agrawal, Appeared in Journal of Computer and System Sciences, Vol 124, Mar 2022.
- Parameterized Complexity of Minimum Membership Dominating Set
Akanksha Agrawal, Pratibha Choudhary, Narayanaswamy N S, Nisha K K, Vijayaraghunathan Ramamoorthi, Appeared in WALCOM, Mar 2022.
- Deleting, Eliminating and Decomposing to Hereditary Graph Classes Are All FPT Equivalent
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi, Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Jan 2022.
- Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH
Akanksha Agrawal, Allumalla Ravi Kiran, Dhanekula Varun Teja, Appeared in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Sep 2021.
- ​A Polynomial Kernel for Deletion to Ptolemaic Graphs
Akanksha Agrawal, Aditya Anand, Saket Saurabh, Appeared in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Aug 2021.
- Paths to Trees and Cacti
Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, Prafullkumar Tale, Appeared in Theoretical Computer Science, Vol 860, Mar 2021.
- ​​An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Appeared in Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.