Shivesh K. Roy

About

I am currently a postdoc at Chennai Mathematical Institute (CMI) hosted by Prof. Pranabendu Misra. Before joining CMI, I spent two years as a postdoc at the Institute of Mathematical Sciences Chennai, hosted by Prof. Saket Saurabh. Prior to that, I completed my PhD in the Algorithms group at TU Eindhoven, under the supervision of Prof. Bart Jansen and Prof. Mark de Berg.

Research

I am broadly interested in theoretical computer science, with a particular focus on (parameterized) algorithms and complexity, and graph theory.

Recent News:

Gave a talk at the Foundational Lecture Series on Theoretical Computer Science 2026 [Slides]
Attended Frontiers of Graph Algorithms workshop at IISc Bangalore 2025
Gave a talk at the workshop Modern Trends in Parameterized Algorithms, IIT Madras 2025 [Slides]
Gave a talk at IIT Dharwad on “Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components” [Slides]

Defended PhD thesis titled "Parameterized Algorithms for Augmented Graph Problems" on September 19, 2024. [PDF] [Slides]

Committee: Hans Bodlaender, Daniel Paulusma, Frits Spieksma, Ramanujan Sridharan

Publications [Also available at DBLP]

Minimum Sum Coloring Revisited
- With Suchismita Mishra, Ravindra Pawar, Nidhi Purohit, and Saket Saurabh
- In: Proceedings of the 46th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, IIT Delhi, India
- FSTTCS 2026

Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components [Slides in the 2nd half cover algorithmic results]
- With Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Sahiba, and Saket Saurabh [Slides covering structural results]
- In: Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland
- MFCS 2025

Subset Feedback Vertex Set Parameterized by Multiway Cut is FPT [Slides in1st half]
- With Sriram Bhyravarapu, Shashanka Kulamarva, Pritesh Kumar, and Saket Saurabh
- In: Proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science, Europahausstraße, Germany
- WG 2025
- Journal: Accepted with a minor revision at Algorithmica

Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs [Slides] [Recorded Talk at IIT-Dh]
- With Bart Jansen
- In: Proceedings of the 18th International Symposium on Parameterized and Exact Computation, Amsterdam, the Netherlands
- IPEC 2023

On the Parameterized Complexity of Multiway Near-Separator [Slides]
- With Bart Jansen
- In: Proceedings of the 18th International Symposium on Parameterized and Exact Computation, Amsterdam, the Netherlands
- IPEC 2023

On the Hardness of Compressing Weights [Slides]
- With Bart Jansen, and Michał Włodarczyk
- In: Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Tallinn, Estonia
- MFCS 2021
- Journal: Accepted with a minor revision at the ACM Transactions on Computation Theory (TOCT)

Circumventing Connectivity for Kernelization [Slides]
- With Pallavi Jain, Lawqueen Kanesh, Saket Saurabh, and Roohani Sharma
- In: Proceedings of the 12th International Conference on Algorithms and Complexity, Virtual due to COVID-19
- CIAC 2021

Preprint

Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond

With Satyabrata Jana and R. B. Sandeep
Under Submission

Emails

roykumarshivesh [at] gmail [dot] com (Prefer)

skroy [at] cmi [dot] ac [dot] in

Google Sites

Report abuse