[J12] A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs. In SIAM Journal on Discrete Mathematics (2023), 37(2). Conference version appeared in [C24].
[J11] Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In ACM Transactions on Algorithms (2021), 17(2). Joint work with Andreas Emil Feldmann and Pasin Manurangsi. Conference version appeared in [C21].
[J10] Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). In SIAM Journal of Computing. Joint work with Andreas Emil Feldmann and MohammadTaghi Hajiaghayi and Dániel Marx. This is the journal version of [C12]: the algorithm is both faster and simplified.
[J9] A Tight Lower Bound for Planar Steiner Orientation. In Algorithmica (2019), 81(8), 3200-3216. Joint work with Andreas Emil Feldmann and Ondrej Suchy. This is the journal version of [C20]: it extends the W[1]-hardness from genus 1 to genus 0 (planar graphs) and also has a new FPT inapproximability result
[J8] Faster Exact Algorithms for Some Terminal Set Problems. In Journal of Computer and System Sciences (2017), 88, 195-207. Joint work with Fedor Fomin and Daniel Lokshtanov and Pranabendu Misra and M.S. Ramanujan and Saket Saurabh. Conference version appeared in [C9].
[J7] List H-Coloring a Graph by Removing Few Vertices. In Algorithmica (2017), 78(1), 110-146. Joint work with Laszlo Egri and Dániel Marx. Conference version appeared in [C8].
[J6] Designing FPT Algorithms for Cut Problems using Randomized Contractions. In SIAM Journal of Computing (2016), 45(4), 1171-1229.. Joint work with Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and Michal Pilipczuk. Conference version appeared in [C5].
[J5] A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands. In Algorithmica (2017), 77(4), 1216-1239 . Joint work with Hossein Esfandiari and MohammadTaghi Hajiaghayi and Rohit Khandekar and Guy Kortsarz and Saeed Seddighin. Conference version appeared in [C13].
[J4] Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. In Information and Computation (2016), 247, 11-22. Joint work with Fedor Fomin and Petr Golovach. Conference version appeared in [C11].
[J3] Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. In ACM Transactions on Algorithms (2015), 11(4), 28:1-28:28. Joint work with Marek Cygan and MohammadTaghi Hajiaghayi and Dániel Marx. Conference version appeared in [C4].
[J2] Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. In SIAM Journal of Computing (2013), 42(4), 1674-1696. Joint work with MohammadTaghi Hajiaghayi and Dániel Marx. Conference version appeared in [C3].
[J1] On the SIG dimension of trees under the L∞ metric. In Graphs and Combinatorics (2013), 29(4), 773-794. Joint work with L. Sunil Chandran and Ramanjit Kumar
[C29] Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths. In WAOA 2024. Joint work with Samuel Thomas and Tony Wirth
[C28] Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs. In WADS 2023. Joint work with Xiuge Chen and Patrick Eades and Tony Wirth
[C27] How Does Fairness Affect the Complexity of Gerrymandering? (extended abstract). In AAMAS 2023. Joint work with Sandip Banerjee and Abhiruk Lahiri
[C26] Tight Lower Bounds for Approximate & Exact k-Center in ℝd. In SoCG 2022. Joint work with Nitin Saurabh
[C25] Refined Lower Bounds for Nearest Neighbor Condensation. In ALT 2022.
[C24] A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs. In CIAC 2021.
[C23] Towards a Theory of Parameterized Streaming Algorithms. In IPEC 2019. Joint work with Graham Cormode
[C22] FPT Inapproximability of Directed Cut and Connectivity Problems. In IPEC 2019. Joint work with Andreas Emil Feldmann
[C21] Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In ESA 2018. Joint work with Andreas Emil Feldmann and Pasin Manurangsi
[C20] A Tight Lower Bound for Steiner Orientation. In CSR 2018. Joint work with Andreas Emil Feldmann.
[C19] Can We Create Large k-Cores by Adding Few Edges? In CSR 2018. Joint work with Nimrod Talmon
[C18] Algorithms and Hardness Results for Nearest Neighbor Problems in Bicolored Point Sets. In LATIN 2018. Joint work with Sandip Banerjee and Sujoy Bhore
[C17] Tight Bounds for Gomory-Hu-like Cut Counting. In WG 2016. Joint work with Lior Kamma and Robert Krauthgamer. The latest version (on arXiv) contains additional references to previous work (which have some overlap with our results).
[C16] Kernelization via Sampling with Applications to Dynamic Graph Streams . In SODA 2016. Joint work with Graham Cormode and Hossein Esfandiari and MohammadTaghi Hajiaghayi and Andrew McGregor and Morteza Monemizadeh and Sofya Vorotnikova
[C15] New Streaming Algorithms for Parameterized Maximal Matching and Beyond . In SPAA 2015 (short paper). Joint work with Graham Cormode and Hossein Esfandiari and MohammadTaghi Hajiaghayi and Morteza Monemizadeh
[C14] Parameterized Streaming: Maximal Matching and Vertex Cover. In SODA 2015. Joint work with Graham Cormode and MohammadTaghi Hajiaghayi and Morteza Monemizadeh
[C13] A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands. In IPEC 2014. Joint work with Hossein Esfandiari and MohammadTaghi Hajiaghayi and Rohit Khandekar and Guy Kortsarz and Saeed Seddighin
[C12] Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). In SODA 2014. Joint work with MohammadTaghi Hajiaghayi and Dániel Marx
[C11] Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs . In FSTTCS 2013. Joint work with Fedor Fomin and Petr Golovach
[C10] Fixed-Parameter and Approximation Algorithms: A New Look. In IPEC 2013. Joint work with MohammadTaghi Hajiaghayi and Guy Kortsarz
[C9] Faster Exact Algorithms for Some Terminal Set Problems. In IPEC 2013. Joint work with Fedor Fomin and Daniel Lokshtanov and Pranabendu Misra and M.S. Ramanujan and Saket Saurabh
[C8] List H-Coloring a Graph by Removing Few Vertices. In ESA 2013. Joint work with Laszlo Egri and Dániel Marx
[C7] Preventing Unraveling in Social Networks Gets Harder. In AAAI 2013. Joint work with Fedor Fomin and Petr Golovach
[C6] A Game-Theoretic Model Motivated by the DARPA Network Challenge. In SPAA 2013 (short paper). A preliminary version appeared in Workshop on Risk Aversion in Algorithmic Game Theory and Mechanism Design . Joint work with MohammadTaghi Hajiaghayi and Jonathan Katz and Koyel Mukherjee
[C5] Designing FPT Algorithms for Cut Problems using Randomized Contractions. In FOCS 2012. Joint work with Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and Michal Pilipczuk
[C4] Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable. In ICALP 2012. Joint work with Marek Cygan and MohammadTaghi Hajiaghayi and Dániel Marx
[C3] Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset. In SODA 2012. Joint work with MohammadTaghi Hajiaghayi and Dániel Marx
[C2] Parameterized Complexity of Problems in Coalitional Resource Games. In AAAI 2011. Joint work with MohammadTaghi Hajiaghayi and Vahid Liaghat
[C1] Parameterized Algorithms for Boxicity. In ISAAC 2010. Joint work with Abhijin Adiga and Saket Saurabh
Directed Graphs: Fixed-Parameter Tractability and Beyond. Advised by Prof. MohammadTaghi Hajiaghayi
Shadowless Solutions for Fixed-Parameter Tractability of Directed Graphs. In Encyclopedia of Algorithms 2015. Jointly written with MohammadTaghi Hajiaghayi
Review of Fundamentals of Parameterized Complexity by Rodney G. Downey and Michael R. Fellows. In SIGACT News