Hello, I am a Researcher at the Department of Informatics, University of Bergen. Prior to this, I was a Lise-Meitner Post-doctoral Fellow at the Max Planck Institute for Informatics, Germany. I did my PhD from Institute of Mathematical Sciences, Chennai, India.
My primary area of research is parameterized complexity and kernelization. I am also interested in the intersection of the above paradigms with approximation, like FPT-approximation and lossy kernelization.
In the above paradigms, I (have) work(ed) on various kinds of graph problems that can be grouped into different categories: cut, connectivity, CSPs, clustering, covering, packing, partitioning, width-measures, geomteric graph classes and graph drawing.
Attending Dagstuhl seminar 25041: Solving Problems on Graphs: From Structure to Algorithms.
Crossing Number in Slightly Superexponential Time, to appear at SODA 2025. Joint work with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi.
Uniform Polynomial Kernel for Deletion to K_{2,p} Minor-Free Graphs, to appear at ISAAC 2024. Joint work with William Lochet.
Co-organized Dagstuhl seminar 24411: New tools in Parameterized Complexity: Paths, Cuts and Decomposition.
Served at the programme committee of ESA 2024.
Component Order Connectivity admits no polynomial kernel parameterized by the feedback vertex set number appeared at IPEC 2024. Joint work with Jacob Greilhuber.
Hitting Meets Packing: How Hard Can it Be? appeared at ESA 2024. Joint work with Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Philipp Schepper, Karol Węgrzycki.
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces appeared at ICALP 2024. Joint work with Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Joachim Spoerhase.
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification appeared at ICALP 2024. Joint work with Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx.
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth and Vertex Cover appeared at ICALP 2024. Joint work with Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale.
Eliminating Crossings in Ordered Graphs appeared at SWAT 2024. Joint work with Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Yushi Uno, Alexander Wolff.
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations appeared at SODA 2024. Joint work with Baris Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen.
Odd Cycle Transversal on P_5-free Graphs in Quasi-polynomial Time appeared at SODA 2024. Joint work with Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov, Saket Saurabh.
You can contact me at r.sharma[AT] uib [DOT] no or [first-name].[last-name]90 [AT] gmail [DOT] com.