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, To Appear 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, To Appear in Information Processing Letters, Oct 2023.
- Testing properties of distributions in the streaming model
Sampriti Roy, Yadu Vasudev, To Appear in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Sep 2023.
- Matchings under One-Sided Preferences with Soft Quotas
Santhini K A, Meghana Nasre, Raghu Raman Ravi, Appeared in International Joint Conference on Artificial Intelligence (IJCAI), Aug 2023.
- On Separating Words Problem over Groups
Neha Kuntewar, Anoop S K M, Jayalal Sarma, Appeared in 25th International Conference on Descriptional Complexity of Formal Systems (DCFS 2023), Jul 2023.
- Optimal Cost based allocation under Two sided preferences
Girija Limaye, Meghana Nasre, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), pp.259--270, Jun 2023.
- Critical Relaxed Stable Matchings with Two-Sided Ties
Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 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.
- Envy-freeness and relaxed stability: hardness and approximation algorithms
Prem Krishnaa, Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar, Appeared in Journal of Combinatorial Optimization, Vol 45, No.1, pp.41, Jan 2023.
- Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
Manas Jyothi Kashyap, Narayanaswamy N S, Meghana Nasre, Sai Mohith Potluri, Appeared in Algorithmica, Vol 85, No.4, pp.854--878, Jan 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.
- On Rotation Distance, Transpositions and Rank Bounded Trees
Anoop S K M, Jayalal Sarma, Appeared in 28th International Computing and Combinatorics Conference (COCOON 2022), Oct 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.
- Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Data Compression Conference (DCC 2022), Mar 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.
- Isomorphism Testing of Read-once Functions and Polynomials
Raghavendra Rao B V, Jayalal Sarma, Appeared in Information and Computation, Feb 2022. A preliminary version appeared in Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), LIPIcs–Leibniz International Proceedings in Informatics, Vol 13, pp.115-126, Dec 2011.
- Optimal Matchings with One-sided Preferences : Fixed and Cost Based Quotas
Santhini K A, Govind S. Sankar, Meghana Nasre, Appeared in Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022),, To Appear, Jan 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.
- Popular Matchings in the Hospital-Residents Problem with Two-sided Lower Quotas
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar, Appeared in 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2021.