## Surveys

**Fedor Fomin**, **Daniel Lokshtanov**, **Saket Saurabh** and **Meirav Zehavi**:
Parameterized Algorithms. Chapter in "Beyond the Worst-Case Analysis of Algorithms", 2021.

**Daniel Lokshtanov**:
Bidimensionality And Kernels. Encyclopedia of Algorithms, 2016.

**Daniel Lokshtanov**, **Neeldhara Misra** and **Saket Saurabh**:
Kernelization - Preprocessing with A Guarantee. Chapter in "The Multivariate Algorithmic Revolution and Beyond", 2012.

**Daniel Lokshtanov**, **Dániel Marx** and **Saket Saurabh**:
Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 2011.

##
Journal Publications

###
2019

**Gábor Bacsó**,

**Daniel Lokshtanov**,

**Dániel Marx**,

**Marcin Pilipczuk**,

**Zsolt Tuza** and

**Erik Jan van Leeuwen**:

Subexponential-Time Algorithms for Maximum Independent Set in P_t-Free and Broom-Free Graphs.
Algorithmica.

**Fedor V. Fomin**,

**Serge Gaspers**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Exact Algorithms via Monotone Local Search.
Journal of the ACM. Short version in the Proceedings of STOC 2016.

**Marek Cygan**,

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michal Pilipczuk** and

**Saket Saurabh**:

Minimum Bisection Is Fixed-Parameter Tractable.
SIAM Journal on Computing. Short version in the Proceedings of STOC 2014.

**Fedor V. Fomin**,

**Petteri Kaski**,

**Daniel Lokshtanov**,

**Fahad Panolan** and

**Saket Saurabh**:

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.
SIAM Journal on Discrete Math. Short version in the Proceedings of ICALP 2015

**Daniel Lokshtanov** and

**Amer E. Mouawad**:

The Complexity of Independent Set Reconfiguration on Bipartite Graphs.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2018.

**Fedor V. Fomin**,

**Petr A. Golovach**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2018.

**Akanksha Agrawal**,

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Saket Saurabh** and

**Meirav Zehavi**:

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2017.

**Fedor V. Fomin**,

**Tien-Nam Le**,

**Daniel Lokshtanov**,

**Saket Saurabh**,

**Stéphan Thomassé** and

**Meirav Zehavi**:

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2018.

**Akanksha Agrawal**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Split Contraction: The Untold Story.
ACM Transactions on Computation Theory. Short version in the Proceedings of STACS 2017.

###
2018

**Fedor V. Fomin**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes.
Journal of the ACM. Based on short versions in the Proceedings of SODA 2011 and SODA 2012.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Long directed (s, t)-path: FPT algorithm.
Information Processing Letters.

**Daniel Lokshtanov**,

**Amer E. Mouawad**,

**Fahad Panolan**,

**M. S. Ramanujan** and

**Saket Saurabh**:

Reconfiguration on sparse graphs.
Journal of Computer and System Sciences. Short version in the Proceedings of WADS 2015.

**Daniel Lokshtanov**,

**Dániel Marx** and

**Saket Saurabh**:

Slightly Superexponential Parameterized Problems.
SIAM Journal on Computing. Short version in the Proceedings of SODA 2011.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Syed Mohammad Meesum**,

**Saket Saurabh** and

**Meirav Zehavi**:

Matrix Rigidity from the Viewpoint of Parameterized Complexity.
SIAM Journal on Discrete Math. Short version in the Proceedings of STACS 2017.

**Akanksha Agrawal**,

**Daniel Lokshtanov**,

**Diptapriyo Majumdar**,

**Amer E. Mouawad** and

**Saket Saurabh**:

Kernelization of Cycle Packing with Relaxed Disjointness Constraints.
SIAM Journal on Discrete Math. Short version in the Proceedings of ICALP 2016.

**Daniel Lokshtanov**,

**Michal Pilipczuk** and

**Saket Saurabh**:

Below All Subsets for Minimal Connected Dominating Set.
SIAM Journal on Discrete Math.

**Fedor V. Fomin**,

**Petr A. Golovach**,

**Daniel Lokshtanov** and

**Saket Saurabh:**
Covering Vectors by Spaces: Regular Matroids.
SIAM Journal on Discrete Math. Short version in the Proceedings of ICALP 2017.

**Daniel Lokshtanov**,

**Marcin Pilipczuk** and

**Erik Jan van Leeuwen**:

