# Daniel Lokshtanov

Professor
• E-maildaniel.lokshtanov@uib.no
• Phone+47 55 58 41 56
HIB - Thormøhlens gate 55
5006 Bergen
Postboks 7803
5020 Bergen
Textbook
• Show author(s) (2019). Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press.
• Show author(s) (2022). On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number. Algorithmica.
• Show author(s) (2022). Erdős–Pósa property of obstructions to interval graphs. Journal of Graph Theory.
• Show author(s) (2021). b-Coloring Parameterized by Clique-Width. Leibniz International Proceedings in Informatics. 43:1-43:15.
• Show author(s) (2021). On the threshold of intractability. Journal of computer and system sciences. 1-25.
• Show author(s) (2021). On the Parameterized Approximability of Contraction to Classes of Chordal Graphs. ACM Transactions on Computation Theory. 1-40.
• Show author(s) (2021). Faster and enhanced inclusion-minimal cograph completion. Discrete Applied Mathematics. 138-151.
• Show author(s) (2021). FPT-approximation for FPT Problems. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 199-218.
• Show author(s) (2021). Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version). Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 179-198.
• Show author(s) (2021). Diversity in Kemeny Rank Aggregation: A Parameterized Approach. IJCAI International Joint Conference on Artificial Intelligence. 10-16.
• Show author(s) (2021). Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. ACM Transactions on Computation Theory. 10:1-10:25.
• Show author(s) (2021). A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 822-839.
• Show author(s) (2021). 2-Approximating Feedback Vertex Set in Tournaments. ACM Transactions on Algorithms (TALG). 11:1-11:14.
• Show author(s) (2020). The Parameterized Complexity of Guarding Almost Convex Polygons. Leibniz International Proceedings in Informatics. 3:1-3:16.
• Show author(s) (2020). Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. ACM Transactions on Algorithms (TALG). 37 pages.
• Show author(s) (2020). Polylogarithmic Approximation Algorithms for Weighted-F-deletion Problems. ACM Transactions on Algorithms (TALG). 1-38.
• Show author(s) (2020). Path contraction faster than \$2^n\$. SIAM Journal on Discrete Mathematics. 1302-1325.
• Show author(s) (2020). Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 20 pages.
• Show author(s) (2020). Parameterization Above a Multiplicative Guarantee . Leibniz International Proceedings in Informatics. 39:1-39:13.
• Show author(s) (2020). On the maximum number of edges in chordal graphs of bounded degree and matching number. Lecture Notes in Computer Science (LNCS). 600-612.
• Show author(s) (2020). Hitting Topological Minors Is FPT. Proceedings of the Annual ACM Symposium on Theory of Computing. 1317-1326.
• Show author(s) (2020). Fault tolerant subgraphs with applications in kernelization. Leibniz International Proceedings in Informatics. 47:1-47:22.
• Show author(s) (2020). ETH-tight algorithms for long path and cycle on unit disk graphs. Leibniz International Proceedings in Informatics. 44:1-44:18.
• Show author(s) (2020). Bidimensionality and Kernels. SIAM journal on computing (Print). 1397-1422.
• Show author(s) (2020). Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 2299-2318.
• Show author(s) (2020). A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion. Leibniz International Proceedings in Informatics. 80:1-80:16.
• Show author(s) (2020). 2-Approximating Feedback Vertex Set in Tournaments. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1010-1018.
• Show author(s) (2019). The parameterized complexity of finding point sets with hereditary properties. Leibniz International Proceedings in Informatics.
• Show author(s) (2019). Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. ACM Transactions on Algorithms (TALG). 44 pages.
• Show author(s) (2019). Split contraction: The untold story. ACM Transactions on Computation Theory.
• Show author(s) (2019). Spanning circuits in regular matroids. ACM Transactions on Algorithms (TALG).
• Show author(s) (2019). Path Contraction Faster Than 2n. Leibniz International Proceedings in Informatics. 11:1-11:13.
• Show author(s) (2019). Packing cycles faster than Erdos-Posa. SIAM Journal on Discrete Mathematics. 1194-1215.
• Show author(s) (2019). Minimum Bisection Is Fixed-Parameter Tractable. SIAM journal on computing (Print). 417-450.
• Show author(s) (2019). Going Far From Degeneracy. Leibniz International Proceedings in Informatics. 47:1-47:14.
• Show author(s) (2019). Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. Discrete & Computational Geometry. 879-911.
• Show author(s) (2019). Exact algorithms via monotone local search. Journal of the ACM. 8:1-8:23.
• Show author(s) (2019). Decomposition of map graphs with applications. Leibniz International Proceedings in Informatics. 60:1-60:15.
• Show author(s) (2019). Balanced judicious bipartition is fixed-parameter tractable. SIAM Journal on Discrete Mathematics. 1878-1911.
• Show author(s) (2019). A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem. Leibniz International Proceedings in Informatics.
• Show author(s) (2018). The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms (TALG). 1-19.
• Show author(s) (2018). Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs. Algorithmica. 421-438.
• Show author(s) (2018). Slightly superexponential parameterized problems. SIAM journal on computing (Print). 675-702.
• Show author(s) (2018). Simultaneous feedback vertex set: A parameterized perspective. ACM Transactions on Computation Theory.
• Show author(s) (2018). Reducing CMSO model checking to highly connected graphs. Leibniz International Proceedings in Informatics. 135:1-135:14.
• Show author(s) (2018). Reconfiguration on sparse graphs. Journal of computer and system sciences. 122-131.
• Show author(s) (2018). Quasipolynomial representation of transversal matroids with applications in parameterized complexity. Leibniz International Proceedings in Informatics. 1-13.
• Show author(s) (2018). Polylogarithmic approximation algorithms for weighted-F-Deletion problems. Leibniz International Proceedings in Informatics. 1:1-1:15.
• Show author(s) (2018). On the parameterized complexity of simultaneous deletion problems. Leibniz International Proceedings in Informatics. 9:1-9:14.
• Show author(s) (2018). Matrix rigidity from the viewpoint of parameterized complexity . SIAM Journal on Discrete Mathematics. 966-985.
• Show author(s) (2018). Long directed (s,t)-path: FPT algorithm. Information Processing Letters. 8-12.
• Show author(s) (2018). Linear time parameterized algorithms for subset feedback vertex set. ACM Transactions on Algorithms (TALG). 37 pages.
• Show author(s) (2018). Known algorithms on graphs of bounded treewidth are probably optimal. ACM Transactions on Algorithms (TALG). 1-30.
• Show author(s) (2018). Kernels for (Connected) dominating set on graphs with excluded topological minors. ACM Transactions on Algorithms (TALG).
• Show author(s) (2018). Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG).
• Show author(s) (2018). Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion. ACM Transactions on Algorithms (TALG). 28 pages.
• Show author(s) (2018). Excluded grid minors and efficient polynomial-time approximation schemes. Journal of the ACM. 1-44.
• Show author(s) (2018). Erdos-Posa property of obstructions to interval graphs. Leibniz International Proceedings in Informatics. 1-15.
• Show author(s) (2018). Covering Vectors by Spaces: Regular Matroids. SIAM Journal on Discrete Mathematics. 2512-2565.
• Show author(s) (2018). Conflict Free Feedback Vertex Set: A Parameterized Dichotomy. Leibniz International Proceedings in Informatics. 53:1-53:15.
• Show author(s) (2018). Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 262-273.
• Show author(s) (2018). Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG). 27 pages.
• Show author(s) (2018). Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS. Leibniz International Proceedings in Informatics. 110:1-110:4.
• Show author(s) (2018). Below all subsets for minimal connected dominating set. SIAM Journal on Discrete Mathematics. 2332-2345.
• Show author(s) (2018). Balanced judicious bipartition is fixed-paramater tractable. Leibniz International Proceedings in Informatics. 40:1-40:15.
• Show author(s) (2018). Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. Leibniz International Proceedings in Informatics. 21:1-21:14.
• Show author(s) (2018). A polynomial sized kernel for tracking paths problem. Lecture Notes in Computer Science (LNCS). 94-107.
• Show author(s) (2017). Uniform kernelization complexity of hitting forbidden minors. ACM Transactions on Algorithms (TALG). 1-35.
• Show author(s) (2017). Split contraction: The untold story. Leibniz International Proceedings in Informatics. 1-14.
• Show author(s) (2017). Spanning Circuits in Regular Matroids. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 1433-1441.
• Show author(s) (2017). Representative families of product families. ACM Transactions on Algorithms (TALG). 1-29.
• Show author(s) (2017). Quick but Odd Growth of Cacti. Algorithmica. 271-290.
• Show author(s) (2017). Parameterized complexity of directed Steiner tree on sparse graphs. SIAM Journal on Discrete Mathematics. 1294-1327.
• Show author(s) (2017). Packing cycles faster than Erdös-Pósa. Leibniz International Proceedings in Informatics. 1-15.
• Show author(s) (2017). Matrix rigidity from the viewpoint of parameterized complexity. Leibniz International Proceedings in Informatics.
• Show author(s) (2017). Lossy kernelization. Proceedings of the Annual ACM Symposium on Theory of Computing. 224-237.
• Show author(s) (2017). Irrelevant vertices for the planar Disjoint Paths Problem. Journal of combinatorial theory. Series B (Print). 815-843.
• Show author(s) (2017). Independence and efficient domination on P6-free graphs. ACM Transactions on Algorithms (TALG).
• Show author(s) (2017). Hitting selected (ODD) Cycles. SIAM Journal on Discrete Mathematics. 1581-1615.
• Show author(s) (2017). Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM journal on computing (Print). 161-189.
• Show author(s) (2017). Finding, hitting and packing cycles in subexponential time on unit disk graphs. Leibniz International Proceedings in Informatics. 1-15.
• Show author(s) (2017). Faster exact algorithms for some terminal set problems. Journal of computer and system sciences. 195-207.
• Show author(s) (2017). Critical node cut parameterized by treewidth and solution size is W[1]-Hard. Lecture Notes in Computer Science (LNCS). 32-44.
• Show author(s) (2017). Covering vectors by spaces: Regular matroids. Leibniz International Proceedings in Informatics. 1-15.
• Show author(s) (2017). A linear-Time parameterized algorithm for node unique label cover. Leibniz International Proceedings in Informatics.
• Show author(s) (2017). A 2lk kernel for l-component order connectivity. Leibniz International Proceedings in Informatics. 1-14.
• Show author(s) (2016). Tree deletion set has a polynomial kernel (but No OPTο(1) Approximation). SIAM Journal on Discrete Mathematics. 1371-1384.
• Show author(s) (2016). Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Leibniz International Proceedings in Informatics. 39.1-39.15.
• Show author(s) (2016). Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 515-524.
• Show author(s) (2016). SIMULTANEOUS Feedback Vertex set: A parameterized perspective. Leibniz International Proceedings in Informatics. 7:1-7:15.
• Show author(s) (2016). On the ordered list subgraph embedding problems. Algorithmica. 992-1018.
• Show author(s) (2016). On problems as hard as CNF-SAT. ACM Transactions on Algorithms (TALG).
• Show author(s) (2016). Lower bounds for approximation schemes for closest string. Leibniz International Proceedings in Informatics. 12.1-12.10.
• Show author(s) (2016). Kernelization of cycle packing with relaxed disjointness constraints. Leibniz International Proceedings in Informatics. 1-14.
• Show author(s) (2016). Kernelization and sparseness: The case of dominating set. Leibniz International Proceedings in Informatics. 14 pages.
• Show author(s) (2016). Hitting forbidden minors: Approximation and kernelization. SIAM Journal on Discrete Mathematics. 383-410.
• Show author(s) (2016). Faster exact and parameterized algorithm for feedback vertex set in tournaments. Leibniz International Proceedings in Informatics. 24.1-24.15.
• Show author(s) (2016). Exact algorithms via monotone local search. Proceedings of the Annual ACM Symposium on Theory of Computing. 764-775.
• Show author(s) (2016). Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM.
• Show author(s) (2016). A new perspective on FO model checking of dense graph classes. Logic in Computer Science. 176-184.
• Show author(s) (2016). A faster FPT algorithm and a smaller kernel for block graph vertex deletion. Lecture Notes in Computer Science (LNCS). 1-13.
• Show author(s) (2016). A \$c^k n\$ 5-approximation algorithm for treewidth. SIAM journal on computing (Print). 317-378.
• Show author(s) (2016). (Meta) Kernelization. Journal of the ACM.
• Show author(s) (2015). Uniform kernelization complexity of hitting forbidden minors. Lecture Notes in Computer Science (LNCS). 629-641.
• Show author(s) (2015). Reconfiguration on sparse graphs. Lecture Notes in Computer Science (LNCS). 506-517.
• Show author(s) (2015). Quick but odd growth of cacti. Leibniz International Proceedings in Informatics. 258-269.
• Show author(s) (2015). Parameterized single-exponential time polynomial space algorithm for steiner tree. Lecture Notes in Computer Science (LNCS). 494-505.
• Show author(s) (2015). On the threshold of intractability. Lecture Notes in Computer Science (LNCS). 411-423.
• Show author(s) (2015). Linear time parameterized algorithms for subset feedback vertex set. Lecture Notes in Computer Science (LNCS). 935-946.
• Show author(s) (2015). Fast algorithms for parameterized problems with relaxed disjointness constraints. Lecture Notes in Computer Science (LNCS). 545-556.
• Show author(s) (2015). Deterministic truncation of linear matroids. Lecture Notes in Computer Science (LNCS). 922-934.
• Show author(s) (2015). Consensus patterns (Probably) has no EPTAS. Lecture Notes in Computer Science (LNCS). 239-250.
• Show author(s) (2014). Tree deletion set has a polynomial kernel (but no OPTO(1) approximation). Leibniz International Proceedings in Informatics. 85-96.
• Show author(s) (2014). Solving Multicut faster than 2n. Lecture Notes in Computer Science (LNCS). 666-676.
• Show author(s) (2014). Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology. 374-386.
• Show author(s) (2014). Representative sets of product families. Lecture Notes in Computer Science (LNCS). 443-454.
• Show author(s) (2014). On cutwidth parameterized by vertex cover. Algorithmica. 940-953.
• Show author(s) (2014). Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms (TALG).
• Show author(s) (2014). Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG).
• Show author(s) (2014). Contracting graphs to paths and trees. Algorithmica. 109-132.
• Show author(s) (2014). Almost optimal lower bounds for problems parameterized by clique-width. SIAM journal on computing (Print). 1541-1563.
• Show author(s) (2013). Quadratic upper bounds on the Erdős–Pósa property for a generalization of packing and covering cycles. Journal of Graph Theory. 417-424.
• Show author(s) (2013). Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics. 2143-2156.
• Show author(s) (2013). Imbalance is fixed parameter tractable. Information Processing Letters.
• Show author(s) (2013). Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Information and Computation. 109-116.
• Show author(s) (2013). Computing optimal Steiner trees in polynomial space. Algorithmica. 584-604.
• Show author(s) (2013). Clustering with local restrictions. Information and Computation. 278-292.
• Show author(s) (2013). Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Information and Computation. 60-70.
• Show author(s) (2013). An O(c^k n) 5-approximation algorithm for treewidth. Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 499-508.
• Show author(s) (2012). Sharp separation and applications to exact and parameterized algorithms. Algorithmica. 692-706.
• Show author(s) (2012). Planar F-deletion: Approximation, kernelization and optimal FPT algorithms (extended abstract). Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS). 470-479.
• Show author(s) (2012). On Cutwidth Parameterized by Vertex Cover. Algorithmica.
• Show author(s) (2012). Kernel(s) for Problems with no Kernel: On Out-Trees with Many Leaves. ACM Transactions on Algorithms (TALG). 19 pages.
• Show author(s) (2012). Faster algorithms for finding and counting subgraphs. Journal of computer and system sciences. 698-706.
• Show author(s) (2012). Cops and robber game without recharging. Theory of Computing Systems. 611-620.
• Show author(s) (2012). Contracting graphs to paths and trees. Lecture Notes in Computer Science (LNCS). 55-66.
• Show author(s) (2012). Computing the cutwidth of bipartite permutation graphs in linear time. SIAM Journal on Discrete Mathematics. 1008-1021.
• Show author(s) (2011). Treewidth governs the complexity of target set selection. Discrete Optimization. 87-96.
• Show author(s) (2011). Subexponential algorithms for partial cover problems. Information Processing Letters. 814-818.
• Show author(s) (2011). On the directed Full Degree Spanning Tree problem. Discrete Optimization. 97-109.
• Show author(s) (2011). On the complexity of some colorful problems parameterized by treewidth. Information and Computation. 143-153.
• Show author(s) (2011). On the Complexity of Reconstructing H-Free Graphs from Their Star Systems. Journal of Graph Theory. 113-124.
• Show author(s) (2011). Guard games on graphs: Keep the intruder out! Theoretical Computer Science. 6484-6497.
• Show author(s) (2011). Cutwidth of Split Graphs and Threshold Graphs. SIAM Journal on Discrete Mathematics. 1418-1437.
• Show author(s) (2011). Bandwidth on AT-free graphs. Theoretical Computer Science. 7001-7008.
• Show author(s) (2011). An exact algorithm for minimum distortion embedding. Theoretical Computer Science. 3530-3536.
• Show author(s) (2011). A linear kernel for a planar connected dominating set. Theoretical Computer Science. 2536-2543.
• Show author(s) (2010). On the complexity of computing treelength. Discrete Applied Mathematics. 820-827.
• Show author(s) (2010). Intractability of clique-width parameterizations. SIAM journal on computing (Print). 1941-1956.
• Show author(s) (2010). Imbalance is fixed parameter tractable. Lecture Notes in Computer Science (LNCS). 199-208.
• Show author(s) (2010). Generalized graph clustering: recognizing (p,q)-cluster graphs. Lecture Notes in Computer Science (LNCS). 171-183.
• Show author(s) (2010). Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Lecture Notes in Computer Science (LNCS). 334-345.
• Show author(s) (2010). Computing the cutwidth of bipartite permutation graphs in linear time. Lecture Notes in Computer Science (LNCS). 75-87.
• Show author(s) (2010). Characterizing and computing minimal cograph completions. Discrete Applied Mathematics. 755-764.
• Show author(s) (2010). Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Leibniz International Proceedings in Informatics. 251-262.
• Show author(s) (2010). Algorithmic Lower Bounds for Problems on Decomposable Graphs. Lecture Notes in Computer Science (LNCS). 37.
• Show author(s) (2009). The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems. 822-848.
• Show author(s) (2009). Subexponential Algorithms for Partial Cover Problems. Leibniz International Proceedings in Informatics. 193-201.
• Show author(s) (2009). Simpler Parameterized Algorithm for OCT. Lecture Notes in Computer Science (LNCS). 380-384.
• Show author(s) (2009). On the Directed Degree-Preserving Spanning Tree Problem. Lecture Notes in Computer Science (LNCS). 276-287.
• Show author(s) (2009). Linear Kernel for Planar Connected Dominating Set. Lecture Notes in Computer Science (LNCS). 281-290.
• Show author(s) (2009). Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Leibniz International Proceedings in Informatics. 421-432.
• Show author(s) (2009). Incompressibility through Colors and IDs. Lecture Notes in Computer Science (LNCS). 378-389.
• Show author(s) (2009). Finding the longest isometric cycle in a graph. Discrete Applied Mathematics. 2670-2674.
• Show author(s) (2009). Fast FAST. Lecture Notes in Computer Science (LNCS). 49-58.
• Show author(s) (2009). Even Faster Algorithm for Set Splitting! Lecture Notes in Computer Science (LNCS). 288-299.
• Show author(s) (2009). Distortion Is Fixed Parameter Tractable. Lecture Notes in Computer Science (LNCS). 463-474.
• Show author(s) (2009). Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science (LNCS). 573-582.
• Show author(s) (2009). An Exact Algorithm for Minimum Distortion Embedding. Lecture Notes in Computer Science (LNCS). 112-121.
• Show author(s) (2008). Wheel-free deletion is W[2]-Hard. Lecture Notes in Computer Science (LNCS). 141-147.
• Show author(s) (2008). On the complexity of reconstructing H-free graphs from their Star Systems. Lecture Notes in Computer Science (LNCS). 194-205.
• Show author(s) (2008). Graph Layout problems Parameterized by Vertex Cover. Lecture Notes in Computer Science (LNCS). 294-305.
• Show author(s) (2008). Cutwidth of split graphs, threshold graphs, and proper interval graphs. Lecture Notes in Computer Science (LNCS). 218-229.
• Show author(s) (2008). Characterizing and Computing Minimal Cograph Completions. Lecture Notes in Computer Science (LNCS). 147-158.
• Show author(s) (2008). Capacitated Domination and Covering: A Parameterized Perspective. Lecture Notes in Computer Science (LNCS). 78-90.
• Show author(s) (2007). On the Complexity of Computing Treelength. Lecture Notes in Computer Science (LNCS). 276-287.
• Show author(s) (2006). Optimal broadcast domination in polynomial time. Discrete Mathematics. 3267-3280.
Editorial
• Show author(s) (2018). Preface. Leibniz International Proceedings in Informatics.