Daniel Lokshtanov

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

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.


Students

Markus Dregi (Phd. Student, 2012 - )
Mithilesh Kumar (Phd. Student, 2014 - )


Postdocs

M.S. Ramanujan




Events

FAW 2014---FPT School, Bedlewo
ICALP 2013---IPEC 2013---Beroun CS Winter School (slides)
SWAT 2012
IPEC 2011 --- MFCS 2011 --- ESA 2011 --- GROW 2011 --- FCT 2011
IPEC 2010 --- MFCS 2010 --- WORKER 2010 --- CIRM Workshop on Graph Decompositions 2010
AGAPE 2009




Teaching

INF237 - Algorithms Engineering, Spring 2014
INF334 - Advanced Algorithms, Fall 2013
INF339 - Seminar Course on Approximation Algorithms, Spring 2013
INF334 - Advanced Algorithms, Fall 2012



Journal Publications

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.



Conference Proceedings

Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh: Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. To appear in the Proceedings of Symposium on Foundations of Computer Science (FOCS 2014).

Daniel Lokshtanov, Saket Saurabh and Ondrej Suchý: Solving Multicut Faster than 2^n. To appear in the Proceedings of European Symposium on Algorithms (ESA 2014).

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh: Representative Sets of Product Families. To appear in the 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).

Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh: Algorithmic Lower Bounds for Problems Parameterized by Clique-width. 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).

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)

Michael Dom, Daniel Lokshtanov, and Saket Saurabh: Incompressibility through Colors and IDs. 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).

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. June 2006.