Independence and Efficient Domination on P6-free Graphs.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2016.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Dimitrios M. Thilikos**:

Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors.
ACM Transactions on Algorithms. Based on short versions in the Proceedings of SODA 2012 and STACS 2013.

**Daniel Lokshtanov**,

**M. S. Ramanujan** and

**Saket Saurabh**:

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set.
ACM Transactions on Algorithms. Short version in the Proceedings of ICALP 2015.

**Daniel Lokshtanov**,

**Dániel Marx** and

**Saket Saurabh**:

Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2011.

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Fahad Panolan** and

**Saket Saurabh**:

Deterministic Truncation of Linear Matroids.
ACM Transactions on Algorithms. Short version in the Proceedings of ICALP 2015.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Saket Saurabh**,

**Michal Pilipczuk** and

**Marcin Wrochna**:

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth.
ACM Transactions on Algorithms. Short version in the Proceedings of SODA 2017

###
2017

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michal Pilipczuk** and

**Saket Saurabh**:

Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth.
SIAM Journal on Computing. FOCS 2014 Special Issue.

**Rajesh Chitnis**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**M.S. Ramanujan** and

**Saket Saurabh**:

Faster Exact Algorithms for Some Terminal Set Problems.
Journal of Computer and System Sciences. Short version in the Proceedings of IPEC 2013.

**Isolde Adler**,

**Stavros G. Kolliopoulos**,

**Philipp K. Krause**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Dimitrios M. Thilikos**:

Irrelevant Vertices for the planar Disjoint Paths Problem.
Journal of Combinatorial Theory, Series B. Short version in the Proceedings of ICALP 2011.

**Mark Jones**,

**Daniel Lokshtanov**,

**M.S. Ramanujan**,

**Saket Saurabh** and

**Ondej Suchý**:

Parameterized Complexity of Directed Steiner Tree on Sparse Graphs.
SIAM Journal on Discrete Math. Short version in the Proceedings of ESA 2013.

**Sudeshna Kolay**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh**:

Quick but Odd Growth of Cacti.
Algorithmica. Short version in Proceedings of IPEC 2015

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**M. S. Ramanujan**,

**Saket Saurabh**:

Hitting Selected (Odd) Cycles.
SIAM Journal on Discrete Math.

**Archontia C. Giannopoulou**,

**Bart M. P. Jansen**,

**Daniel Lokshtanov**,

**Saket Saurabh**:

Uniform Kernelization Complexity of Hitting Forbidden Minors.
ACM Transactions on Algorithms. Short version in the Proceedings of ICALP 2015.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh**:

Representative Families of Product Families.
ACM Transactions on Algorithms. Short version in Proceedings of ESA 2014.

###
2016

**Olawale Hassan**,

**Iyad Kanj**,

**Daniel Lokshtanov** and

**Ljubomir Perkovic**:

On the Ordered List Subgraph Embedding Problems. Algorithmica. Short version in the Proceedings of IPEC 2013.

**Fedor V. Fomin**,

**Daniel Lokshtanov** and

**Saket Saurabh** Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. Journal of the ACM. Short version in the Proceedings of SODA 2014.

**Hans L. Bodlaender**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Eelko Penninkx**,

**Saket Saurabh** and

**Dimitrios M. Thilikos**:

(Meta) Kernelization. Journal of the ACM. Short version in the Proceedings FOCS 2009.

**Hans L. Bodlaender**,

**Pål G. Drange**,

**Markus S. Dregi**,

**Fedor V. Fomin**,

**Daniel Lokshtanov** and

**Michal Pilipczuk**:

A c^kn 5-Approximation Algorithm for Treewidth. SIAM Journal on Computing. Short version in the Proceedings of FOCS 2013.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Neeldhara Misra**,

**Geevarghese Philip** and

**Saket Saurabh**:

Hitting forbidden minors: Approximation and Kernelization. SIAM Journal on Discrete Math. Short version in the Proceedings of STACS 2011.

**Archontia Giannopoulou**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Ondrej Suchý**:

Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). SIAM Journal on Discrete Math. Short version in the Proceedings of FSTTCS 2014.

**Marek Cygan**,

**Holger Dell**,

**Daniel Lokshtanov**,

**Dániel Marx**,

**Jesper Nederlof**,

**Yoshio Okamoto**,

**Ramamohan Paturi**,

**Saket Saurabh** and

**Magnus Wahlström**:

On Problems as Hard as CNF-SAT. ACM Transactions on Algorithms. Short version in the Proceedings of CCC 2012.

###
2014

**Michael Dom**,

