Roohani Sharma

Hello, I am a Young Scientist Fellow and PI at the Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea. I am also an Adjunct Professor at the Korean Advanced Institute of Science and Technology (KAIST).

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 2026

Other positions and teaching

Also started as an Adjunct Professor at Korean Advanced Institute of Science and Technology (KAIST).
Teaching Formal Languages and Automata at KAIST, Autumn 2026.

Program Committees

Will serve as a co-chair for the Program Committee (PC) of 22nd International Symposium on Parameterized and Exact Computation (IPEC 2027).
Serving on the Program Committee (PC) of 44th International Symposium on Theoretical Aspects of Computer Science (STACS 2027).
Serving on the Program Committee (PC) of 10th Symposium on Simplicity of Algorithms (SOSA 2027).
Served on the Program Committee (PC) of 38th Annual ACM Symposium on Discrete Algorithms (SODA 2027).
Served on the Program Committee (PC) of 37th International Symposium on Algorithms and Computation (ISAAC 2026).
Served on the Program Committee (PC) of 21st International Symposium on Parameterized and Exact Computation (IPEC 2026).
Served on the Program Committee (PC) of 52nd International Workshop on Graph-Theoretic Comcepts in Computer Science (WG 2026).

Accepted work

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity: to appear at SODA 2027. Joint work with Jan Drier, Robert Ganian, Marlene Gründel, Simon Wietheger.
Metric Dimension and Geodetic Set Parameterized by Vertex Cover: at JCSS 2026. Joint work with Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Prafullkumar Tale.
Approximate Monotone Local Search for Weighted Problems: at Algorithmica 2026. Joint work with Bariş Can Esmer, Ariel Kulik, Dániel Marx, Daniel Neuen.
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time: at Journal of Graph Theory 2026. Joint work with Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh, Meirav Zehavi.
Reducing CMSO to Unbreakable Graphs Cannot be Computable: at ESA 2026. Joint work with Colin Geniet.
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-\eta Deletion: at ESA 2026. Joint work with Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann.
A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth: at MFCS 2026. Joint work with Jakob Greilhuber.
Balanced Substructures in Bicolored Graphs: at TCS 2026. Joint work with P. S. Ardra, R. Krithika, Saket Saurabh.
Protrusion Decompositions Revisited: Uniform Lossy Kernels For Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors: at STACS 2026. Joint work with Michał Włodarczyk.
Applications of flow-augmentation (survey) accepted to Computer Science Review. Jointly written with Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström.

Travels and talks

Presented Reducing CMSO to Unbreakable Graphs Cannot be Computable at ESA 2026, L'Aquila, Italy.
Attended ALGO 2026, L'Aquila, Italy.
Invited speaker at Parameterized Complexity of Constraint Reasoning (PCCR 2026) workshop at FLoC, Lisbon.
Attended Federated Logic Conference (FLoC 2026) in Lisbon, Portugal.
Attended Symposium on Theory of Computing (STOC 2026) in Salt Lake City, Utah, USA.
Invited (and attended) Modern Trends in Parameterized Complexity, Venice, Italy.
Presented Protrusion Decompositions Revisited: Uniform Lossy Kernels For Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors at STACS 2026, Grenoble France.
Attended STACS 2026, Grenoble France.
Invited speaker for Graph Algorithms symposium at the Indo-European Conference of Mathematics, SSPU and IISER Pune, January 2026.

Past events (2025)

Attended Foundations of Computer Science (FOCS 2025) in Sydney, Australia.
Attended 47th Australasian Combinatorics Conference (47th ACC) in Wellington, New Zealand.
Joined as an editor for Discrete Mathematics and Theoretical Computer Science (DMTCS).
Attended LoGAlg 2025 TU Wein.
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 (2024-2025)

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.