Daniel Lokshtanov

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 283

Top Venues

CoRR

SODA

ACM Trans. Algorithms

ICALP

Publications

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable. SODA (2024)
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Daniel Lokshtanov, Giannos Stamoulis
Shortest Cycles with Monotone Submodular Costs. ACM Trans. Algorithms 20 (1) (2024)
Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov, Pawel Rzazewski, Saket Saurabh, Roohani Sharma
-free Graphs in Polynomial Time. CoRR (2024)
Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
When far is better: The Chamberlin-Courant approach to obnoxious committee selection. CoRR (2024)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3. CoRR (2024)
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Anannya Upasana
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. CoRR (2024)
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi
Kernelization of Counting Problems. ITCS (2024)
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
The Parameterized Complexity of Guarding Almost Convex Polygons. Discret. Comput. Geom. 71 (2) (2024)
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl
Tree Independence Number IV. Even-hole-free Graphs. CoRR (2024)
Tuukka Korhonen, Daniel Lokshtanov
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition. SODA (2024)
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue
True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs. ACM Trans. Algorithms 20 (3) (2024)
Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov, Saket Saurabh, Roohani Sharma
-free Graphs in Quasi-polynomial Time. SODA (2024)
Chaofan Shou, Rohan Bhatia, Arpit Gupta, Rob Harrison, Daniel Lokshtanov, Walter Willinger
Query Planning for Robust and Scalable Hybrid Network Telemetry Systems. Proc. ACM Netw. 2 (CoNEXT1) (2024)
Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. STOC (2024)
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
Meta-theorems for Parameterized Streaming Algorithms‡. SODA (2024)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
A 1.9999-Approximation Algorithm for Vertex Cover on String Graphs. SoCG (2024)
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Anannya Upasana
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints. ICALP (2024)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
A Framework for Approximation Schemes on Disk Graphs. SODA (2023)
Úrsula Hébert-Johnson, Daniel Lokshtanov, Eric Vigoda
Counting and Sampling Labeled Chordal Graphs in Polynomial Time. ESA (2023)
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi
Polynomial Kernel for Interval Vertex Deletion. ACM Trans. Algorithms 19 (2) (2023)
Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability. CoRR (2023)
Úrsula Hébert-Johnson, Daniel Lokshtanov, Eric Vigoda
Counting and Sampling Labeled Chordal Graphs in Polynomial Time. CoRR (2023)
Tuukka Korhonen, Daniel Lokshtanov
An Improved Parameterized Algorithm for Treewidth. STOC (2023)
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi
Lossy Kernelization for (Implicit) Hitting Set Problems. ESA (2023)
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi
An ETH-Tight Algorithm for Bidirected Steiner Connectivity. WADS (2023)
Peter Gartland, Tuukka Korhonen, Daniel Lokshtanov
On Induced Versions of Menger's Theorem on Sparse Graphs. CoRR (2023)
Eric Aaron, Úrsula Hébert-Johnson, Danny Krizanc, Daniel Lokshtanov
Min-max coverage problems on tree-like metrics. LAGOS (2023)
Tuukka Korhonen, Daniel Lokshtanov
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition. CoRR (2023)
Peter Gartland, Daniel Lokshtanov
Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs. SODA (2023)
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi
Erdős-Pósa property of obstructions to interval graphs. J. Graph Theory 102 (4) (2023)
Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
Parameterized Complexity of Fair Bisection: (FPT-Approximation meets Unbreakability). ESA (2023)
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
Breaking the All Subsets Barrier for Min k-Cut. ICALP (2023)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs. CoRR (2023)
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
Meta-theorems for Parameterized Streaming Algorithms. CoRR (2023)
Peter Gartland, Daniel Lokshtanov
Graph Classes with Few Minimal Separators. II. A Dichotomy. SODA (2023)
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Daniel Lokshtanov, Giannos Stamoulis
Shortest Cycles With Monotone Submodular Costs. SODA (2023)
Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. CoRR (2023)
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, Meirav Zehavi
Lossy Kernelization for (Implicit) Hitting Set Problems. CoRR (2023)
Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, Saket Saurabh
Parameterized Approximation Scheme for Feedback Vertex Set. MFCS (2023)
Michael Kuhn, Daniel Lokshtanov, Zachary Miller
-Free Graphs. CoRR (2023)
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable. CoRR (2023)
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi
Kernelization of Counting Problems. CoRR (2023)
Sushmita Gupta, Pallavi Jain, Daniel Lokshtanov, Sanjukta Roy, Saket Saurabh
Gehrlein Stable Committee with Multi-modal Preferences. SAGT (2022)
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue
True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs. SoCG (2022)
Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. SIAM J. Comput. 51 (6) (2022)
Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan
Backdoor Sets on Nowhere Dense SAT. ICALP (2022)
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri, Jie Xue
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles. CoRR (2022)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
A Framework for Approximation Schemes on Disk Graphs. CoRR (2022)
Pål Grønås Drange, Markus Fanebust Dregi, Daniel Lokshtanov, Blair D. Sullivan
On the threshold of intractability. J. Comput. Syst. Sci. 124 (2022)
Tuukka Korhonen, Daniel Lokshtanov
An Improved Parameterized Algorithm for Treewidth. CoRR (2022)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract). SODA (2022)
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri, Jie Xue
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles. SoCG (2022)
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Highly unbreakable graph with a fixed excluded minor are almost rigid. CoRR (2022)
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor. CoRR (2022)
Daniel Lokshtanov, Bernardo Subercaseaux
Wordle is NP-hard. CoRR (2022)
Daniel Lokshtanov, Bernardo Subercaseaux
Wordle Is NP-Hard. FUN (2022)
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H<-Minor-Free Graphs. SODA (2022)
Jean R. S. Blair, Pinar Heggernes, Paloma T. Lima, Daniel Lokshtanov
On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number. Algorithmica 84 (12) (2022)
Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. STOC (2022)
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. Algorithmica 84 (2) (2022)
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent. SODA (2022)
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, Daniel Lokshtanov, Giannos Stamoulis
Shortest Cycles With Monotone Submodular Costs. CoRR (2022)
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski
-free graphs in quasipolynomial time. STOC (2021)
Eduard Eiben, Daniel Lokshtanov, Amer E. Mouawad
Bisection of bounded treewidth graphs by convolutions. J. Comput. Syst. Sci. 119 (2021)
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh
Elimination Distance to Topological-minor-free Graphs is FPT. CoRR (2021)
William Lochet, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Exploiting Dense Structures in Parameterized Complexity. STACS (2021)
Daniel Lokshtanov, Vaishali Surianarayanan
Dominating Set in Weakly Closed Graphs is Fixed Parameter Tractable. FSTTCS (2021)
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs. CoRR (2021)
Daniel Lokshtanov, Pranabendu Misra, Michal Pilipczuk, Saket Saurabh, Meirav Zehavi
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths. CoRR (2021)
Daniel Lokshtanov, Subhash Suri, Jie Xue
Efficient Algorithms for Least Square Piecewise Polynomial Regression. ESA (2021)
Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan, Eric Thierry
Faster and enhanced inclusion-minimal cograph completion. Discret. Appl. Math. 288 (2021)
Meirav Zehavi, Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs. J. Comput. Geom. 12 (2) (2021)
Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version). SODA (2021)
Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf
Diversity in Kemeny Rank Aggregation: A Parameterized Approach. IJCAI (2021)
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane. SODA (2021)
Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
FPT-approximation for FPT Problems. SODA (2021)
Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh, Magnus Wahlström
Randomized Contractions Meet Lean Decompositions. ACM Trans. Algorithms 17 (1) (2021)
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza
Computing the Largest Bond and the Maximum Connected Cut of a Graph. Algorithmica 83 (5) (2021)
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
b-Coloring Parameterized by Clique-Width. STACS (2021)
Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs. ACM Trans. Comput. Theory 13 (4) (2021)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. ACM Trans. Comput. Theory 13 (2) (2021)
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
Multiplicative Parameterization Above a Guarantee. ACM Trans. Comput. Theory 13 (3) (2021)
Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh
2-Approximating Feedback Vertex Set in Tournaments. ACM Trans. Algorithms 17 (2) (2021)
Rohan Bhatia, Arpit Gupta, Rob Harrison, Daniel Lokshtanov, Walter Willinger
DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems. CoRR (2021)
Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf
Diversity in Kemeny Rank Aggregation: A Parameterized Approach. CoRR (2021)
Daniel Lokshtanov, Andreas Björklund, Saket Saurabh, Meirav Zehavi
-Paths: Simpler, Deterministic, and in Polynomial Space. ACM Trans. Algorithms 17 (3) (2021)
Daniel Lokshtanov, Saket Saurabh, Subhash Suri, Jie Xue
An ETH-Tight Algorithm for Multi-Team Formation. FSTTCS (2021)
Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, Saket Saurabh
2-Approximating Feedback Vertex Set in Tournaments. SODA (2020)
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
A Parameterized Approximation Scheme for Min k-Cut. CoRR (2020)
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza
Computing the Largest Bond and the Maximum Connected Cut of a Graph. CoRR (2020)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. CoRR (2020)
Fedor V. Fomin, Daniel Lokshtanov, Sudeshna Kolay, Fahad Panolan, Saket Saurabh
Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. ACM Trans. Algorithms 16 (2) (2020)
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
The Parameterized Complexity of Guarding Almost Convex Polygons. SoCG (2020)
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
b-Coloring Parameterized by Clique-Width. CoRR (2020)
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs. CoRR (2020)
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
Parameterization Above a Multiplicative Guarantee. ITCS (2020)
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. ACM Trans. Algorithms 16 (3) (2020)
Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi
Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems. ACM Trans. Algorithms 16 (4) (2020)
Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs. CoRR (2020)
Peter Gartland, Daniel Lokshtanov
Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time. FOCS (2020)

Daniel Lokshtanov.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Daniel Lokshtanov