**Daniel Lokshtanov**, and

**Saket Saurabh**:

Kernelization Lower Bounds Through Colors and IDs. ACM Transactions on Algorithms. Short version in the proceedings of ICALP 2009.

**Daniel Lokshtanov**,

**N.S. Narayanaswamy**,

**Venkatesh Raman**,

**M.S. Ramanujan** and

**Saket Saurabh**:

Faster Parameterized Algorithms using Linear Programming. ACM Transactions on Algorithms.

**Fedor Fomin**,

**Petr Golovach**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Almost Optimal Lower Bounds for Problems Parameterized by Clique-width.
SIAM Journal on Computing. Short version in the Proceedings of SODA 2010.

**Pinar Heggernes**,

**Pim van't Hof**,

**Benjamin Lévêque**,

**Daniel Lokshtanov** and

**Christophe Paul**:

Contracting Graphs to Paths and Trees.
Algorithmica. Short version in the Proceedings of IPEC 2011.

**Marek Cygan**,

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michal Pilipczuk** and

**Saket Saurabh**:

On Cutwidth Parameterized by Vertex Cover.
Algorithmica. Short version in the Proceedings of IPEC 2011.

**Marek Cygan**,

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michal Pilipczuk** and

**Saket Saurabh**:

On The Hardness of Losing Width.
Theory of Computing Systems. Short version in the Proceedings of IPEC 2011.

**Christine Lo**,

**Boyko Kakadarov**,

**Daniel Lokshtanov** and

**Christina Boucher**:

SeeSite: Characterizing Relationships Between Splice Junctions and Splicing Enhancers. Trans. Comput. Biology Bioinform. Short version in the Proceedings of APBC 2014.

###
2013

**Daniel Lokshtanov**,

**Neeldhara Misra** and

**Saket Saurabh**:

Imbalance is Fixed Parameter Tractable.
Information Processing Letters. Short version in the Proceedings of COCOON 2010.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Neeldhara Misra**,

**Geevarghese Philip**,

**Saket Saurabh**:

Quadratic Upper Bounds on the Erdos-Posa Property for a Generalization of Packing and Covering Cycles.
Journal of Graph Theory.

**Pinar Heggernes**,

**Dieter Kratsch**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Venkatesh Raman**:

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Information and Computation. Short version in the Proceedings of SWAT 2010.

**Frederic Dorn**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Venkatesh Raman** and

**Saket Saurabh**:

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Information and Computation. Short version in the Proceedings of STACS 2010.

**Pinar Heggernes**,

**Pim van't Hof**,

**Daniel Lokshtanov** and

**Cristophe Paul**:

Obtaining a Bipartite Graph by Contracting Few Edges.
SIAM Journal on Discrete Math. Short version in the Proceedings of FSTTCS 2011.

**Michael R. Fellows**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Elena Losievskaja**,

**Frances A. Rosamond** and

**Saket Saurabh**:

Distortion is Fixed Parameter Tractable.
Transactions on Computation Theory. Short version in the Proceedings of ICALP 2009.

**Daniel Lokshtanov** and

**Dániel Marx**:

Clustering with Local Restrictions. Information and Computation. Short version in the Proceedings of ICALP 2011.

**Fedor V. Fomin**,

** Fabrizio Grandoni**,

**Dieter Kratsch**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Computing Optimal Steiner Trees in Polynomial Space. Algorithmica.

###
2012

**Henning Fernau**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Daniel Raible**,

**Saket Saurabh** and

**Yngve Villanger**:

Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves. ACM Transactions on Algorithms. Short version in the Proceedings of STACS 2009.

**Pinar Heggernes**,

**Pim van't Hof**,

**Daniel Lokshtanov** and

**Jesper Nederlof**:

Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time. SIAM Journal on Discrete Mathematics. Short verion in the Proceedings of WG 2010.

**Fedor V. Fomin**,

** Fabrizio Grandoni**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica. Short version in the Proceedings of LATIN 2010.

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Venkatesh Raman**,

**B.V. Raghavendra Rao** and

**Saket Saurabh**:

Faster Algorithms for Finding and Counting Subgraphs. Journal of Computer and System Sciences.

**Michael R. Fellows**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Frances A. Rosamond**,

**Saket Saurabh** and

**Yngve Villanger**:

Local Search: Is brute-force avoidable?
Journal of Computer and System Sciences. Short Version in the Proceedings of IJCAI 09.

**Fedor V. Fomin**,

**Petr Golovach** and

**Daniel Lokshtanov**:

