Roohani Sharma

Hello, I am a Young Scientist Fellow and PI at the Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea. Prior to this I was a Researcher at the, Department of Informatics, University of Bergen and a Lise-Meitner Post-doctoral Fellow at the Max Planck Institute for Informatics (MPII), 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, logic and structural graph theory.

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, geometric graph classes and graph drawing.

Recent news

Will serve in the Program Committee (PC) of 52nd International Workshop on Graph-Theoretic Comcepts in Computer Science (WG 2026).
Received the Young Scientist Fellowship (YSF) to lead as a PI at the DIMAG group at the Institute for Basic Science, Daejeon, South Korea.
Joined as a reviewer at Mathematical Reviews published by the American Mathematical Society (AMS).
Attended Dagstuhl seminar 25041: Solving Problems on Graphs: From Structure to Algorithms.
MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal: to appear at STACS 2025. Joint work with Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity, Saket Saurabh.
Metric Dimension and Geodetic Set Parameterized by Vertex Cover, at STACS 2025. Joint work with Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Prafullkumar Tale.
Odd Cycle Transversal on P_5-free Graphs in Polynomial Time, at TALG 2025. Joint work with Akanksha Agrawal, Paloma T. Lima, Paweł Rzążewski, Daniel Lokshtanov, Saket Saurabh.
Crossing Number in Slightly Superexponential Time, at SODA 2025. Joint work with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi.

Past events

Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS, at TOCT 2025. Joint work with Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi.
Exact and Approximate Digraph Bandwidth, at TOCS 2025. Joint work with Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh.
Co-organized Dagstuhl seminar 24411: New tools in Parameterized Complexity: Paths, Cuts and Decomposition.
Served at the programme committee of ESA 2024.
Uniform Polynomial Kernel for Deletion to K_{2,p} Minor-Free Graphs, to appear at ISAAC 2024. Joint work with William Lochet.
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 Wę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, 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.

Contact

You can contact me at roohani [AT] ibs [DOT] re [DOT] kr or [first-name] [DOT] [last-name]90 [AT] gmail [DOT] com.