Surveys
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
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.
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.
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
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 and
Amer E. Mouawad:
The complexity of independent set reconfiguration on bipartite graphs.
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).
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.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
Petr A. Golovach,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth.
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,
Petr A. Golovach,
Daniel Lokshtanov and
Saket Saurabh:
Covering vectors by spaces: Regular matroids (short version).
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).
Akanksha Agrawal,
Daniel Lokshtanov,
Saket Saurabh and
Meirav Zehavi:
Split Contraction: The Untold Story.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2017).
Fedor V. Fomin,
Daniel Lokshtanov,
Syed M. Meesum,
Saket Saurabh and
Meirav Zehavi:
Matrix Rigidity: Matrix Theory from the Viewpoint of Parameterized Complexity.
Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 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).
Fedor V. Fomin,
Daniel Lokshtanov,
Michal Pilipczuk,
Saket Saurabh and
Marcin Wrochna:
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth.
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).
Akanksha Agrawal,
Daniel Lokshtanov,
Pranabendu Misra,
Saket Saurabh and
Meirav Zehavi:
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion.
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 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).
Akanksha Agrawal,
Daniel Lokshtanov,
Diptapriyo Majumdar,
Amer E. Mouawad and
Saket Saurabh:
Kernelization of Cycle Packing with Relaxed Disjointness Constraints. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 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).
Fedor V. Fomin,
Serge Gaspers,
Daniel Lokshtanov and
Saket Saurabh:
Exact Algorithms via Monotone Local Search. Proceedings of the ACM Symposium on the Theory of Computing (STOC 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).
Daniel Lokshtanov,
Marcin Pilipczuk and
Erik Jan van Leeuwen:
Independence and Efficient Domination on P6-free Graphs. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).
2015
Sudeshna Kolay,
Daniel Lokshtanov,
Fahad Panolan and
Saket Saurabh:
Quick but Odd Growth of Cacti. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 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).
Daniel Lokshtanov,
M.S. Ramanujan and
Saket Saurabh:
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2015).
Daniel Lokshtanov,
Pranabendu Misra,
Fahad Panolan and
Saket Saurabh:
Deterministic Truncation of Linear Matroids. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2015).
Fedor V. Fomin,
Petteri Kaski,
Fahad Panolan,
Daniel Lokshtanov and
Saket Saurabh:
Parameterized single-exponential time polynomial space algorithm for Steiner Tree. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2015).
Archontia Giannopoulou,
Bart M. P. Jansen,
Daniel Lokshtanov and
Saket Saurabh:
Uniform Kernelization Complexity of Hitting Forbidden Minors. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2015).
Daniel Lokshtanov,
Amer E. Mouawad,
Fahad Panolan,
M.S. Ramanujan and
Saket Saurabh:
Reconfiguration on sparse graphs. Proceedings of Algorithms and Data Structures Symposium (WADS 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).
Fedor V. Fomin,
Daniel Lokshtanov,
Fahad Panolan and
Saket Saurabh:
Representative Sets of Product Families. 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).
Marek Cygan,
Daniel Lokshtanov,
Marcin Pilipczuk,
Michal Pilipczuk and
Saket Saurabh:
Minimum Bisection is Fixed Parameter Tractable. Proceedings of the ACM Symposium on the Theory of Computing (STOC 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).
Fedor V. Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Dimitrios M. Thilikos:
Linear Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Subgraphs. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 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).
Fedor V. Fomin,
Daniel Lokshtanov,
Saket Saurabh and
Dimitrios M. Thilikos:
Linear Kernels for (Connected) Dominating Set on H-minor-free graphs. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 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).
Daniel Lokshtanov,
Dániel Marx and
Saket Saurabh:
Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Also on
arXiv.
Daniel Lokshtanov, Dániel Marx and Saket Saurabh:
Slightly Superexponential Parameterized Problems. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 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.