Cops and Robber game without recharging.
Theory of Computing Systems. Short Version in the Proceedings of SWAT 2010.

###
2011

**Petr A. Golovach**,

**Pinar Heggernes**,

**Dieter Kratsch**,

**Daniel Lokshtanov**,

**Daniel Meister**, and

**Saket Saurabh**:

Bandwidth on AT-free graphs.
Theoretical Computer Science. Short Version in the Proceedings of ISAAC 2009.

**Fedor V. Fomin**,

**Petr A. Golovach** and

**Daniel Lokshtanov**:

Guard games on Graphs: Keep the Intruder Out!
Theoretical Computer Science. Short Version in the Proceedings of WAOA 2009

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Venkatesh Raman** and

**Saket Saurabh**:

Subexponential Algorithms for Partial Cover Problems.
Information Processing Letters. Short version in the Proceedings of FSTTCS 2009.

**Michael R. Fellows**,

**Fedor V.Fomin**,

**Daniel Lokshtanov**,

**Frances A. Rosamond**,

**Saket Saurabh**,

**Stefan Szeider** and

**Carsten Thomassen**:

On the Complexity of Some Colorful Problems Parameterized by Treewidth. Information and Computation. Short version in Proceedings of COCOA 2007.

**Fedor V. Fomin**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

An Exact Algorithm for Minimum Distortion Embedding.
Theoretical Computer Science. Short version in the Proceedings of WG 2009.

**Daniel Lokshtanov**,

** Venkatesh Raman**,

**Saket Saurabh** and

**Somnath Sikdar**:

On the Directed Degree-Preserving Spanning Tree Problem.
Journal of Discrete Optimization. Short version in the Proceedings of IWPEC 2009.

**Oren Ben-Zwi**,

**Danny Hermelin**,

**Daniel Lokshtanov**, and

**Ilan Newman**:

Treewidth governs the complexity of target set selection.
Journal of Discrete Optimization. Short version in thr Proceedings of EC 2009.

**Daniel Lokshtanov**,

**Matthias Mnich** and

**Saket Saurabh**:

A Linear Kernel for Planar Connected Dominating Set. Theoretical Computer Science. TAMC09 special issue. Short version in the Proceedings of TAMC 2009.

**Fedor V. Fomin**,

**Jan Kratochvíl**,

**Daniel Lokshtanov**,

**Federico Mancini** and

**Jan Arne Telle**:

On the Complexity of Reconstructing H-free Graphs from their Star Systems. Journal of Graph Theory. Short version in thr Proceedings of LATIN 2008.

**Pinar Heggernes**,

**Daniel Lokshtanov**,

**Rodica Mihai** and

**Charis Papadopoulos**:

Cutwidth of split graphs and threshold graphs. SIAM Journal on Discrete Mathematics. Short version in the Proceedings of WG 2008.

###
2010

** Fedor V. Fomin**,

**Petr A. Golovach**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Intractability of Clique-width Parameterizations.
SIAM Journal on Computing. Short version in the Proceedings of SODA 2009.

**Daniel Lokshtanov**:

On the Complexity of Computing Treelength.
Discrete Applied Math. Short version in the Proceedings of MFCS 2007.

**Daniel Lokshtanov**,

**Federico Mancini** and

**Charis Papadopoulos**:

Computing and extracting minimal cograph completions in linear time.
Discrete Applied Math. Short version in the Proceedings of FAW 2008.

###
2009

**Michael R. Fellows**,

**Daniel Lokshtanov**,

**Neeldhara Misra**,

**Matthias Mnich**,

**Frances A. Rosamond** and

**Saket Saurabh**:

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. Theory Of Computing Systems. CIE07 special issue.

**Daniel Lokshtanov**:

Finding the longest isometric cycle in a graph.
Discrete Applied Math. WLAB05 special issue.

###
2006

**Pinar Heggernes** and

**Daniel Lokshtanov**:

Optimal broadcast domination of arbitrary graphs in polynomial time.
Discrete Mathematics. Short version in the Proceedings of WG 2005.

## Conference Proceedings

#### (that do not have a journal version)

###
2021

**Peter Gartland**,

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michał Pilipczuk** and

**Paweł Rzążewski**:

Finding large induced sparse subgraphs in C_{>t}-free graphs in quasipolynomial time.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2021).

**Lars Jaffke**,

**Paloma de Lima**,

**Daniel Lokshtanov**:

b-Coloring Parameterized by Clique-Width.:
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2021).

**William Lochet**,

