Name: What: Where: E-mail: Phone: Fax: Mail Address: |
Daniel Lokshtanov Junior Faculty at UiB Department of Informatics daniello [4t] ii [d0t] uib [d0t] no +47 55 58 41 56 +47 55 58 41 99 Department of Informatics University of Bergen, Norway PB 7803, N-5020 Bergen |
Textbook from Springer: Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh Springer -- Amazon -- Barnes & Noble |
I enjoy hiking, skiing, fantasy, sci-fi, tennis, cognac, parmesan and soccer. A couple (now 10) years ago I starred in Fana school theatre. I'm also involved with the Norwegian high school Informatics Olympiad, NIO. Most of the reasearch I do is in algorithmic graph theory. My Phd. is in parameterized algorithms and complexity. Check out the Parameterized Complexity Wiki. I'm project leader for BeHard, a four year research project on Kernelization funded by Bergen Research Foundation and University of Bergen. |
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. 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. 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. D. Lokshtanov, N.S. Narayanaswamy, V. Raman, M.S. Ramanujan and S. Saurabh: Faster Parameterized Algorithms using Linear Programming. ACM Transactions on Algorithms. Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh: Algorithmic Lower Bounds for Problems Parameterized by Clique-width. SIAM Journal on Computing. Short version in the Proceedings of SODA 2010. P.Heggernes, P.van't Hof, B.Leveque, D.Lokshtanov and C.Paul: Contracting Graphs to Paths and Trees. Algorithmica. Short version in the Proceedings of IPEC 2011. M.Cygan, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk and S.Saurabh: On Cutwidth Parameterized by Vertex Cover. Algorithmica. Short version in the Proceedings of IPEC 2011. M.Cygan, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk and S.Saurabh: On The Hardness of Losing Width. Theory of Computing Systems. Short version in the Proceedings of IPEC 2011. Daniel Lokshtanov, Neeldhara Misra and Saket Saurabh: Imbalance is Fixed Parameter Tractable. Information Processing Letters. Short version in the Proceedings of COCOON 2010. F. Fomin, D. Lokshtanov, N. Misra, G. Philip, S. Saurabh: Quadratic Upper Bounds on the Erdos-Posa Property for a Generalization of Packing and Covering Cycles. Journal of Graph Theory. 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. M.Fellows, F.Fomin, D.Lokshtanov, E.Losievskaja, F.Rosamond and S.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. F.V. Fomin, F. Grandoni, D. Kratsch, D. Lokshtanov and S. Saurabh: Computing Optimal Steiner Trees in Polynomial Space. Algorithmica. H.Fernau, F.Fomin, D.Lokshtanov, D.Raible, S.Saurabh and Y.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 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. F.V.Fomin and Daniel Lokshtanov, V.Raman, B.V.R.Rao and S.Saurabh: Faster Algorithms for Finding and Counting Subgraphs. Journal of Computer and System Sciences. M. Fellows, F. V. Fomin, D.Lokshtanov, F. A. Rosamond, S. Saurabh and Y. 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. P.Golovach, P.Heggernes, D.Kratsch, D.Lokshtanov, D.Meister, and S.Saurabh: Bandwidth on AT-free graphs. Theoretical Computer Science. Short Version in the Proceedings of ISAAC 2009. Fedor V. Fomin, Petr Golovach and Daniel Lokshtanov: Guard games on Graphs: Keep the Intruder Out! Theoretical Computer Science. Short Version in the Proceedings of WAOA 2009 Fedor 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. M.Fellows, F.Fomin, D.Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider and C. 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: Linear Kernel for Planar Connected Dominating Set. Theoretical Computer Science. TAMC09 special issue. Short version in the Proceedings of TAMC 2009. F.Fomin, J.Kratochvíl, D.Lokshtanov, F.Mancini and J.A.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. Fedor Fomin, Petr 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. M.Fellows, D.Lokshtanov, N.Misra, M.Mnich, F.Rosamond and S.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. Pinar Heggernes and Daniel Lokshtanov: Optimal broadcast domination of arbitrary graphs in polynomial time. Discrete Mathematics. Short version in the Proceedings of WG 2005. 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 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.Drange, M.Dregi, F.Fomin, S.Kreutzer, D.Lokshtanov, M.Pilipczuk, M.Pilipczuk, F.Reidl, F.Villaamil, S.Saurabh, S.Siebertz and S.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). 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). J. Gajarský, P. Hlinený, D. Lokshtanov, J. Obdržálek, S. Ordyniak, M. S. Ramanujan and S. 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, Ramanujan M. S. 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 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). D. Lokshtanov, A. Mouawad, F. Panolan, M.S. Ramanujan and S. Saurabh: Reconfiguration on sparse graphs. Proceedings of Algorithms and Data Structures Symposium (WADS 2015). F. Fomin, D. Lokshtanov, N. Misra, Ramanujan M. S. and S. Saurabh: Solving d-SAT via Backdoors to Small Treewidth. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015). Archontia Giannopoulou, Daniel Lokshtanov, Saket Saurabh and Ondrej Suchy: Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 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 Dregi and Daniel Lokshtanov: Parameterized Complexity of Bandwidth on Trees. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2014). M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk and S. Saurabh: Minimum Bisection is Fixed Parameter Tractable. Proceedings of the ACM Symposium on the Theory of Computing (STOC 2014). Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 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). Christine Lo, Boyko Kakadarov, Daniel Lokshtanov and Christina Boucher: SeeSite: Characterizing Relationships Between Splice Junctions and Splicing Enhancers. Proceedings of Asia Pacific Bioinformatics Conference (APBC 2014). 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). Olawale Hassan, Iyad Kanj, Daniel Lokshtanov and Ljubomir Perkovic: On the Ordered List Subgraph Embedding Problems. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013). R. Chitnis, F.V. Fomin, D. Lokshtanov, P. Misra, M.S. Ramanujan and S. Saurabh: Faster Exact Algorithms for Some Terminal Set Problems. Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013). Hans L. Bodlaender, Paul 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). D. Lokshtanov, N. Misra, G. Philip, M.S. Ramanujan and S. Saurabh: Hardness of r-dominating set on graphs of diameter (r + 1). Proceedings of International Symposium on Parameterized and Exact Computation (IPEC 2013). M. Jones, D. Lokshtanov, M.S. Ramanujan, S. Saurabh and O. Suchy: Parameterized Complexity of Directed Steiner Tree on Sparse Graphs. Proceedings of European Symposium on Algorithms (ESA 2013). H.L. Bodlaender, P.G. Drange, M. Dregi, F.V. Fomin, D. Lokshtanov and M.Pilipczuk: A c^kn 5-Approximation Algorithm for Treewidth. Proceedings of Symposium on Foundations of Computer Science (FOCS 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). 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). M.Cygan, H.Dell, D.Lokshtanov, D.Marx, J.Nederlof, Y.Okamoto, R.Paturi, S.Saurabh and M.Wahlström: On Problems as Hard as CNF-SAT. Proceedings of the IEEE Conference on Computational Complexity (CCC 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). Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh: Bidimensionality and Geometric Graphs. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2012). 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). I.Adler, S.G.Kolliopoulos, P.K.Krause, D.Lokshtanov, S.Saurabh and D.Thilikos: Tight Bounds for Linkages in Planar Graphs. Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP 2011). Paul Bonsma and Daniel Lokshtanov: Feedback Vertex Set in Mixed Graps. Proceedings of the Algorithms and Data Structures Symposium (WADS 2011). F.V.Fomin, D.Lokshtanov, N.Misra, G.Philip and S.Saurabh: Hitting forbidden minors: Approximation and Kernelization. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2011). Also on arXiv. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh: Bidimensionality and EPTAS. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Also on arXiv. 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). M.Fellows, B.Jansen, D.Lokshtanov, F.Rosamond and S.Saurabh: Determining the Winner of a Dodgson Election is Hard. Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). H.Fernau, F.V.Fomin, D.Lokshtanov, M. Mnich, G.Philip and S.Saurabh: Ranking and Drawing in Subexponential Time. Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2010). P.Heggernes, D.Lokshtanov, J.Nederlof, C.Paul and J.A.Telle: Generalized graph clustering: recognizing (p,q)-cluster graphs. Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010). Fedor 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) P.Heggernes, D.Kratsch, D.Lokshtanov, S. Saurabh and V.Raman: Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010) Daniel Lokshtanov and Jesper Nederlof: Saving Space by Algebraization. Proceedings of ACM Symposium on Theory of Computing (STOC 2010). F. Dorn,F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh: Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Proceedings of International Symposium on Theoretical Aspects of Computer Science (STACS 2010). Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios M. Thilikos: Bidimensionality and Kernels. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). 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) H.L.Bodlaender, F.V.Fomin, D.Lokshtanov, E.Penninkx, S.Saurabh and D.M.Thilikos: (Meta) Kernelization. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 2009). A full version is on arXiv. 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) M.Fellows, D.Lokshtanov, N.Misra, F. Rosamond and S. 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) 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). 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. June 2006. |