Daniel Lokshtanov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Daniel Lokshtanov has a total of 79 co-authors. Here are the top co-authors by number of shared publications:
- Saket Saurabh
Institute of Mathematical Sciences
49 shared publications - Fedor V. Fomin
Department of Informatics, University of Bergen
27 shared publications - Dániel Marx
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
20 shared publications - Marcin Pilipczuk
Institute of Informatics, University of Warsaw, Poland
18 shared publications - Marek Cygan
University of Warsaw
17 shared publications - Michał Pilipczuk
University of Warsaw
15 shared publications
Latest Publications
- 7 September 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 288, 138-151
Faster and enhanced inclusion-minimal cograph completion
- 7 September 2020
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 288, 138-151
Faster and enhanced inclusion-minimal cograph completion
- Open Access
Faster and Enhanced Inclusion-Minimal Cograph Completion
We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in $O(n+m')$ time, where $m'$ is the number of edges in the completed graph. This matches the complexity of the algorithm in [Lokshtanov, Mancini and Papadopoulos 2010] and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to $O(n+m\log^2 n)$ when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only $O(n)$ edges, require $\Omega(n^2)$ edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as $O(n/\log^2 n)$.Open AccessFaster and Enhanced Inclusion-Minimal Cograph Completion
We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in $O(n+m')$ time, where $m'$ is the number of edges in the completed graph. This matches the complexity of the algorithm in [Lokshtanov, Mancini and Papadopoulos 2010] and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to $O(n+m\log^2 n)$ when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only $O(n)$ edges, require $\Omega(n^2)$ edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as $O(n/\log^2 n)$. - Open Access
Slightly Superexponential Parameterized Problems
A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot n^{O(1)}$ such that $f$ is as slow growing function of the parameter $k$ as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where $f(k)$ is single-exponential, that is, $c^k$ for some constant $c$, which makes aiming for such a running time a natural goal for other problems as well. However there are still plenty of problems where the $f(k)$ appearing in the best known running time is worse than single-exponential and it remained ``slightly superexponential'' even after serious attempts to bring it down. A natural question to ask is whether the $f(k)$ appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where $f(k)$ is $k^{O(k)}=2^{O(k\log k)}$ in the best known running time and for a number of such problems, we show that the dependence on $k$ in the running time cannot be improved to single exponential. (See paper for the longer abstract.)Open AccessSlightly Superexponential Parameterized Problems
A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot n^{O(1)}$ such that $f$ is as slow growing function of the parameter $k$ as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where $f(k)$ is single-exponential, that is, $c^k$ for some constant $c$, which makes aiming for such a running time a natural goal for other problems as well. However there are still plenty of problems where the $f(k)$ appearing in the best known running time is worse than single-exponential and it remained ``slightly superexponential'' even after serious attempts to bring it down. A natural question to ask is whether the $f(k)$ appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where $f(k)$ is $k^{O(k)}=2^{O(k\log k)}$ in the best known running time and for a number of such problems, we show that the dependence on $k$ in the running time cannot be improved to single exponential. (See paper for the longer abstract.) - Open Access
A New Perspective on FO Model Checking of Dense Graph Classes
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking of any graph class which is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.
Open AccessA New Perspective on FO Model Checking of Dense Graph Classes
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking of any graph class which is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.
- Open Access
Reducing CMSO Model Checking to Highly Connected Graphs
Given a Counting Monadic Second Order (CMSO) sentence $\psi$, the CMSO$[\psi]$ problem is defined as follows. The input to CMSO$[\psi]$ is a graph $G$, and the objective is to determine whether $G\models \psi$. Our main theorem states that for every CMSO sentence $\psi$, if CMSO$[\psi]$ is solvable in polynomial time on "globally highly connected graphs", then CMSO$[\psi]$ is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph $G$ and the task is to find a connected induced subgraph of $G$ such that "few" vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property.Open AccessReducing CMSO Model Checking to Highly Connected Graphs
Given a Counting Monadic Second Order (CMSO) sentence $\psi$, the CMSO$[\psi]$ problem is defined as follows. The input to CMSO$[\psi]$ is a graph $G$, and the objective is to determine whether $G\models \psi$. Our main theorem states that for every CMSO sentence $\psi$, if CMSO$[\psi]$ is solvable in polynomial time on "globally highly connected graphs", then CMSO$[\psi]$ is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph $G$ and the task is to find a connected induced subgraph of $G$ such that "few" vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property. - Open Access
Clustering with Local Restrictions
We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let $\mu$ be a function on the subsets of vertices of a graph $G$. In the $(\mu,p,q)$-PARTITION problem, the task is to find a partition of the vertices into clusters where each cluster $C$ satisfies the requirements that (1) at most $q$ edges leave $C$ and (2) $\mu(C)\le p$. Our first result shows that if $\mu$ is an {\em arbitrary} polynomial-time computable monotone function, then $(\mu,p,q)$-PARTITION can be solved in time $n^{O(q)}$, i.e., it is polynomial-time solvable {\em for every fixed $q$}. We study in detail three concrete functions $\mu$ (the number of vertices in the cluster, number of nonedges in the cluster, maximum number of non-neighbors a vertex has in the cluster), which correspond to natural clustering problems. For these functions, we show that $(\mu,p,q)$-PARTITION can be solved in time $2^{O(p)}\cdot n^{O(1)}$ and in time $2^{O(q)}\cdot n^{O(1)}$ on $n$-vertex graphs, i.e., the problem is fixed-parameter tractable parameterized by $p$ or by $q$.Open AccessClustering with Local Restrictions
We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let $\mu$ be a function on the subsets of vertices of a graph $G$. In the $(\mu,p,q)$-PARTITION problem, the task is to find a partition of the vertices into clusters where each cluster $C$ satisfies the requirements that (1) at most $q$ edges leave $C$ and (2) $\mu(C)\le p$. Our first result shows that if $\mu$ is an {\em arbitrary} polynomial-time computable monotone function, then $(\mu,p,q)$-PARTITION can be solved in time $n^{O(q)}$, i.e., it is polynomial-time solvable {\em for every fixed $q$}. We study in detail three concrete functions $\mu$ (the number of vertices in the cluster, number of nonedges in the cluster, maximum number of non-neighbors a vertex has in the cluster), which correspond to natural clustering problems. For these functions, we show that $(\mu,p,q)$-PARTITION can be solved in time $2^{O(p)}\cdot n^{O(1)}$ and in time $2^{O(q)}\cdot n^{O(1)}$ on $n$-vertex graphs, i.e., the problem is fixed-parameter tractable parameterized by $p$ or by $q$. - Open Access
Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
We give the first linear kernels for the (Connected) Dominating Set problems on H-topological minor free graphs. We prove the existence of polynomial time algorithms that, for a given H-topological-minor-free graph G and a positive integer k, output an H-topological-minor-free graph G' on O(k) vertices such that G has a (connected) dominating set of size k iff G' has one. Our results extend the known classes of graphs on which the Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for Dominating Set, a kernel of size kc(H), where c(H) is a constant depending on the size of H, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for Dominating Set on H-minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For Connected Dominating Set no polynomial kernel even on H-minor-free graphs was known prior to our work. On the negative side, it is known that Connected Dominating Set on 2-degenerated graphs does not admit a polynomial kernel unless coNP $\subseteq$ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; A novel notion of protrusions, different than the one defined in [FOCS 2009]; Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H-minor-free) of the problem, with treewidth $O(\sqrt{k})$. The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels.Open AccessKernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs
We give the first linear kernels for the (Connected) Dominating Set problems on H-topological minor free graphs. We prove the existence of polynomial time algorithms that, for a given H-topological-minor-free graph G and a positive integer k, output an H-topological-minor-free graph G' on O(k) vertices such that G has a (connected) dominating set of size k iff G' has one. Our results extend the known classes of graphs on which the Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for Dominating Set, a kernel of size kc(H), where c(H) is a constant depending on the size of H, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for Dominating Set on H-minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For Connected Dominating Set no polynomial kernel even on H-minor-free graphs was known prior to our work. On the negative side, it is known that Connected Dominating Set on 2-degenerated graphs does not admit a polynomial kernel unless coNP $\subseteq$ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; A novel notion of protrusions, different than the one defined in [FOCS 2009]; Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H-minor-free) of the problem, with treewidth $O(\sqrt{k})$. The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels. - Open Access
Balanced Judicious Partition is Fixed-Parameter Tractable
The family of judicious partitioning problems, introduced by Bollob\'as and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollob\'as and Scott, and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is FPT (which also proves that JB is FPT).
Open AccessBalanced Judicious Partition is Fixed-Parameter Tractable
The family of judicious partitioning problems, introduced by Bollob\'as and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollob\'as and Scott, and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is FPT (which also proves that JB is FPT).
- Open Access
Polylogarithmic Approximation Algorithms for Weighted-$\mathcal{F}$-Deletion Problems
For a family of graphs $\cal F$, the canonical Weighted $\cal F$ Vertex Deletion problem is defined as follows: given an $n$-vertex undirected graph $G$ and a weight function $w: V(G)\rightarrow\mathbb{R}$, find a minimum weight subset $S\subseteq V(G)$ such that $G-S$ belongs to $\cal F$. We devise a recursive scheme to obtain $O(\log^{O(1)}n)$-approximation algorithms for such problems, building upon the classic technique of finding balanced separators in a graph. Roughly speaking, our scheme applies to problems where an optimum solution $S$, together with a well-structured set $X$, form a balanced separator of $G$. We obtain the first $O(\log^{O(1)}n)$-approximation algorithms for the following problems. * We give an $O(\log^2n)$-factor approximation algorithm for Weighted Chordal Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal graphs. On the way, we also obtain a constant factor approximation algorithm for Multicut on chordal graphs. * We give an $O(\log^3n)$-factor approximation algorithm for Weighted Distance Hereditary Vertex Deletion (WDHVD). This is the vertex deletion problem to the family of distance hereditary graphs, or equivalently, the family of graphs of rankwidth 1. Our methods also allow us to obtain in a clean fashion a $O(\log^{1.5}n)$-approximation algorithm for the Weighted $\cal F$ Vertex Deletion problem when $\cal F$ is a minor closed family excluding at least one planar graph. For the unweighted version of the problem constant factor approximation algorithms are were known~[Fomin et al., FOCS~2012], while for the weighted version considered here an $O(\log n \log\log n)$-approximation algorithm follows from~[Bansal et al., SODA~2017]. We believe that our recursive scheme can be applied to obtain $O(\log^{O(1)}n)$-approximation algorithms for many other problems as well.Open AccessPolylogarithmic Approximation Algorithms for Weighted-$\mathcal{F}$-Deletion Problems
For a family of graphs $\cal F$, the canonical Weighted $\cal F$ Vertex Deletion problem is defined as follows: given an $n$-vertex undirected graph $G$ and a weight function $w: V(G)\rightarrow\mathbb{R}$, find a minimum weight subset $S\subseteq V(G)$ such that $G-S$ belongs to $\cal F$. We devise a recursive scheme to obtain $O(\log^{O(1)}n)$-approximation algorithms for such problems, building upon the classic technique of finding balanced separators in a graph. Roughly speaking, our scheme applies to problems where an optimum solution $S$, together with a well-structured set $X$, form a balanced separator of $G$. We obtain the first $O(\log^{O(1)}n)$-approximation algorithms for the following problems. * We give an $O(\log^2n)$-factor approximation algorithm for Weighted Chordal Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal graphs. On the way, we also obtain a constant factor approximation algorithm for Multicut on chordal graphs. * We give an $O(\log^3n)$-factor approximation algorithm for Weighted Distance Hereditary Vertex Deletion (WDHVD). This is the vertex deletion problem to the family of distance hereditary graphs, or equivalently, the family of graphs of rankwidth 1. Our methods also allow us to obtain in a clean fashion a $O(\log^{1.5}n)$-approximation algorithm for the Weighted $\cal F$ Vertex Deletion problem when $\cal F$ is a minor closed family excluding at least one planar graph. For the unweighted version of the problem constant factor approximation algorithms are were known~[Fomin et al., FOCS~2012], while for the weighted version considered here an $O(\log n \log\log n)$-approximation algorithm follows from~[Bansal et al., SODA~2017]. We believe that our recursive scheme can be applied to obtain $O(\log^{O(1)}n)$-approximation algorithms for many other problems as well. - Open Access
The complexity of independent set reconfiguration on bipartite graphs
We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model the problem is NP-complete. For the token sliding model, we show that the problem remains PSPACE-complete.
Open AccessThe complexity of independent set reconfiguration on bipartite graphs
We settle the complexity of the Independent Set Reconfiguration problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model the problem is NP-complete. For the token sliding model, we show that the problem remains PSPACE-complete.