**Daniel Lokshtanov**,

**Saket Saurabh**,

**Meirav Zehavi**:

Exploiting Dense Structures in Parameterized Complexity.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2021).

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).

**Neeraj Kumar**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Subhash Suri**:

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**M. S. Ramanujan**,

**Saket Saurabh** and

**Meirav Zehavi**:

FPT Approximation for FPT Problems.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).

###
2020

**Pratibha Choudhary**,

**Daniel Lokshtanov**,

**Lawqueen Kanesh**,

**Fahad Panolan** and

**Saket Saurabh**:

Parameterized Complexity of Feedback Vertex Sets on Hypergraphs.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020).

**Daniel Lokshtanov**,

**Amer Mouawad**,

**Fahad Panolan** and

**Sebastian Siebertz**:

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets.
Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2020).

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Vaishali Surianarayanan**:

A Parameterized Approximation Scheme for Min k-Cut.
Proceedings of the Symposium on Foundations of Computer Science (FOCS 2020)

**Peter Gartland** and

**Daniel Lokshtanov**:

Independent Set on Pk-Free Graphs in Quasi-Polynomial Time.
Proceedings of the Symposium on Foundations of Computer Science (FOCS 2020)

**Daniel Lokshtanov**,

**Chinmay Sonar**,

**Subhash Suri** and

**Jie Xue**:

Fair Covering of Points by Balls.
Proceedings of the Canadian Conference on Computational Geometry (CCCG 2020).

**Spoorthy Gunda**,

**Pallavi Jain**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Prafullkumar Tale**:

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs.
Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020).

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Ivan Mihajlin**,

**Saket Saurabh** and

**Meirav Zehavi**:

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2020).

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Fahad Panolan**,

**Geevarghese Philip**,

**Saket Saurabh**:

A (2 + ε)-factor Approximation Algorithm for Split Vertex Deletion.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2020).

**Jean R.S. Blair**,

**Pinar Heggernes**,

**Paloma T. Lima** and

**Daniel Lokshtanov**:

On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number.
Proceedings of Latin American Theoretical Informatics Symposium (LATIN 2020).

**Eduard Eiben** and

**Daniel Lokshtanov**:

Removing Connected Obstacles in the Plane is FPT.
Proceedings of the International Symposium on Computational Geometry (SoCG 2020).

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh**, and

**Meirav Zehavi**:

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs.
Proceedings of the International Symposium on Computational Geometry (SoCG 2020).

**Akanksha Agrawal**,

**Kristine Knudsen**,

**Daniel Lokshtanov**,

**Saket Saurabh**, and

**Meirav Zehavi**:

The Parameterized Complexity of Guarding Almost Convex Polygons.
Proceedings of the International Symposium on Computational Geometry (SoCG 2020).

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Michał Pilipczuk**,

**Saket Saurabh**, and

**Meirav Zehavi**:

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2020).

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Hitting Topological Minors is FPT.
Proceedings of the ACM Symposium on Theory of Computing (STOC 2020).

**Fedor Fomin**,

**Petr Golovach**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Parameterization Above a Multiplicative Guarantee.
Proceedings of Innovations in Theoretical Computer Science (ITCS 2020).

**William Lochet**,

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Saket Saurabh**,

**Roohani Sharma** and

**Meirav Zehavi**:

Fault Tolerant Subgraphs with Applications in Kernelization.
Proceedings of Innovations in Theoretical Computer Science (ITCS 2020).

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Joydeep Mukherjee**,

**Fahad Panolan**,

**Geevarghese Philip** and

**Saket Saurabh**:

2-Approximating Feedback Vertex Set in Tournaments.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).

**M. S. Ramanujan**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Parameterized Complexity and Approximability of Directed Odd Cycle Transversal.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).

###
2019

**Gabriel Duarte**,

**Lehilton Pedrosa**,

**Rafael Schouery**,

**Uéverton Souza** and

**Daniel Lokshtanov**:

Computing the largest bond of a graph.
Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2019).

**Fedor Fomin**,

**Petr Golovach**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Going Far From Degeneracy.
Proceedings of European Symposium on Algorithms (ESA 2019).

**Eduard Eiben**,

**Daniel Lokshtanov** and

**Amer Mouawad**:

Bisection of Bounded Treewidth Graphs by Convolutions.
Proceedings of European Symposium on Algorithms (ESA 2019).

**Andreas Björklund**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Approximate Counting of $k$-Paths: Deterministic and in Polynomial Space.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2019).

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Decomposition of Map Graphs with Applications.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2019).

