I am an Assistant Professor in Computer Science at the Chennai Mathematical Institute (CMI), India.
In the recent past, I was a postdoctoral fellow in the Algorithms and Complexity department at the Max Planck Institute for Informatics, Saarbrucken, Germany.
Earlier, I was a researcher in the Algorithms group at the Department of Informatics, University of Bergen, Norway.
I obtained my PhD in Computer Science, advised by Prof. Saket Saurabh, from the Institute of Mathematical Sciences (IMSc), India and my masters and undergraduate degree from CMI in Mathematics and Computer Science.
Grants, Awards …
- Google India Research Award 2022
- SERB Startup Research Grant (SRG) 2022
Research Interests
Algorithms, Graph Theory, Parameterized Complexity, Approximation Algorithms.
I have also worked on a few problems in Matroid Theory, Derandomization, Algorithmic Game Theory, Fault-tolerant subgraphs, Streaming algorithms, Machine Learning and Artificial Intellegence,… etc.
Broadly, I am interested in anything with an algorithmic flavor.
Publications
(Also available at DBLP and Google Scholar.)
- A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
- with Daniel Marx, Daniel Neuen and Prafullkumar Tale
- SODA 2022
- Improving EFX Guarantees through Rainbow Cycle Number
- with Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn and Ruta Mehta
- EC 2021
- Strong Connectivity Augmentation is FPT
- with Kristine Vitting Klinkby and Saket Saurabh
- SODA 2021
- FPT Approximation for FPT Problems
- with Daniel Lokshtanov, MS Ramanujan, Saket Saurabh and Meirav Zehavi
- SODA 2021
- An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
- with Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh and Meirav Zehavi
- STOC 2020.
- Fault Tolerant Subgraphs with Applications in Kernelization
- with William Lochet, Daniel Lokshtanov, Saket Saurabh, Roohani Sharma and Meirav Zehavi
- ITCS 2020.
- 2-Approximating Feedback Vertex Set in Tournaments
- with Daniel Lokshtanov, Joydeep Mukherjee, Geevarghese Philip, Fahad Panolan, Saket Saurabh
- SODA 2020.
- On the Complexity of Recovering Incidence Matrices
- with Ramanujan M. S., Petr Golovach and Fedor Fomin
- ESA 2020.
- A (2 + ε)-factor Approximation Algorithm for Split Vertex Deletion
- with Daniel Lokshtanov, Fahad Panolan, Geevarghese Philip and Saket Saurabh
- ICALP 2020.
- Quick Separation in Chordal and Split Graphs
- with Fahad Panolan, Ashutosh Rai, Saket Saurabh and Roohani Sharma
- MFCS 2020.
- Parameterized Complexity of Directed Spanner Problems
- with Fedor Fomin, Petr Golovach, William Lochet, Saket Saurabh and Roohani Sharma
- IPEC 2020
- Popular Matching in the Roommates Setting is NP-hard
- with Sushmita Gupta, Saket Saurabh, and Meirav Zehavi
- SODA 2019
- Interval Vertex Deletion Admits a Polynomial Kernel
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
- SODA 2019
- An Erdős-Pósa Theorem on Neighborhoods and Domination Number
- with Jayakrishnan Madathil and Saket Saurabh
- COCOON 2019
- Parameterized Algorithms for Survivable Network Design with Uniform Demands
- with Joergen Bang-Jensen, Manu Basavaraju, Kristine Vitting Klinkby, Ramanujan M. S., Saket Saurabh and Meirav Zehavi
- SODA 2018
- Erdos-Posa Property of Obstructions to Interval Graphs
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
- STACS 2018
- Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
- with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- ITCS 2018
- Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
- APPROX 2018
- Journal: ACM Transactions on Algorithms, 2020.
- Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
- with Roohani Sharma, Saket Saurabh and Meirav Zehavi
- FSTTCS 2018
- Exploring the Kernelization Borders for Hitting Cycles
- with Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh and Saket Saurabh
- IPEC 2018
- Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
- with Pallavi Jain and Lawqueen Kanesh
- CSR 2018
- Journal: Theory of Computing Systems, 2020.
- An FPT Algorithm for Contraction to Cactus.
- with R. Krithika and Prafullkumar Tale.
- COCOON 2018
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- with Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
- SODA 2017
- Journal: ACM Transactions on Algorithms, 2019.
- Fast Exact Algorithms for Survivable Network Design with Uniform Requirements.
- with Akanksha Agarwal, Fahad Panolan and Saket Saurabh.
- WADS 2017
- Derandomization of Transversal Matroids and Gammoids in Moderately Exponential Time.
- with Fahad Panolan, M.S. Ramanujan and Saket Saurabh.
- COCOON 2017
- Journal: Theoretical Computer Science, 2020.
- Hitting Selected (Odd) Cycles.
- with Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh.
- Journal: In SIAM Journal of Discrete Mathematics 31(3):1581-1615 (2017).
- Lossy Kernels for Graph Contraction Problems
- with R Krithika, Ashutosh Rai and Prafullkumar Tale.
- FSTTCS 2016
- Deterministic Truncation of Linear Matroids.
- with Daniel Lokshtanov, Fahad Panolan and Saket Saurabh.
- ICALP 2015
- Journal: ACM Transactions on Algorithms, 2018.
- Reducing Rank of the Adjacency Matrix by Graph Modification.
- with S. M. Meesum and Saket Saurabh
- COCOON 2015
- Journal: Theoretical Computer Science 654:70-79 (2016).
- Finding Even Subgraphs Even Faster.
- with Prachi Goyal, Fahad Panolan, Geevarghese Philip and Saket Saurabh.
- FSTTCS 2015
- Journal: Journal of Computer and System Sciences, 2018.
- Parameterized Algorithms to Preserve Connectivity.
- with Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan and Saket Saurabh.
- ICALP 2014
- Faster Graph Bipartization
- with Sudeshna Kolay, M. S. Ramanujan and Saket Saurabh.
- MFCS 2014
- Journal: Journal of Computer and System Sciences, 2020.
- Faster Exact Algorithms for Some Terminal Set Problems.
- with Rajesh H. Chitnis, Fedor V. Fomin, Daniel Lokshtanov, M. S. Ramanujan and Saket Saurabh.
- IPEC 2013
- Journal: Journal of Computing and System Sciences 88:195-207 (2017).
- Faster Parameterized Algorithms for Deletion to Split Graphs
- with Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Fahad Panolan, Ashutosh Rai and M. S. Ramanujan.
- SWAT 2012
- Journal: Algorithmica 71(4): 989-1006 (2015).
- Parameterized Algorithms for Even Cycle Transversal
- with Venkatesh Raman, M.S. Ramanujan and Saket Saurabh.
- WG 2012
- A polynomial kernel for Feedback Arc Set on bipartite tournaments.
- with Venkatesh Raman, M.S. Ramanujan and Saket Saurabh.
- ISAAC 2011
- Journal: Theory of Computing Systems 53(4):609-620 (2013).
Manuscripts
- On Fault Tolerant Feedback Vertex Set
- An ETH-tight algorithm for Bidirected Steiner Connectivity
- with Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- Deterministic Representation of Gammoids in Quasipolynomial time with Applications
- with Rohit Gurjar, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi
- A Brief Note on Single Source Fault Tolerant Reachability
- with Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi
- Graph Algorithms in the Parameterized Semi-Streaming Model
- with Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh and Meirav Zehavi
Thesis
- PhD Thesis: Parameterized Algorithms for Network Design.
Teaching
Email
pranabendu.m [__A_T___] gmail.com
pranabendu@cmi.ac.in
Postal address
Chennai Mathematical Institute
H1, SIPCOT IT Park, Siruseri
Kelambakkam, Chennai 603103
India
Links