**Fedor Fomin**,

**Petr Golovach**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Meirav Zehavi**:

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2019).

**Akanksha Agrawal**,

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Prafullkumar Tale**:

Path Contraction Faster than 2^n.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2019).

**Daniel Lokshtanov**,

**Ramanujan M. Sridharan**,

**Saket Saurabh**,

**Roohani Sharma** and

**Meirav Zehavi**:

Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for DFVS.
Proceedings of Algorithms and Data Structures Symposium (WADS 2019).

###
2018

**David Eppstein** and

**Daniel Lokshtanov**:

The Parameterized Complexity of Finding Point Sets with Hereditary Properties.
Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2018).

**Daniel Lokshtanov**,

**Mateus de Oliveira Oliveira** and

**Saket Saurabh**:

A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem.
Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2018).

**Timothy Carpenter**,

**Fedor Fomin**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Anastasios Sidiropoulos**:

Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces.
Proceedings of the Symposium on Computational Geometry (SoCG 2018).

**Daniel Lokshtanov**,

**M.S. Ramanujan**,

**Saket Saurabh** and Meirav Zehavi:

Reducing CMSO Model Checking to Highly Connected Graphs.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2018).

**Akanksha Agrawal**,

**Pallavi Jain**,

**Lawqueen Kanesh**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy.
Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity.
Proceedings of Innovations in Theoretical Computer Science (ITCS 2018).

**Akanksha Agrawal**,

**Daniel Lokshtanov**,

**Pranabendu Misra**,

**Saket Saurabh** and

**Meirav Zehavi**:

Erdös-Pósa Property of Obstructions to Interval Graphs.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2018).

**Aritra Banik**,

**Pratibha Choudhary**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Venkatesh Raman**:

A Polynomial Sized Kernel for Tracking Paths Problem.
Proceedings of Latin American Theoretical Informatics (LATIN 2018).

**Daniel Lokshtanov**,

**M. S. Ramanujan** and

**Saket Saurabh**:

When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh**,

**Roohani Sharma**, and

**Meirav Zehavi**:

Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

**Daniel Lokshtanov**,

**Ivan Mikhailin**,

**Ramamohan Paturi** and

**Pavel Pudlak**:

Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

###
2017

**Akanksha Agrawal**,

**R. Krithika**,

**Daniel Lokshtanov**,

**Amer E.
Mouawad** and

**M. S. Ramanujan**:

On the Parameterized Complexity of Simultaneous Deletion Problems.
Proceedings of Foundations of Software Technology and Theoretical Computer Science(FSTTCS 2017).

**Daniel Lokshtanov**,

**Saket Saurabh**,

**Roohani Sharma** and

**Meirav Zehavi**:

Balanced Judicious Bipartition is FPT.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017).

**Christophe Crespelle**,

**Daniel Lokshtanov**,

**Thi Ha Duong Phan** and

**Eric
Thierry**:

Faster and Enhanced Inclusion-Minimal
Cograph Completion.
Proceedings of Conference on Combinatorial Optimization and Applications (COCOA 2017).

**Daniel Lokshtanov**,

**M.S. Ramanujan** and

**Saket Saurabh**:

A Linear-Time Parameterized Algorithm for Node Unique Label Cover.
Proceedings of European Symposium on Algorithms (ESA 2017).

**Akanksha Agrawal**,

**Daniel Lokshtanov** and

**Amer Mouawad**:

Critical node cut parameterized by treewidth and solution size is W[1]-hard.
Proceedings of Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017).

**Daniel Lokshtanov**,

**Amer E. Mouawad**,

**Saket Saurabh** and

**Meirav Zehavi**:

Packing Cycles Faster Than Erdos-Pósa.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2017).

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Fahad Panolan**,

**Saket Saurabh** and

**Meirav Zehavi**:

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs.
Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2017).

**Daniel Lokshtanov**,

**Fahad Panolan**,

**M.S. Ramanujan** and

**Saket Saurabh**:

Lossy Kernelization.
Proceedings of the ACM Symposium on the Theory of Computing (STOC 2017).

**Fedor V. Fomin**,

**Petr A. Golovach**,

**Daniel Lokshtanov** and

**Saket Saurabh**:

Spanning Circuits in Regular Matroids.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).

**Daniel Lokshtanov**,

**Ramamohan Paturi**,

**Suguru Tamaki**,

**R. Ryan Williams** and

**Huacheng Yu**:

Beating Brute Force for Systems of Polynomial Equations over Finite Fields.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).

###
2016

**Mithilesh Kumar** and

**Daniel Lokshtanov**:

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments.
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016).

**Mithilesh Kumar** and

**Daniel Lokshtanov**:

A 2lk Kernel for l-Component Order Connectivity. Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC 2016).

**Fedor V. Fomin**,

**D. Lokshtanov**,

**Dániel Marx**,

**Marcin Pilipczuk**,

**Michal Pilipczuk** and

**Saket Saurabh**:

Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. Proceedings of the Symposium on Foundations of Computer Science (FOCS 2016).

**Marek Cygan**,

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michal Pilipczuk** and

**Saket Saurabh**:

Lower bounds for Approximation Schemes for Closest String. Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016).

**Jakub Gajarský**,

**Petr Hlinený**,

**Daniel Lokshtanov**,

**Jan Obdrzálek** and

**M.S. Ramanujan**:

A New Perspective on FO Model Checking of Dense Graph Classes. Proceedings of Logic in Computer Science (LICS 2016).

**Fedor V. Fomin**,

**Sudeshna Kolay**,

**Daniel Lokshtanov**,

**Fahad Panolan** and

**Saket Saurabh**:

Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Proceedings of the Symposium on Computational Geometry (SoCG 2016).

**Akanksha Agrawal**,

**Daniel Lokshtanov**,

**Amer E. Mouawad** and

**Saket Saurabh**:

Simultaneous Feedback Vertex Set: A Parameterized Perspective. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2016).

**Mithilesh Kumar** and

**Daniel Lokshtanov**:

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2016).

**Pål G. Drange**,

**Markus S. Dregi**,

**Fedor V. Fomin**,

**Stephan Kreutzer**,

**Daniel Lokshtanov**,

**Marcin Pilipczuk**,

**Michal Pilipczuk**,

**Felix Reidl**,

**Fernando S. Villaamil**,

**Saket Saurabh**,

**Sebastian Siebertz** and

**Somnath Sikdar**.

Kernelization and Sparseness: the case of Dominating Set. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2016).

**Akanksha Agrawal**,

**Sudeshna Kolay**,

**Daniel Lokshtanov**, and

**Saket Saurabh**:

A Faster FPT Algorithm and a Smaller Kernel for Block Graph
Vertex Deletion. Proceedings of the Latin American Theoretical Informatics Symposium (LATIN 2016).

###
2015

**Jakub Gajarský**,

**Petr Hlinený**,

**Daniel Lokshtanov**,

**Jan Obdržálek**,

**Sebastian Ordyniak**,

**M.S. Ramanujan** and

**Saket Saurabh**:

FO Model Checking on Posets of Bounded Width. Proceedings of Symposium on Foundations of Computer Science (FOCS 2015).

**Pål G. Drange**,

** Markus S. Dregi**,

**Daniel Lokshtanov** and

**Blair D. Sullivan**:

On the Threshold of Intractability. Proceedings of the European Symposium on Algorithms (ESA 2015).

**Christina Boucher**,

**Christine Lo** and

**Daniel Lokshtanov**:

Consensus Patterns (Probably) Has no EPTAS. Proceedings of the European Symposium on Algorithms (ESA 2015).

**Best ESA Paper Award.**
**Ariel Gabizon**,

**Daniel Lokshtanov** and

**Michal Pilipczuk**:

Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints. Proceedings of the European Symposium on Algorithms (ESA 2015).

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Neeldhara Misra**,

**M.S. Ramanujan** and

**Saket Saurabh**:

Solving d-SAT via Backdoors to Small Treewidth. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).

###
2014

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Ondrej Suchý**:

Solving Multicut Faster than 2^n. Proceedings of European Symposium on Algorithms (ESA 2014).

**Markus S. Dregi** and

**Daniel Lokshtanov**:

Parameterized Complexity of Bandwidth on Trees. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2014).

**Bart Jansen**,

**Daniel Lokshtanov** and

**Saket Saurabh** A Near-Optimal Planarization Algorithm. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).

**Daniel Lokshtanov**,

**Martin Vatshelle** and

**Yngve Villanger** Independent Set in P5-Free Graphs in Polynomial Time. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).

###
2013

**Daniel Lokshtanov**,

**Neeldhara Misra**, and

**Saket Saurabh**:

On the hardness of eliminating small induced subgraphs by contracting edges. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013).

**Hans L. Bodlaender**,

**Paul S. Bonsma** and

**Daniel Lokshtanov**:

The Fine Details of Fast Dynamic Programming over Tree Decompositions. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013).

**Daniel Lokshtanov**,

**Neeldhara Misra**,

**Geevarghese Philip**,

**M.S. Ramanujan** and

**Saket Saurabh**:

Hardness of r-dominating set on graphs of diameter (r + 1). Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013).

**Ravi Kumar**,

**Daniel Lokshtanov**,

**Sergei Vassilvitskii** and

**Andrea Vattani**:

Near-Optimal Bounds for Cross-Validation via Loss Stability. Proceedings of International Conference on Machine Learning (ICML 2013).

###
2012

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Magnus Wahlström**:

Subexponential Parameterized Odd Cycle Transversal on Planar Graphs. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012).

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Neeldhara Misra** and

**Saket Saurabh**:

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. Proceedings of Symposium on Foundations of Computer Science (FOCS 2012).

**Daniel Lokshtanov** and

**M.S. Ramanujan**:

Parameterized Tractability of Multiway Cut with Parity Constraints. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2012).

###
2011

**Daniel Lokshtanov**,

**Matthias Mnich** and

**Saket Saurabh**:

Planar k-Path in Subexponential Time and Polynomial Space. Proceedings of Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011).

**Paul S. Bonsma** and

**Daniel Lokshtanov**:

Feedback Vertex Set in Mixed Graps. Proceedings of the Algorithms and Data Structures Symposium (WADS 2011).

###
2010

**Michael R. Fellows**,

**Bart M. P. Jansen**,

**Daniel Lokshtanov**,

**Frances A Rosamond** and

**Saket Saurabh**:

Determining the Winner of a Dodgson Election is Hard. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010).

**Henning Fernau**,

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Matthias Mnich**,

**Geevarghese Philip** and

**Saket Saurabh**:

Ranking and Drawing in Subexponential Time. Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2010).

**Pinar Heggernes**,

**Daniel Lokshtanov**,

**Jesper Nederlof**,

**Christophe Paul** and

**Jan Arne Telle**:

Generalized graph clustering: recognizing (p,q)-cluster graphs. Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010).

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Venkatesh Raman** and

**Saket Saurabh**:

Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments. Proceedings of the Conference on Artificial Intelligence (AAAI 2010)

**Daniel Lokshtanov** and

**Jesper Nederlof**:

Saving Space by Algebraization. Proceedings of ACM Symposium on Theory of Computing (STOC 2010).

**Fedor V. Fomin**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Dimitrios M. Thilikos**:

Bidimensionality and Kernels. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).

###
2009

**Daniel Lokshtanov** and

**Saket Saurabh**:

Even Faster Algorithm for Set Splitting! Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2009)

**Hans L. Bodlaender**,

**Daniel Lokshtanov** and

**Eelko Penninkx**:

Planar Capacitated Dominating Set is W[1]-hard. Proceedings of the International Workshop on Parameterized and Exact Computation (IWPEC 2009)

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Somnath Sikdar**:

Simpler Parameterized Algorithm for OCT. Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA09)

**Noga Alon**,

**Daniel Lokshtanov**, and

**Saket Saurabh**:

Fast FAST. Proceedings of the International Colloquium on Automata, Languages and Programming, Track A (ICALP09)

###
2008

** Michael R. Fellows**,

**Daniel Lokshtanov**,

**Neeldhara Misra**,

**Frances A. Rosamond** and

**Saket Saurabh**:

Graph Layout problems Parameterized by Vertex Cover. Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2008).

**Michael Dom**,

**Daniel Lokshtanov**,

**Saket Saurabh** and

**Yngve Villanger**:

Capacitated Domination and Covering: A Parameterized Perspective. Proceedings of International Workshop on Exact and Parameterized Computation (IWPEC 2008)

**Daniel Lokshtanov**:

Wheel-free deletion is W[2]-Hard. Proceedings of International Workshop on Exact and Parameterized Computation (IWPEC 2008)

###
2005

**Daniel Lokshtanov** and

**Christian Sloper**:

Fixed Parameter Set Splitting, Obtaining a Linear Kernel and Improving Running Time. Proceedings of Algorithms and Complexity in Durham (ACID 2005).

##
Thesis

**Daniel Lokshtanov**:
Phd Thesis, New Methods in Parameterized Algorithms and Complexity.
Supervised by Pinar Heggernes. Submitted April 2009, Defended June 2009.

**Daniel Lokshtanov**:
Master Thesis, Broadcast Domination.
Supervised by Pinar Heggernes. June 2006.