Arrow Research search

Author name cluster

Daniel Lokshtanov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

86 papers
2 author rows

Possible papers

86

STOC Conference 2025 Conference Paper

Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs

  • Daniel Lokshtanov
  • Fahad Panolan
  • Saket Saurabh 0001
  • Jie Xue 0003
  • Meirav Zehavi

Graph classes of bounded expansion were introduced by Nešetřil and de Mendez as a general model of structurally sparse graphs, which have received considerable attention from both combinatorial and algorithmic perspectives. A celebrated result of Dvořák et al. [JACM’13] showed that any first-order model checking problem on bounded-expansion graph classes is fixed-parameter tractable. A main drawback of the FPT algorithms resulted from this result is the high dependency of their time complexity on the parameter k : the algorithms run in time at least doubly exponential in k , even when the graph class is of polynomial expansion. It is natural to ask whether there exist FPT algorithms for these problem that run in singly exponential time, i.e., 2 k O (1) n O (1) time. In this paper, we give a new algorithmic framework for a broad family of first-order model checking problems on sparse graphs, which results in algorithms with running time 2 k O (1) · n when the graph class is of exponential expansion (i.e., the expansion is bounded by a singly exponential function). This covers most well-studied instances of bounded-expansion graph classes, in particular, all polynomial-expansion graph classes. Our framework applies to all problems that can be formulated as finding k vertices in a host graph G with certain distance constraints . Furthermore, the framework can be generalized to give (1 ± ε)-approximation algorithms for the counting versions of these problems with running time 2 k O (1) · n (log n /ε) O (1) on exponential-expansion graph classes. In terms of techniques, our framework differs entirely from the one of Dvořák et al. based on centered coloring. We develop various technical components based on the theory of sparse graphs and other tools such as representative sets/functions, tree decomposition, inclusion-exclusion, etc., which are of independent interest. Remarkably, some of our techniques can be applied to even more general graph classes, such as degenerate graph classes. Therefore, as a byproduct, we obtain a (1 ± ε)-approximation algorithm for approximately counting bounded-treewidth induced subgraphs in degenerate graphs with running time k O ( k ) · ( n /ε) O (1) . This resolves (in a much stronger form) an open problem of Bressan and Roth [FOCS’22], which asked whether such an algorithm exists for counting induced k -matching in degenerate graphs.

Details

MFCS Conference 2025 Conference Paper

Quasipolynomial-Time Deterministic Kernelization and (Gammoid) Representation

  • Rohit Gurjar
  • Daniel Lokshtanov
  • Pranabendu Misra
  • Fahad Panolan
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper, we suggest to extend the notion of a kernel to permit the kernelization algorithm to be executed in quasi-polynomial time rather than polynomial time. So far, we are only aware of one work that addressed this negatively, showing that some lower bounds on kernel sizes proved for kernelization also hold when quasi-polynomial time complexity is allowed. When we, anyway, deal with an NP-hard problem, sacrificing polynomial time in preprocessing for quasi-polynomial time may often not be a big deal, but, of course, the question is - does it give us more power? The only known work, mentioned above, seems to suggest that the answer is "no". In this paper, we show that this is not the case - in particular, we show that this notion is extremely powerful for derandomization. Some of the most basic kernelization algorithms in the field are based on inherently randomized tools whose derandomization is a huge problem that has remained (and may still remain) open for many decades. Still, some breakthrough advances for derandomization in quasi-polynomial time have been made. Can we harness these advancements to design quasi-polynomial deterministic kernelization algorithms for basic problems in the field? To this end, we revisit the question of deterministic polynomial-time computation of a linear representation of transversal matroids and gammoids, which is a longstanding open problem. We present a deterministic computation of a representation matrix of a transversal matroid in time quasipolynomial in the rank of the matroid, where each entry of the matrix can be represented in quasipolynomial (in the rank of the matroid) bits. As a corollary, we obtain a linear representation of a gammoid in deterministic quasipolynomial time and quasipolynomial bits in the size of the underlying ground set of the gammoid. In turn, as applications of our results, we present deterministic quasi-polynomial time kernels of polynomial size for several central problems in the field.

Details

FOCS Conference 2024 Conference Paper

Efficient Approximation of Fractional Hypertree Width

  • Viktoriia Korchemna
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Vaishali Surianarayanan
  • Jie Xue 0003

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input n-vertex m-edge hypergraph $H$ of fractional hypertree width at most $\omega$, runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $\mathcal{O}(\omega\log n\log\omega)$, i. e. , it is an $\mathcal{O}(\log n\log\omega)$ -approximation algorithm. As an immediate corollary this yields poly-nomial time $\mathcal{O}(\log^{2}n\log\omega)$ -approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $\omega$ is considered a constant. For hypergraphs where every pair of hyperedges have at most $\eta$ vertices in common, the al-gorithm outputs a hypertree decomposition with fractional hypertree width $\mathcal{O}(\eta\omega^{2}\log\omega)$ and generalized hypertree width $\mathcal{O}(\eta\omega^{2}\log\omega(\log\eta+\text{log}\omega))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width ${\mathcal{O}}(\omega^{2}(\omega+\eta))$, but uses time (at least) exponential in $\eta$ and $\omega$. The second algorithm runs in time $n^{\omega}m^{\mathcal{O}(1)}$ and pro-duces a tree decomposition of $H$ of fractional hypertree width $\mathcal{O}(\omega{\mathrm{l}}\text{og}^{2}\omega)$. This significantly improves over the $(n+m)^{\mathcal{O}(\omega^{3})}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hyper-tree width $\mathcal{O}(\omega^{3})$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph $G$, vertex sets $A$ and $B$, family $\mathcal{F}$ of cliques in $G$, and positive rational $f$, either there exists a sub-family of $\mathcal{O}(f \cdot {\mathrm{l}}\text{og}^{2}n)$ cliques in $\mathcal{F}$ whose union separates $A$ from $B$, or there exist $f\cdot\log\vert \mathcal{F}\vert$ paths from $A$ to $B$ such that no clique in $\mathcal{F}$ intersects more than $\log\vert \mathcal{F}\vert$ paths.

Details

SODA Conference 2024 Conference Paper

Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition

  • Tuukka Korhonen
  • Daniel Lokshtanov

A graph G contains a graph H as an induced minor if H can be obtained from G by vertex deletions and edge contractions. The class of H -induced-minor-free graphs generalizes the class of H -minor-free graphs, but unlike H -minor-free graphs, it can contain dense graphs. We show that if an n -vertex m -edge graph G does not contain a graph H as an induced minor, then it has a balanced vertex separator of size, where the O H (·)-notation hides factors depending on H. More precisely, our upper bound for the size of the balanced separator is. We give an algorithm for finding either an induced minor model of H in G or such a separator in randomized polynomial-time. We apply this to obtain subexponential time algorithms on H -induced-minor-free graphs for a large class of problems including maximum independent set, minimum feedback vertex set, 3-coloring, and planarization. For graphs H where every edge is incident to a vertex of degree at most 2, our results imply a time algorithm for testing if G contains H as an induced minor. Our second main result is that there exists a fixed tree T, so that there is no time algorithm for testing if a given n -vertex graph contains T as an induced minor unless the Exponential Time Hypothesis (ETH) fails. Our reduction also gives NP-hardness, which solves an open problem asked by Fellows, Kratochvíl, Middendorf, and Pfeiffer [Algorithmica, 1995], who asked if there exists a fixed planar graph H so that testing for H as an induced minor is NP-hard. * The research leading to these results has received funding from the Research Council of Norway via the project BWCA (grant no. 314528) and NSF award CCF-2008838.

Details

STOC Conference 2024 Conference Paper

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

  • Peter Gartland
  • Daniel Lokshtanov
  • Tomás Masarík
  • Marcin Pilipczuk
  • Michal Pilipczuk
  • Pawel Rzazewski

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H -free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F -free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let S t , t , t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G , one can in polynomial time find either an induced S t , t , t in G , or a balanced separator consisting of O (log| V ( G )|) vertex neighborhoods in G , or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G . This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O (log| V ( G )|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

Details

IJCAI Conference 2024 Conference Paper

Parameterized Complexity of Kidney Exchange Revisited

  • Úrsula Hébert-Johnson
  • Daniel Lokshtanov
  • Chinmay Sonar
  • Vaishali Surianarayanan

As of January 2023, there are more than 90, 000 people on the national transplant waiting list in need of a kidney in the United States. These patients often have a friend or family member who is willing to donate, but whose kidney type might not be compatible. To help match these patients to suitable donors, patient-donor compatibility can be modeled as a directed graph. Specifically, in the Kidney Exchange problem, the input is a directed graph G, a subset B of vertices (altruistic donors), and two integers l_p and l_c. An altruistic donor is a donor who is not paired with a patient, and the remaining vertices are patient-donor pairs. Whenever a donor is compatible with a patient from a patient-donor pair, we place a directed edge from the donor vertex to the patient-donor pair. Here the donor vertex can be either altruistic or non-altruistic. The goal is to find a collection of vertex-disjoint cycles and paths covering the maximum number of patients such that each cycle has length at most l_c, and such that each path has length at most l_p and begins at a vertex in B. The path and cycle lengths are bounded so that the surgeries for a given path or cycle can be performed simultaneously. Kidney Exchange has received a great deal of attention in recent years. We contribute to this line of work by closing two open problems from IJCAI '18 and IJCAI '22: "Is Kidney Exchange FPT when parameterized by (i) the treewidth (omega) of G and (ii) the number of vertex types in G? '' Two vertices have the same vertex type if they have the same in- and out-neighborhoods. We show that Kidney Exchange is FPT parameterized by the number of vertex types. On the other hand, we show W[1]-hardness with respect to omega. We also design a randomized 4^t * n^O(1)-time algorithm parameterized by t, the number of patients helped, significantly improving upon the previous state of the art, which was 161^t * n^O(1).

PDF Details DOI

STOC Conference 2023 Conference Paper

An Improved Parameterized Algorithm for Treewidth

  • Tuukka Korhonen
  • Daniel Lokshtanov

We give an algorithm that takes as input an n -vertex graph G and an integer k , runs in time 2 O ( k 2 ) n O (1) , and outputs a tree decomposition of G of width at most k , if such a decomposition exists. This resolves the long-standing open problem of whether there is a 2 o ( k 3 ) n O (1) time algorithm for treewidth. In particular, our algorithm is the first improvement on the dependency on k in algorithms for treewidth since the 2 O ( k 3 ) n O (1) time algorithm given by Bodlaender and Kloks [ICALP 1991] and Lagergren and Arnborg [ICALP 1991]. We also give an algorithm that given an n -vertex graph G , an integer k , and a rational ε ∈ (0,1), in time k O ( k /ε) n O (1) either outputs a tree decomposition of G of width at most (1+ε) k or determines that the treewidth of G is larger than k . Prior to our work, no approximation algorithms for treewidth with approximation ratio less than 2, other than the exact algorithms, were known. Both of our algorithms work in polynomial space.

Details

SODA Conference 2023 Conference Paper

Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs

  • Peter Gartland
  • Daniel Lokshtanov

A vertex set S in a graph G is a minimal separator if there exist vertices u and v that are in distinct connected components of G — S, but in the same connected component of G — S ' for every S ' ⊂ S. A class F of graphs is called tame if there exists a constant c so that every graph in F on n vertices contains at most O(n c ) minimal separators. If there exists a constant c so that every graph in F on n vertices contains at most O(n c log n ) minimal separators the class is strongly-quasi-tame. If there exists a constant c > 1 so that F contains n -vertex graphs with at least c n minimal separators for arbitrarily large n then F is called feral. The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention. A key graph-theoretic object in the quest for such a classification is the notion of a k-creature. A k -creature consists of 4 disjoint vertex sets A, B, X = { x 1, …, x k }, Y = { y 1, … y k } such that: (a) A and B are connected, (b) there are no edges from A to Y ∪ B and no edges from B to X ∪ A, ( c ) A dominates X (every vertex in X has a neighbor in A ) and B dominates Y and ( d ) X i y i is an edge if and only if i = j. It is easy to verify that a k -creature contains at least 2 k minimal separators. On the other hand, in a recent article Abrishami et al. [1] conjecture that every hereditary class F that excludes k -creatures for some fixed constant k is tame. In this paper we first give a counterexample to the conjecture of Abrishami et al. Our main result is a proof of a weaker form of their conjecture. More concretely, we prove that a hereditary class F is strongly quasi-tame if it excludes k -creatures for some fixed constant k and additionally every minimal separator can be dominated by another fixed constant k ' number of vertices. The tools developed on the way lead to a number of additional results of independent interest. (i) We obtain a complete classification of all hereditary graph classes defined by a finite set of forbidden induced subgraphs into strongly quasi-tame or feral. This substantially generalizes a recent result of Milanic and Pivac [18], who classified all hereditary graph classes defined by a finite set of forbidden induced subgraphs on at most 4 vertices into tame or feral. (ii) We show that every hereditary class that excludes k -creatures and additionally excludes all cycles of length at least c, for some constant c, is tame. This generalizes the result of Chudnovsky et al. [6] who obtained the same statement for c =5. (iii) We show that every hereditary class that excludes k -creatures and additionally excludes a complete graph on c vertices for some fixed constant c is tame. * The full version of the paper can be accessed at https: //arxiv. org/abs/2007. 08761

Details

SODA Conference 2023 Conference Paper

Graph Classes with Few Minimal Separators. II. A Dichotomy

  • Peter Gartland
  • Daniel Lokshtanov

A class F of graphs is called tame if every graph in F on n vertices contains at most n O(1) minimal separators, quasi-tame if every graph in F on n vertices contains at most 2 log O (1) ( n ) minimal separators, and feral if there exists a constant c > 1 so that F contains n -vertex graphs with at least c n minimal separators for arbitrarily large n. The classification of graph classes into (quasi-) tame or feral has numerous algorithmic consequences, and has recently received considerable attention. In this paper we precisely characterize the structure of graphs which have few minimal separators. Specifically we show that every graph which excludes certain graphs called k-creatures and k-critters as induced subgraphs has at most quasi-polynomially many minimal separators. We then demonstrate that this sufficient condition for having few minimal separators is the “right” one. In particular we show that every hereditary graph class F definable in CMSO logic that contains k -creatures or k -critters for every k is feral.

Details

MFCS Conference 2023 Conference Paper

Parameterized Approximation Scheme for Feedback Vertex Set

  • Satyabrata Jana
  • Daniel Lokshtanov
  • Soumen Mandal 0001
  • Ashutosh Rai 0001
  • Saket Saurabh 0001

Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G-S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time 𝒪^*(3. 460^k) and 𝒪^*(2. 7^k) respectively. In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1+ε) approximation algorithms for FVS, running in times 𝒪^*(2^{εk}⋅ 2. 7^{(1-ε)k}), 𝒪^*(({(4/(1+ε))^{(1+ε)}}⋅{(ε/3)^ε})^k), and 𝒪^*(4^{(1-ε)k}) respectively for every ε ∈ (0, 1). Combining these three algorithms, we obtain a factor (1+ε) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ε ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS.

Details

SODA Conference 2023 Conference Paper

Shortest Cycles With Monotone Submodular Costs

  • Fedor V. Fomin
  • Petr A. Golovach
  • Tuukka Korhonen
  • Daniel Lokshtanov
  • Giannos Stamoulis

We introduce the following submodular generalization of the SHORTEST CYCLE problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost OPT = f(C). We give an algorithm that given an n -vertex graph G, parameter ε > 0, and the function f represented by an oracle, in time n 𝒪(log 1/ε) finds a cycle C in G with f ( C ) ≤ (1 + ε) · OPT. This is in sharp contrast with the non-approximability of the closely related MONOTONE SUBMODULAR SHORTEST ( s, t )-PATH problem, which requires exponentially many queries to the oracle for finding an n 2//3-ε -approximation [Goel et al. , FOCS 2009]. We complement our algorithm with a matching lower bound. We show that for every ε > 0, obtaining a (1 + ε)-approximation requires at least n Ω(log 1/ε) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost OPT can be found in time n 𝒪(log OPT). In particular, for OPT = n 𝒪(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n 𝒪(log n ) queries are required even when OPT = 𝒪(n).

Details

SODA Conference 2022 Conference Paper

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

  • Akanksha Agrawal 0001
  • Lawqueen Kanesh
  • Daniel Lokshtanov
  • Fahad Panolan
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001
  • Meirav Zehavi

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by mod ℋ ) of a modulator to a graph class ℋ, i. e. , a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by ed ℋ ) [Bulian and Dawar, Algorithmica, 2016] and ℋ -treewidth (denoted by tw ℋ ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the “torso” of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v ∊ S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of ed ℋ parameterized by tw ℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ed ℋ and tw ℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a “strong irrelevant vertex rule”, then there exists a uniform FPT algorithm for ed ℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing ed ℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.

Details

STOC Conference 2022 Conference Paper

Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor

  • Daniel Lokshtanov
  • Marcin Pilipczuk
  • Michal Pilipczuk
  • Saket Saurabh 0001

We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph H as a minor can be solved by an algorithm working in time f ( H )· n O (1) , where f is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given H -minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable H -minor-free graphs, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth.

Details

SODA Conference 2022 Conference Paper

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H<-Minor-Free Graphs

  • Sayan Bandyapadhyay
  • William Lochet
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Jie Xue 0003

We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on H -minor free graphs. In particular, we obtain the following results (where k is the solution-size parameter). time algorithms for E dge B ipartization and O dd C ycle T ransversal; a time algorithm for E dge M ultiway C ut and a time algorithm for V ertex M ultiway C ut (with undeletable terminals), where r is the number of terminals to be separated; a time algorithm for E dge M ulticut and a time algorithm for V ertex M ulticut (with undeletable terminals), where r is the number of terminal pairs to be separated; a time algorithm for G roup F eedback E dge S et and a time algorithm for G roup F eedback V ertex S et, where g is the size of the group. In addition, our approach also gives time algorithms for all above problems with the exception of time for E dge /V ertex M ulticut and time for G roup F eedback E dge /V ertex S et. All of our FPT algorithms (the first four items above) are randomized, as they use known randomized kernelization algorithms as sub-routines. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an h -almost-embeddable graph for an arbitrary but fixed constant h. Our new decomposition theorem generalizes known Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H -minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. In particular we show the following. Let G be a graph of bounded genus, or more generally, an h -almost-embeddable graph for an arbitrary but fixed constant h. Then for every p ∊ ℕ, there exist disjoint sets Z 1, …, Z p ⊆ V(G ) such that for every i ∊ {1, …, p } and every Z′ ⊆ Z i, the treewidth of G/(Z i \Z′ ) is upper bounded by O(p + | Z′| ), where the constant hidden in O (·) depends on h. Here G/(Z i \Z′ ) denotes the graph obtained from G by contracting every edge with both endpoints in Z i \Z′. When Z′ =, this corresponds to classical Contraction Decomposition Theorem.

Details

SODA Conference 2022 Conference Paper

Subexponential Parameterized Algorithms on Disk Graphs (Extended Abstract)

  • Daniel Lokshtanov
  • Fahad Panolan
  • Saket Saurabh 0001
  • Jie Xue 0003
  • Meirav Zehavi

One of the most celebrated results in Parameterized Complexity is the Bidimensionality theory of Demaine et al. [J. ACM, 2005], which has yielded, over the past two decades, numerous subexponential-time fixed-parameter tractable (FPT) algorithms for various problems on planar (and H -minor-free) graphs. At the heart of this theory is the proof of sublinear bounds in terms of solution size on the treewidth of a given graph. Inspired by this theory, in recent years, significant efforts have been devoted to design subexponential-time FPT algorithms for problems on geometric graph classes that utilize new treewidth bounds, in particular (but not only) for unit disk graphs [Fomin et al. , SODA'12; Fomin et al. , DCG'19; Panolan et al. , SODA'19; Fomin et al. SoCG'20]. In this paper, we aim to attain such results on disk graphs, a broad class of graphs that generalizes both the classes of planar graphs and unit disk graphs, and thereby unify the aforementioned research frontiers for planar and unit disk graphs. Our main contribution is an approach to design subexponential-time FPT algorithms for problems on disk graphs, which we apply to several well-studied graph problems. At the heart of our approach lie two new combinatorial theorems concerning the treewidth of disk graphs having a realization of bounded ply (or maximum clique size) that are of independent interest. In particular, we prove a stronger version of the following treewidth bound: Let G be a disk graph that has some realization of ply p and no false twins, and M ⊆ V(G ) such that G has no triangle with exactly one vertex from M, and G – M has treewidth w. Then, the treewidth of G is. Among our applications are the first subexponential-time FPT algorithms for several problems on disk graphs, including T riangle H itting, F eedback V ertex S et and O dd C ycle T ransversal (OCT). Previously, subexponential-time FPT algorithms for these problems were only known on planar graphs and unit disk graphs (excluding OCT, which was only known to admit such an algorithm on planar graphs). Our algorithms are robust, in particular, they do not require a geometric realization of the input graph (for all aforementioned problems), and they generalize to the weighted and counting versions of all aforementioned problems except for OCT.

Details

SODA Conference 2021 Conference Paper

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

  • Neeraj Kumar 0004
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Subhash Suri

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names M in -C olor P ath and M inimum L abel P ath ), wireless sensor networks (B arrier R esilience ) and motion planning (M inimum C onstraint R emoval ). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al. , CGTA, 2020]. We also obtain a constant factor approximation for the M inimum C olor P rize C ollecting S teiner F orest where the goal is to connect multiple request pairs ( s 1, t 1 ), …, ( s k, t k ) while minimizing the number of obstacles touched by any ( s i, t i ) path plus a fixed cost of w i for each pair ( s i, t i ) left disconnected. This generalizes the classic S teiner F orest and P rize -C ollecting S teiner F orest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for M in -C olor P ath even on planar graphs since the problem is known to be APX-hard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles in the plane or connected obstacles in higher dimensions are strongly inapproximable assuming some well-known hardness conjectures.

Details

IJCAI Conference 2021 Conference Paper

Diversity in Kemeny Rank Aggregation: A Parameterized Approach

  • Emmanuel Arrighi
  • Henning Fernau
  • Daniel Lokshtanov
  • Mateus de Oliveira Oliveira
  • Petra Wolf

In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that KRA is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.

PDF Details DOI

SODA Conference 2021 Conference Paper

Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version)

  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper we prove an analogue of the classic Bollobás lemma for approximate counting. In fact, we match an analogous result of Fomin et al. [JACM 2016] for decision. This immediately yields, for a number of fundamental problems, parameterized approximate counting algorithms with the same running times as what is obtained for the decision variant using the representative family technique of Fomin et al. [JACM 2016]. For example, we devise an algorithm for approximately counting (a factor (1 ± ∊ ) approximation algorithm) k -paths in an n -vertex directed graph (# k -Path) running in time ( n + m )). This improves over an earlier algorithm of Brand et al. [STOC 2018] that runs in time. Additionally, we obtain an approximate counting analogue of the efficient computation of representative families for product families of Fomin et al. [TALG 2017], again essentially matching the running time for decision. This results in an algorithm with running time for computing a (1 + ∊ ) approximation of the sum of the coefficients of the multilinear monomials in a degree- k homogeneous n -variate polynomial encoded by a monotone circuit (#M ultilinear M onomial D etection ). When restricted to monotone circuits (rather than polynomials of non-negative coefficients), this improves upon an earlier algorithm of Pratt [FOCS 2019] that runs in time.

Details

STOC Conference 2021 Conference Paper

Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time

  • Peter Gartland
  • Daniel Lokshtanov
  • Marcin Pilipczuk
  • Michal Pilipczuk
  • Pawel Rzazewski

For an integer t , a graph G is called C > t -free if G does not contain any induced cycle on more than t vertices. We prove the following statement: for every pair of integers d and t and a statement φ, there exists an algorithm that, given an n -vertex C > t -free graph G with weights on vertices, finds in time n (log 3 n ) a maximum-weight vertex subset S such that G [ S ] has degeneracy at most d and satisfies φ. The running time can be improved to n (log 2 n ) assuming G is P t -free, that is, G does not contain an induced path on t vertices. This expands the recent results of the authors [FOCS 2020 and SOSA 2021] on the Maximum Weight Independent Set problem on P t -free graphs in two directions: by encompassing the more general setting of C > t -free graphs, and by being applicable to a much wider variety of problems, such as Maximum Weight Induced Forest or Maximum Weight Induced Planar Graph.

Details

SODA Conference 2021 Conference Paper

FPT-approximation for FPT Problems

  • Daniel Lokshtanov
  • Pranabendu Misra
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001
  • Meirav Zehavi

Over the past decade, many results have focused on the design of parameterized approximation algorithms for W[1]-hard problems. However, there are fundamental problems within the class FPT for which the best known algorithms have seen no progress over the course of the decade; some of them have even been proved not to admit algorithms that run in time 2 ( k ) n (1) under the Exponential Time Hypothesis (ETH) or ( c – ∊ ) k n (1) under the Strong ETH (SETH). In this paper, we expand the study of FPT-approximation and initiate a systematic study of FPT-approximation for problems that are FPT. We design FPT-approximation algorithms for problems that are FPT, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time. We present a general scheme to design 2 ( k ) n (1) -time 2-approximation algorithms for cut problems. In particular, we exemplify it for D irected F eedback V ertex S et, D irected S ubset F eedback V ertex S et, D irected O dd C ycle T ransversal and U ndirected M ulticut. Further, we extend our scheme to obtain FPT-time (1)-approximation algorithms for weighted cut problems, where the objective is to obtain a solution of size at most k and of minimum weight. Here, we present two approaches. The first approach achieves 2 ( k ) n (1) -time constant-factor approximation, which we exemplify for all problems mentioned in the first bullet. The other leads to an FPT-approximation Scheme (FPT-AS) for W eighted D irected F eedback V ertex S et. Additionally, we present a combinatorial lemma that yields a partition of the vertex set of a graph to roughly equal sized sets so that the removal of each set reduces its treewidth substantially, which may be of independent interest. For several graph problems, use this lemma to design c w n (1) -time (1 + ∊ )-approximation algorithms that are faster than known SETH lower bounds, where w is the treewidth of the input graph. Examples of such problems include V ertex C over, C omponent O rder C onnectivity, B ounded -D egree V ertex D eletion and ℱ -P acking for any family ℱ of bounded sized graphs. Lastly, we present a general reduction of problems parameterized by treewidth to their versions parameterized by solution size. Combined with our first scheme, we exemplify it to obtain c w n (1) -time bicriteria approximation algorithms for all problems mentioned in the first bullet.

Details

SODA Conference 2020 Conference Paper

2-Approximating Feedback Vertex Set in Tournaments

  • Daniel Lokshtanov
  • Pranabendu Misra
  • Joydeep Mukherjee
  • Fahad Panolan
  • Geevarghese Philip
  • Saket Saurabh 0001

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T – S is acyclic. We consider the F eedback V ertex S et problem in tournaments. Here the input is a tournament T and a weight function w: V ( T ) → ℕ and the task is to find a feedback vertex set S in T minimizing w ( S ) = Σ v ϵ S w ( v ). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2. 5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this paper we give the first polynomial time factor 2 approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time.

Details

FOCS Conference 2020 Conference Paper

A Parameterized Approximation Scheme for Min $k$-Cut

  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Vaishali Surianarayanan

In the Min $k$ -cut problem, input is an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al. [SODA 2018] initiated the study of FPT-approximation for the Min $k$ -Cut problem and gave an 1. 9997-approximation algorithm running in time $2^{\mathcal{O}(k^{6})}n^{\mathcal{O}(1)}$. Later, the same set of authors [FOCS 2018] designed an ( $1+\epsilon$ )-approximation algorithm that runs in time $(k/\epsilon)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$, and a 1. 81-approximation algorithm running in time $2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin [SODA 2020] gave a $(5/3+\epsilon)$ -approximation for Min $k$ -Cut running in time $2^{\mathcal{O}(k^{2}\log k)}n^{\mathcal{O}(1)}$. In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every $\epsilon > 0$, the algorithm obtains a ( $1+\epsilon$ )-approximate solution in time $(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$ -cut. The latter two are of independent interest.

Details

STOC Conference 2020 Conference Paper

An exponential time parameterized algorithm for planar disjoint paths

  • Daniel Lokshtanov
  • Pranabendu Misra
  • Michal Pilipczuk
  • Saket Saurabh 0001
  • Meirav Zehavi

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, { s i , t i } i =1 k , and the task is to find k pairwise vertex-disjoint paths such that the i ’th path connects s i to t i . In this paper, we give a parameterized algorithm with running time 2 O ( k 2 ) n O (1) for Planar Disjoint Paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [JCTB 2017], the algebraic co-homology based technique developed by Schrijver [SICOMP 1994] for Disjoint Paths on directed planar graphs, and one of the key combinatorial insights developed by Cygan et al. [FOCS 2013] in their algorithm for Disjoint Paths on directed planar graphs. To the best of our knowledge our algorithm is the first parameterized algorithm to exploit that the treewidth of the input graph is small in a way completely different from the use of dynamic programming.

Details

SODA Conference 2020 Conference Paper

Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper, we prove a new scaling lemma for vertex weighted minor free graphs that allows for a smooth trade-off between the weight of a vertex set S and the treewidth of G — S. More precisely, we show the following. There exists an algorithm that given an H- minor free graph G, a weight function w: V ( G ) → ℚ + and integers t and s, runs in polynomial time, and outputs a subset S ⊆ V ( G ) of weight at most d log n · opt( G, w, t )/s such that the treewidth of G – S is at most c·st. Here, d and c are fixed constants that depend only on H, and opt( G, w, t ) is the (unknown) minimum weight of a subset U ⊆ V ( G ) such that the treewidth of G – U is at most t. This lemma immediately yields the first polynomial-time approximation schemes (PTASes) for WEIGHTED T reewidth - η V ertex D eletion, for η > 2, on graphs of bounded genus and the first PTAS for W eighted F eedback vertex S et on H -minor free graphs. These results effortlessly generalize to include weighted edge deletion problems, to all W eighted C onnected P lanar -D eletion problems, and finally to quasi polynomial time approximation schemes (QPTASes) for all of these problems on H -minor free graphs. For most of these problems even constant factor approximation algorithms, even on planar graphs, were not previously known. Additionally, using the scaling lemma we subsume, simplify and extend the recent framework of Cohen-Addad et al. [STOC 2016] for turning constant factor approximation algorithms for “ubiquitous” problems into PTASes for the same problems on graphs of bounded genus. Specifically, we obtain PTASes for ubiquitous problems without the requirement of having a constant factor approximation. While the statement of the scaling lemma is inspired by an analogous lemma by Cohen-Addad et al. [STOC 2016] for edge contractions on weighted graphs of bounded genus, as well as a scaling lemma by Fomin et al. [SODA 2011] for unweighted graphs, the proof is entirely different. The proof detours via three different linear programming relaxations for the W eighted T reewidth - η V ertex D eletion problems and a strengthening of a recent rounding procedure of Bansal et al. [SODA 2017] enhanced by the classic Klein-Plotkin-Rao Theorem [STOC 1993].

Details

STOC Conference 2020 Conference Paper

Hitting topological minors is FPT

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Fahad Panolan
  • Saket Saurabh 0001
  • Meirav Zehavi

In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G , a family of undirected graphs F and an integer k . The task is to determine whether G contains a set of vertices S of size at most k , such that the graph G ∖ S obtained from G by removing the vertices of S , contains no graph from F as a topological minor. We give an algorithm forTM-Deletion with running time f ( h ⋆ , k )· | V ( G )| 4 . Here h ⋆ is the maximum size of a graph in F and f is a computable function of h ⋆ and k . This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on k and h ⋆ .

Details

FOCS Conference 2020 Conference Paper

Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time

  • Peter Gartland
  • Daniel Lokshtanov

We present an algorithm that takes as input a graph G with weights on the vertices, and computes a maximum weight independent set S of G. If the input graph G excludes a path P k on k vertices as an induced subgraph, the algorithm runs in time n O(k2 log 3 n). Hence, for every fixed k our algorithm runs in quasi-polynomial time. This resolves in the affirmative an open problem of [Thomassé, SODA'20 invited presentation]. Previous to this work, polynomial time algorithms were only known for P 4 -free graphs [Corneil et al. , DAM'81], P 5 -free graphs [Lokshtanov et al. , SODA'14], and P 6 -free graphs [Grzesik et al. , SODA'19]. For larger values of t, only 2 O(√{knlogn}) time algorithms [Bacsó et al. , Algorithmica'19] and quasipolynomial time approximation schemes [Chudnovsky et al. , SODA'20] were known. Thus, our work is the first to offer conclusive evidence that Independent Set on P k - free graphs is not NP-complete for any integer k. Additionally we show that for every graph H, if there exists a quasi-polynomial time algorithm for Independent Seton C-free graphs for every connected component C of H, then there also exists a quasi-polynomial time algorithm for Independent Set on H-free graphs. This lifts our quasi-polynomial time algorithm to T k -free graphs, where T k has one component that is a P k, and k-1 components isomorphic to a fork (the unique 5-vertex tree with a degree 3 vertex).

Details

SODA Conference 2020 Conference Paper

Parameterized Complexity and Approximability of Directed Odd Cycle Transversal

  • Daniel Lokshtanov
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001
  • Meirav Zehavi

A directed odd cycle transversal of a directed graph (digraph) D is a vertex set S that intersects every odd directed cycle of D. In the D irected O dd C ycle T ransversal (DOCT) problem, the input consists of a digraph D and an integer k. The objective is to determine whether there exists a directed odd cycle transversal of D of size at most k. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size k by showing that DOCT does not admit an algorithm with running time unless FPT = W[1]. On the positive side, we give a factor 2 fixed-parameter approximation (FPT approximation) algorithm for the problem. More precisely, our algorithm takes as input D and k, runs in time, and either concludes that D does not have a directed odd cycle transversal of size at most k, or produces a solution of size at most 2k. Finally, assuming gap-ETH, we show that there exists an ϵ > 0 such that DOCT does not admit a factor (1 + ϵ ) FPT-approximation algorithm.

Details

MFCS Conference 2019 Conference Paper

Picking Random Vertices (Invited Talk)

  • Daniel Lokshtanov

We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set. We will also discuss a recent 2-approximation algorithm for Feedback Vertex Set in Tournaments that is based on picking a vertex at random and declaring it to not be part of the solution.

Details

SODA Conference 2018 Conference Paper

Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth

  • Petr A. Golovach
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Meirav Zehavi

M ax -C ut (MC), E dge D ominating S et (EDS), G raph C oloring (GC) and H amiltonian P ath (HP) on graphs of bounded cliquewidth have received significant attention as they can be formulated in MSO 2 (and therefore have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle's theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded cliquewidth graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of cliquewidth k. Fomin et al. [ Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941–1956 (2010) ] showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out nontrivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. [ Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput. 43(5): 1541–1563 (2014) ] improved the running times for EDS and MC to n O ( k ), and proved g ( k ) n o ( k ) lower bounds for EDS, MC and HP assuming the ETH. Recently, Bergougnoux, Kante and Kwon [ WADS 2017 ] gave an n O ( k ) -time algorithm for HP. Thus, prior to this work, EDS, MC and HP were known to have tight n Θ( k ) algorithmic upper and lower bounds. In contrast, GC has an upper bound of n O (2 k ) and a lower bound of merely (implicit from the W[1]-hardness proof). In this paper, we close the gap for GC by proving a lower bound of n 2 o ( k ) This shows that GC behaves qualitatively different from the other three problems. To the best of our knowledge, GC is the first natural problem known to require exponential dependence on the parameter in the exponent of n.

Details

MFCS Conference 2018 Conference Paper

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy

  • Akanksha Agrawal 0001
  • Pallavi Jain 0001
  • Lawqueen Kanesh
  • Daniel Lokshtanov
  • Saket Saurabh 0001

In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H in F (where V(G)=V(H)), and an integer k, and the objective is to decide if there is a set S subseteq V(G) of size at most k such that G-S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G in F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of K_{i, j}-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0< epsilon<1, the family of graphs F_epsilon, which comprise of graphs G such that |E(G)| <= |V(G)|^(2-epsilon), and show that F_epsilon-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0<epsilon<1.

Details

SODA Conference 2018 Conference Paper

When Recursion is Better than Iteration: A Linear-Time Algorithm for Acyclicity with Few Error Vertices

  • Daniel Lokshtanov
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001

Planarity, bipartiteness and (directed) acyclicity are basic graph properties with classic linear time recognition algorithms. However, the problems of testing whether a given (di)graph has k vertices whose deletion makes it planar, bipartite or a directed acyclic graph (DAG) are all fundamental NP-complete problems when k is part of the input. As a result, a significant amount of research has been devoted to understanding whether, for every fixed k, these problems admit a polynomial time algorithm (where the exponent in the polynomial is independent of k ) and in particular, whether they admit linear time algorithms. While we now know that for any fixed k, we can test in linear time whether a graph is k vertices away from being planar [FOCS 2009, SODA 2014] or bipartite [SODA 2014, SICOMP 2016], the best known algorithms in the case of directed acyclicity are the algorithm of Garey and Tarjan [IPL 78] which runs in time O ( n k–1 m ) and the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008] which runs in time O ( k! 4 k k 4 nm ). In other words, it has remained open whether it is possible to recognize in linear time, a graph which is 2 vertices away from being acyclic! In this paper, we settle this question by giving an algorithm that decides whether a given graph is k vertices away from being acyclic, in time O ( k! 4 k k 5 ( n + m )). That is, for every fixed k, our algorithm runs in time O ( m + n), thus mirroring the case for planarity and bipartiteness. Our algorithm is designed via a general methodology that shaves off a factor of n from some algorithms that use the powerful technique of iterative compression. The two main features of our methodology are: (i) This is the first generic technique for designing linear time algorithms for directed cut-problems and (ii) it can be used in combination with future improvements in algorithms for the compression version of other well-studied cut-problems such as M ulticut and D irected S ubset F eedback V ertex S et.

Details

SODA Conference 2017 Conference Paper

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

  • Daniel Lokshtanov
  • Ramamohan Paturi
  • Suguru Tamaki
  • R. Ryan Williams
  • Huacheng Yu

We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≤ 2 and finite field q where q = p d for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O ( q n ) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time q n + o ( n ) · q − n / O ( k ) time if q < 2 4 ekd, and otherwise, where e = 2. 718… is Napier's constant, and a deterministic algorithm for counting solutions with running time q n + o ( n ) · q − n / O ( kq 6/7 d ). For the important special case of quadratic equations in F 2, our randomized algorithm has running time O (2 0. 8765n ). For systems over 2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a ΣΠΣ circuit, i. e. , a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2 n-dn for δ = 1/ O (log(s/ n )) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of ΣΠΣ polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O (log(s/ n )).

Details

SODA Conference 2017 Conference Paper

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

  • Akanksha Agrawal 0001
  • Daniel Lokshtanov
  • Pranabendu Misra
  • Saket Saurabh 0001
  • Meirav Zehavi

Given a graph G and a parameter k, the C hordal V ertex D eletion (CVD) problem asks whether there exists a subset U ⊆ V ( G ) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O ( k 161 log 58 k ), and asked whether one can design a kernel of size O ( k 10 ). While we do not completely resolve this question, we design a significantly smaller kernel of size O ( k 25 log 14 k ), inspired by the O ( k 2 )-size kernel for F eedback V ertex S et. To obtain this result, we first design an O (opt-log 2 n )-factor approximation algorithm for CVD, which is central to our kernelization procedure. Thus, we improve upon both the kernelization algorithm and the approximation algorithm of Jansen and Pilipczuk. Next, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution. We believe that this notion could be useful in designing kernels for other problems.

Details

SODA Conference 2017 Conference Paper

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Michal Pilipczuk
  • Saket Saurabh 0001
  • Marcin Wrochna

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial, but far from linear, time. Thus, our goal is to construct algorithms with running time of the form poly( k ) · n or poly( k ) · n log n, where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O ( n 1/c ) for some small constant c. Our results include:  an algorithm for computing the determinant and the rank of an n × n matrix using O ( k 3 · n ) time and arithmetic operations;  an algorithm for solving a system of linear equations using O ( k 3 · n ) time and arithmetic operations;  an O ( k 3 · n log n )-time randomized algorithm for finding the cardinality of a maximum matching in a graph;  an O ( k 4 · nlog 2 n )-time randomized algorithm for constructing a maximum matching in a graph;  an O ( k 2 · n log n )-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we provide an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k, runs in time O ( k 2 · n log n ) and either correctly reports that the treewidth of G is larger than k, or constructs a tree decomposition of G of width O ( k 2 ). The above results stand in contrast with the recent work of Abboud et al. [SODA 2016], which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

Details

STOC Conference 2017 Conference Paper

Lossy kernelization

  • Daniel Lokshtanov
  • Fahad Panolan
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001

In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions com- bine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel. Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance ( I , k ) to a parameterized problem, and outputs another instance ( I ′, k ′) to the same problem, such that | I ′| + k ′ ≤ k O (1) . Additionally, for every c ≥ 1, a c -approximate solution s ′ to the pre-processed instance ( I ′, k ′) can be turned in polynomial time into a ( c · α)-approximate solution s to the original instance ( I , k ). Amongst our main technical contributions are α-approximate kernels of polynomial size for three problems, namely Connected Vertex Cover, Disjoint Cycle Packing and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP ⊆ coNP / Poly . Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size, and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an α-approximate kernel of polynomial size, for any α≥1, unless NP ⊆ coNP / Poly . In order to prove this lower bound we need to combine in a non-trivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.

Details

SODA Conference 2017 Conference Paper

Spanning Circuits in Regular Matroids

  • Fedor V. Fomin
  • Petr A. Golovach
  • Daniel Lokshtanov
  • Saket Saurabh 0001

We consider the fundamental Matroid Theory problem of finding a circuit in a matroid spanning a set t of given terminal elements. For graphic matroids this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gavenčiak, Král', and Oum [ICALP'12], who proved that the case of the problem with | T | = 2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gavenciak, Král', and Oum by showing that for regular matroids • the M inimum S panning C ircuit problem, deciding whether there is a circuit with at most ℓ elements containing T, is FPT parameterized by k = ℓ — | T |; • the S panning C ircuit problem, deciding whether there is a circuit containing T, is FPT parameterized by | T |. We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely: M inimum Spanning Circuit parameterized by ℓ is W[1]- hard on binary matroids even when | T | = 1. We also show a limit to how far our results can be strengthened by considering a smaller parameter. More precisely, we prove that M inimum S panning C ircuit parameterized by | T | is W[1]-hard even on cographic matroids, a proper subclass of regular matroids.

Details

Highlights Conference 2016 Conference Abstract

A New Perspective on FO Model Checking of Dense Graph Classes

  • Joint work with Jakub Gajarsky
  • Petr Hlineny
  • Daniel Lokshtanov
  • M. S. Ramanujan.

We study the FO model checking problem of dense graph classes, namely those which are FO-interpretable in some sparse graph class. Note that if an input dense graph is given together with the corresponding FO interpretation in a sparse graph, one can easily solve the model checking problem using the existing algorithms for sparse graph classes. However, if the assumed interpretation is not given, then the situation is markedly harder. In this talk I will give a structural characterization of graph classes which are FO interpretable in graph classes of bounded degree. This characterization allows us to efficiently compute such an interpretation for an input graph. As a consequence, we obtain an FPT algorithm for FO model checking of graph classes FO interpretable in graph classes of bounded degree. The approach used to obtain these results may also be of independent interest. Based on a paper accepted to LICS 2016.

Details

STOC Conference 2016 Conference Paper

Exact algorithms via monotone local search

  • Fedor V. Fomin
  • Serge Gaspers
  • Daniel Lokshtanov
  • Saket Saurabh 0001

We give a new general approach for designing exact exponential-time algorithms for subset problems . In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d -SAT. Here, the input is a CNF-formula with clauses of size at most d , and an integer W . The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W , and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on “monotone local search”, where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem we are also given as input a subset X of the universe and an integer k . The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c k n O (1) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O ((2−1/ c ) n ).

Details

SODA Conference 2016 Conference Paper

Independence and Efficient Domination on P 6 -free Graphs

  • Daniel Lokshtanov
  • Marcin Pilipczuk
  • Erik Jan van Leeuwen

In the M aximum W eight I ndependent S et problem, the input is a graph G, every vertex has a nonnegative integer weight, and the task is to find a set S of pairwise non-adjacent vertices, maximizing the total weight of the vertices in S. We give an time algorithm for this problem on graphs excluding the path P 6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which M aximum W eight I ndependent S et on P k -free graphs becomes NP-complete, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in (quasi)polynomial time. Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for M aximum W eight E fficient D ominating S et on P 6 -free graphs. In this problem, the input is a graph G, every vertex has an integer weight, and the objective is to find a set S of maximum weight such that every vertex in G has exactly one vertex in S in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of P 6 -free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of M aximum W eight E fficient D ominating S et was unknown.

Details

FOCS Conference 2016 Conference Paper

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Dániel Marx
  • Marcin Pilipczuk
  • Michal Pilipczuk
  • Saket Saurabh 0001

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: 1) A induces a subgraph of G of treewidth O(√(k log k)), and 2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2 O(√k log2 k) · n O(1))-1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2 O (√(k log 2 k))n O(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include DIRECTED k-Path, WEIGHTED k-Path, VERTEX COVER LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

Details

FOCS Conference 2015 Conference Paper

FO Model Checking on Posets of Bounded Width

  • Jakub Gajarský
  • Petr Hlinený
  • Daniel Lokshtanov
  • Jan Obdrzálek
  • Sebastian Ordyniak
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula φ, and determines whether φ holds on P in time f(φ, w) · n 2.

Details

SODA Conference 2015 Conference Paper

Solving d- SAT via Backdoors to Small Treewidth

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Neeldhara Misra
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001

A backdoor set of a CNF formula is a set of variables such that fixing the truth values of the variables from this set moves the formula into a polynomial-time de-cidable class. In this work we obtain several algorithmic results for solving d -SAT, by exploiting backdoors to d -CNF formulas whose incidence graphs have small treewidth. For a CNF formula ϕ and integer t, a strong backdoor set to treewidth t is a set of variables such that each possible partial assignment τ to this set reduces ϕ to a formula whose incidence graph is of treewidth at most t. A weak backdoor set to treewidth t is a set of variables such that there is a partial assignment to this set that reduces ϕ to a satisfiable formula of treewidth at most t. Our main contribution is an algorithm that, given a d -CNF formula ϕ and an integer k, in time, either finds a satisfying assignment of ϕ, or reports correctly that ϕ is not satisfiable, or concludes correctly that ϕ has no weak or strong backdoor set to treewidth t of size at most k. As a consequence of the above, we show that d -SAT parameterized by the size of a smallest weak/strong backdoor set to formulas of treewidth t, is fixed-parameter tractable. Prior to our work, such results were know only for the very special case of t = 1 (Gaspers and Szeider, ICALP 2012). Our result not only extends the previous work, it also improves the running time substantially. The running time of our algorithm is linear in the input size for every fixed k. Moreover, the exponential dependence on the parameter k is asymptotically optimal under Exponential Time Hypothesis (ETH). One of our main technical contributions is a linear time “protrusion replacer” improving over a (n log 2 n )-time procedure of Fomin et al. (FOCS 2012). The new deterministic linear time protrusion replacer has several applications in kernelization and parameterized algorithms.

Details

SODA Conference 2014 Conference Paper

A Near-Optimal Planarization Algorithm

  • Bart M. P. Jansen
  • Daniel Lokshtanov
  • Saket Saurabh 0001

The problem of testing whether a graph is planar has been studied for over half a century, and is known to be solvable in ( n ) time using a myriad of different approaches and techniques. Robertson and Seymour established the existence of a cubic algorithm for the more general problem of deciding whether an n -vertex graph can be made planar by at most k vertex deletions, for every fixed k. Of the known algorithms for k -V ertex P lanarization, the algorithm of Marx and Schlotter (WG 2007, Algorithmica 2012) running in time achieves the best running time dependence on k. The algorithm of Kawarabayashi (FOCS 2009), running in time f ( k ) n for some f ( k ) ∊ that is not stated explicitly, achieves the best dependence on n. In this paper we present an algorithm for k -Vertex Planarization with running time 2 ( k log k ) · n, significantly improving the running time dependence on k without compromising the linear dependence on n. Our main technical contribution is a novel scheme to reduce the treewidth of the input graph to ( k ) in time 2 O ( k log k ) · n. It combines new insights into the structure of graphs that become planar after contracting a matching, with a Baker-type subroutine that reduces the number of disjoint paths through planar parts of the graph that are not affected by the sought solution. To solve the reduced instances we formulate a dynamic programming algorithm for W eighted V ertex P lanarization on graphs of treewidth w with running time 2 ( w log w ) · n, thereby improving over previous double-exponential algorithms. While Kawarabayashi's planarization algorithm relies heavily on deep results from the graph minors project, our techniques are elementary and practically self-contained. We expect them to be applicable to related edge-deletion and contraction variants of planarization problems.

Details

SODA Conference 2014 Conference Paper

Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh 0001

Let M = ( E, I ) be a matroid and let S = { S 1, …, S t } be a family of subsets of E of size p. A subfamily Ŝ ⊆ S is q-representative for S if for every set Y ⊆ E of size at most q, if there is a set X ∊ S disjoint from Y with X ∪ Y ∊ I, then there is a set ∊ Ŝ disjoint from Y with ∪ Y ∊ I. By the classical result of Bollobás, in a uniform matroid, every family of sets of size p has a q -representative family with at most sets. In his famous “two families theorem” from 1977, Lovász proved that the same bound also holds for any matroid representable over a field. As observed by Marx, Lovász's proof is constructive. In this paper we show how Lovász's proof can be turned into an algorithm constructing a q -representative family of size at most in time bounded by a polynomial in, t, and the time required for field operations. We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following. In the L ong D irected C ycle problem the input is a directed n -vertex graph G and the positive integer k. The task is to find a directed cycle of length at least k in G, if such a cycle exists. As a consequence of our time algorithm, we have that a directed cycle of length at least log n, if such cycle exists, can be found in polynomial time. As it was shown by Björklund, Husfeldt, and Khanna [ICALP 2004], under an appropriate complexity assumption, it is impossible to improve this guarantee by more than a constant factor. Thus our algorithm not only improves over the best previous log n /log log n bound of Gabow and Nie SODA 2004] but also closes the gap between known lower and upper bounds for this problem. In the M inimum E quivalent G raph (MEG) problem we are seeking a spanning subdigraph D′ of a given n -vertex digraph D with as few arcs as possible in which the reachability relation is the same as in the original digraph D. The existence of a single-exponential c n -time algorithm for some constant c > 1 for MEG was open since the work of Moyles and Thompson [JACM 1969]. To demonstrate the diversity of applications of the approach, we provide an alternative proof of the results recently obtained by Bodlaender, Cygan, Kratsch and Nederlof for algorithms on graphs of bounded treewidth, who showed that many “connectivity” problems such as H amiltonian C ycle or S teiner T ree can be solved in time 2 ( t ) n on n -vertex graphs of treewidth at most t. We believe that expressing graph problems in “matroid language” shed light on what makes it possible to solve connectivity problems single-exponential time parameterized by treewidth. For the special case of uniform matroids on n elements, we give a faster algorithm computing a representative family in time. We use this algorithm to provide the fastest known deterministic parameterized algorithms for k -P ath, k -T ree, and more generally, for k -S ubgraph I somorphism, where the k -vertex pattern graph is of constant treewidth. For example, our k -P ath algorithm runs in time on weighted graphs with maximum edge weight W.

Details

FOCS Conference 2014 Conference Paper

Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

  • Daniel Lokshtanov
  • Marcin Pilipczuk
  • Michal Pilipczuk
  • Saket Saurabh 0001

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G 1, G 2, either concludes that one of these graphs has treewidth at least k, or determines whether G 1 and G 2 are isomorphic. The running time of the algorithm on an n-vertex graph is 2 O(k5 log k) · n 5, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2 OO(k5 log k) · n 5 time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k 4 ). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G 1 and G 2 are equal.

Details

SODA Conference 2014 Conference Paper

Independent Set in P 5 -Free Graphs in Polynomial Time

  • Daniel Lokshtanov
  • Martin Vatshelle
  • Yngve Villanger

The I ndependent S et problem is NP-hard in general, however polynomial time algorithms exist for the problem on various specific graph classes. Over the last couple of decades there has been a long sequence of papers exploring the boundary between the NP-hard and polynomial time solvable cases. In particular the complexity of I ndependent S et on P 5 -free graphs has received significant attention, and there has been a long list of results showing that the problem becomes polynomial time solvable on sub-classes of P 5 -free graphs. In this paper we give the first polynomial time algorithm for I ndependent S et on P 5 -free graphs. Our algorithm also works for the W eighted I ndependent S et problem.

Details

FOCS Conference 2013 Conference Paper

An O(c^k n) 5-Approximation Algorithm for Treewidth

  • Hans L. Bodlaender
  • Pål Grønås Drange
  • Markus S. Dregi
  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Michal Pilipczuk

We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(c k n) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for tree width which runs in time single-exponential in k and linear in n. Tree width based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the tree width and linear in the input size.

Details

I&C Journal 2013 Journal Article

Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs

  • Frederic Dorn
  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Venkatesh Raman
  • Saket Saurabh

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, k-Leaf Out-Branching, which is to find an oriented spanning tree with at least k leaves, we obtain an algorithm solving the problem in time 2 O ( k log k ) n + n O ( 1 ) on directed graphs whose underlying undirected graph excludes some fixed graph H as a minor. For the special case when the input directed graph is planar, the running time can be improved to 2 O ( k ) n + n O ( 1 ). The second example is a generalization of the Directed Hamiltonian Path problem, namely k-Internal Out-Branching, which is to find an oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the problem in time 2 O ( k log k ) + n O ( 1 ) on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that on these classes of graphs, the k-Directed Path problem is solvable in time O ( ( 1 + ε ) k n f ( ε ) ), for any ε > 0, where f is some function of ε. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem-specific combinatorial structures, and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

Details DOI

I&C Journal 2013 Journal Article

Clustering with local restrictions

  • Daniel Lokshtanov
  • Dániel Marx

We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement. Formally, let μ be a function on the subsets of vertices of a graph G. In the ( μ, 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) μ ( C ) ⩽ p. Our first result shows that if μ is an arbitrary polynomial-time computable monotone function, then ( μ, p, q ) -Partition can be solved in time n O ( q ), i. e. , it is polynomial-time solvable for every fixed q. We study in detail three concrete functions μ (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 ( μ, p, q ) -Partition can be solved in time 2 O ( p ) ⋅ n O ( 1 ) and in time 2 O ( q ) ⋅ n O ( 1 ) on n-vertex graphs, i. e. , the problem is fixed-parameter tractable parameterized by p or by q.

Details DOI

I&C Journal 2013 Journal Article

Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization

  • Pinar Heggernes
  • Dieter Kratsch
  • Daniel Lokshtanov
  • Venkatesh Raman
  • Saket Saurabh

Given a permutation π of { 1, …, n } and a positive integer k, can π be partitioned into at most k subsequences, each of which is either increasing or decreasing? We give an algorithm with running time 2 O ( k 2 log k ) n O ( 1 ) that solves this problem, thereby showing that it is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number of a given permutation graph on n vertices is at most k. Our algorithm solves in fact a more general problem: within the mentioned running time, it decides whether the cochromatic number of a given perfect graph on n vertices is at most k. To obtain our result we use a combination of two well-known techniques within parameterized algorithms: iterative compression and greedy localization. Consequently we name this combination “iterative localization”. We further demonstrate the power of this combination by giving an algorithm with running time 2 O ( k 2 log k ) n log n that decides whether a given set of n non-overlapping axis-parallel rectangles can be stabbed by at most k of a given set of horizontal and vertical lines.

Details DOI

ICML Conference 2013 Conference Paper

Near-Optimal Bounds for Cross-Validation via Loss Stability

  • Ravi Kumar 0001
  • Daniel Lokshtanov
  • Sergei Vassilvitskii
  • Andrea Vattani

Multi-fold cross-validation is an established practice to estimate the error rate of a learning algorithm. Quantifying the variance reduction gains due to cross-validation has been challenging due to the inherent correlations introduced by the folds. In this work we introduce a new and weak measure of stability called \emphloss stability and relate the cross-validation performance to loss stability; we also establish that this relationship is near-optimal. Our work thus quantitatively improves the current best bounds on cross-validation.

Details

SODA Conference 2012 Conference Paper

Bidimensionality and geometric graphs

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh 0001

Bidimensionality theory was introduced by Demaine et al. [ JACM 2005 ] as a framework to obtain algorithmic results for hard problems on minor closed graph classes. The theory has been successfully applied to yield subexponential time parameterized algorithms, EPTASs and linear kernels for many problems on families of graphs excluding a fixed graph H as a minor. In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on classes of graphs which are not minor closed, but instead exhibit a geometric structure. In particular we present EPTASs and subexponential time parameterized algorithms for F eedback V ertex S et, V ertex C over, C onnected V ertex C over, on map graphs and unit disk graphs, PTASs for D iamond H itting S et on map graphs and unit disk graphs, and a PTAS and a subexponential time algorithm for C ycle P acking on unit disk graphs. To the best of our knowledge, these results were previously unknown, with the exception of the EPTAS and a subexponential time parameterized algorithm on unit disk graphs for V ertex C over, which were obtained by Marx [ ESA 2005 ] and Alber and Fiala [ J. Algorithms 2004 ], respectively. Our results are based on the recent decomposition theorems proved by Fomin et al. in [ SODA 2011 ] and novel grid-excluding theorems in unit disk and map graphs without large cliques. Our algorithms work directly on the input graph and do not require the geometric representations of the input graph. We also show that our approach can not be extended in its full generality to more general classes of geometric graphs, such as intersection graphs of unit balls in ℝ d, d ≥ 3. Specifically, we prove that F eedback V ertex S et on unit-ball graphs in ℝ 3 neither admits PTASs unless P=NP, nor subexponential time algorithms unless the Exponential Time Hypothesis fails. Additionally, we show that the decomposition theorems which our approach is based on, fail for disk graphs and that therefore any extension of our results to disk graphs would require new algorithmic ideas. On the other hand, we prove that our EPTASs and subexponential time algorithms for V ertex C over and C onnected V ertex C over carry over both to disk graphs and to unit-ball graphs in ℝ d for every fixed d.

Details

SODA Conference 2012 Conference Paper

Linear kernels for (connected) dominating set on H -minor-free graphs

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Dimitrios M. Thilikos

We give the first linear kernels for D ominating S et and C onnected D ominating S et problems on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time algorithms that, for a given H -minor free graph G and positive integer k, output an H -minor free graph G′ on O ( k ) vertices such that G has a (connected) dominating set of size k if and only if G′ has. Prior to our work, the only polynomial kernel for Dominating Set on graphs excluding a fixed graph H as a minor was due to Alon and Gutner [ECCC 2008, IWPEC 2009] and to Philip, Raman, and Sikdar [ESA 2009] but the size of their kernel is k c ( H ), where c ( H ) is a constant depending on the size of H. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for D ominating S et on H -minor free graphs. We answer this question in affirmative. For C onnected D ominating S et no polynomial kernel on H -minor free graphs was known prior to our work. Our results are based on a novel generic reduction rule producing an equivalent instance of the problem with treewidth O (√ k ). The application of this rule in a divide-and-conquer fashion together with protrusion techniques brings us to linear kernels. As a byproduct of our results we obtain the first subexponential time algorithms for C onnected D ominating S et, a deterministic algorithm solving the problem on an n -vertex H -minor free graph in time 2 O (√ k log k ) + n O (1) and a Monte Carlo algorithm of running time 2 O (√ k ) + n O (1). For D ominating S et our results implies a significant simplification and refinement of a 2 O (√ k ) n O (1) algorithm on H minor free graphs due to Demaine et al. [SODA 2003, J. ACM 2005].

Details

FOCS Conference 2012 Conference Paper

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Neeldhara Misra
  • Saket Saurabh 0001

Let F be a finite set of graphs. In the F-DELETION problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k vertices can be deleted from G such that the resulting graph does not contain a graph from F as a minor. F-DELETION is a generic problem and by selecting different sets of forbidden minors F, one can obtain various fundamental problems such as VERTEX COVER, FEEDBACK VERTEX SET or TREEWIDTH η-DELETION. In this paper we obtain a number of generic algorithmic results about F-DELETION, when F contains at least one planar graph. The highlights of our work are · A constant factor approximation algorithm for the optimization version of F-DELETION; · A linear time and single exponential parameterized algorithm, that is, an algorithm running in time O(2 O(k) n), for the parameterized version of F-DELETION where all graphs in F are connected; · A polynomial kernel for parameterized F-DELETION. These algorithms unify, generalize, and improve a multitude of results in the literature. Our main results have several direct applications, but also the methods we develop on the way have applicability beyond the scope of this paper. Our results - constant factor approximation, polynomial kernelization and FPT algorithms - are stringed together by a common theme of polynomial time preprocessing.

Details

TCS Journal 2011 Journal Article

A Linear Kernel for Planar Connected Dominating Set

  • Daniel Lokshtanov
  • Matthias Mnich
  • Saket Saurabh

We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

Details DOI

TCS Journal 2011 Journal Article

An exact algorithm for minimum distortion embedding

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5 n + o ( n ). This is the first algorithm breaking the trivial n! -barrier.

Details DOI

TCS Journal 2011 Journal Article

Bandwidth on AT-free graphs

  • Petr Golovach
  • Pinar Heggernes
  • Dieter Kratsch
  • Daniel Lokshtanov
  • Daniel Meister
  • Saket Saurabh

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G = ( V, E ) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β: { 1, …, ∣ V ∣ } → V such that for every edge u v ∈ E, ∣ β − 1 ( u ) − β − 1 ( v ) ∣ ≤ k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f ( k ) n O ( 1 ) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n ⋅ 2 O ( k log k ) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP -complete.

Details DOI

TCS Journal 2011 Journal Article

Guard games on graphs: Keep the intruder out!

  • Fedor V. Fomin
  • Petr A. Golovach
  • Daniel Lokshtanov

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the guards and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges. The area protected by the guards is an induced subgraph of the given graph. We investigate the algorithmic aspects of the guarding problem, which is to find the minimum number of guards sufficient to patrol the area. We show that the guarding problem is PSPACE-hard and provide a set of approximation algorithms. All approximation algorithms are based on the study of a variant of the game where the intruder must reach the guarded area in a single step in order to win. This variant of the game appears to be a 2-approximation for the guarding problem, and for graphs without cycles of length 5 the minimum number of required guards in both games coincides. We give a polynomial time algorithm for solving the one-step guarding problem in graphs of bounded treewidth, and complement this result by showing that the problem is W [ 1 ] -hard parameterized by the treewidth of the input graph. We also show that the problem is fixed parameter tractable (FPT) parameterized by the treewidth and maximum degree of the input graph. Finally, we turn our attention to a large class of sparse graphs, including planar graphs and graphs of bounded genus, namely apex-minor-free graphs. We prove that the one-step guarding problem is FPT and possess a PTAS on apex-minor-free graphs.

Details DOI

SODA Conference 2011 Conference Paper

Known Algorithms on Graphs on Bounded Treewidth are Probably Optimal

  • Daniel Lokshtanov
  • Dániel Marx
  • Saket Saurabh 0001

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2 − ε) n m O (1) time, we show that for any ε > 0; I ndependent S et cannot be solved in time (2 − ε) tw( G ) | V ( G )| O (1), D ominating S et cannot be solved in time (3 − ε) tw( G ) | V ( G )| O (1), M ax C ut cannot be solved in time (2 − ε) tw( G ) | V ( G )| O (1), O dd C ycle T ranversal cannot be solved in time (3 − ε) tw( G ) | V ( G )| O (1), For any q ≥ 3, q -C oloring cannot be solved in time ( q − ε) tw( G ) | V ( G )| O (1), P artition I nto T riangles cannot be solved in time (2 − ε) tw( G ) | V ( G )| O (1). Our lower bounds match the running times for the best known algorithms for the problems, up to the ε in the base.

Details

I&C Journal 2011 Journal Article

On the complexity of some colorful problems parameterized by treewidth

  • Michael R. Fellows
  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Frances Rosamond
  • Saket Saurabh
  • Stefan Szeider
  • Carsten Thomassen

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph. 1. The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W [ 1 ] -hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W [ 1 ] -hard, parameterized by treewidth. 2. An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W [ 1 ], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W [ 1 ] -hard for forests, parameterized by the number of colors on the lists. 3. The list chromatic number χ l ( G ) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L v of colors, where each list has length at least r, there is a choice of one color from each vertex list L v yielding a proper coloring of G. We show that the problem of determining whether χ l ( G ) ⩽ r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

Details DOI

SODA Conference 2011 Conference Paper

Slightly Superexponential Parameterized Problems

  • Daniel Lokshtanov
  • Dániel Marx
  • Saket Saurabh 0001

A central problem in parameterized algorithms is to obtain algorithms with running time f ( k ) · n O (1) such that f is as slow growing function of the parameter k as possible. In particular, the first natural goal is to make f ( k ) single-exponential, that is, c k for some constant c. This has led to the development of parameterized algorithms for various problems where f ( k ) appearing in their running time is of form 2 O ( k ). However there are still plenty of problems where the “slightly superexponential” f ( k ) appearing in the best known running time has remained non single-exponential even after a lot of 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. More precisely we prove following tight lower bounds, for three natural problems, arising from three different domains: The pattern matching problem C losest S tring is known to be solvable in time 2 O ( d log d ) · n O (1) and 2 O ( d log |σ|) · n O (1). We show that there is no 2 o ( d log d ). · n O (1) and 2 o ( d log |σ|) · n O (1) time algorithm, unless Exponential Time Hypothesis (ETH) fails. The graph embedding problem D istortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be done in time 2 O ( d log d ) · n O (1). We show that there is no 2 o ( d log d ) · n O (1) time algorithm, unless ETH fails. The D isjoint P aths problem can be solved in time in time 2 O ( w log w ) · n O (1) on graphs of treewidth at most w. We show that there is no 2 o ( w log w ) · n O (1) time algorithm, unless ETH fails. To obtain our result we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. We believe that many further results of this form can be obtained by using the framework of the current paper.

Details

MFCS Conference 2010 Conference Paper

Algorithmic Lower Bounds for Problems on Decomposable Graphs

  • Daniel Lokshtanov

Abstract The treewidth and cliquewidth of a graph are central notions in graph theory and graph algorithms. Many NP-hard problems become tractable when the treewidth or cliquewidth of the input graph is bounded by a constant. In this talk I will briefly survey the known algorithmic results for graphs of bounded treewidth and cliquewidth, and give an overview of a line of work that explores the limits of tractability of problems on graphs of bounded treewidth or cliquewidth. Specifically, we will consider the following questions: Which problems are solvable in polynomial time on graphs of bounded treewidth, but require that the degree of the polynomial grows with the treewidth? Which problems are harder on bounded cliquewidth graphs than on bounded treewidth graphs? Can the known algorithms for problems on graphs of bounded treewidth and cliquewidth be improved?

Details

SODA Conference 2010 Conference Paper

Algorithmic Lower Bounds for Problems Parameterized with Clique-Width

  • Fedor V. Fomin
  • Petr A. Golovach
  • Daniel Lokshtanov
  • Saket Saurabh 0001

Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the tree-width of the input graph. On the other hand if we restrict ourselves to graphs of clique-width at most t, then there are many natural problems for which the running time of the best known algorithms is of the form n f ( t ), where n is the input length and f is some function. It was an open question whether natural problems like Graph C oloring, M ax -C ut, E dge D ominating S et, and H amiltonian P ath are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [ SODA 2009 ], we showed that unless FPT≠W[1], there is no algorithm with run time O ( g ( t ) · n c ), for some function g and a constant c not depending on t, for G raph C oloring, E dge D ominating S et and H amiltonian P ath. But the lower bounds obtained in [ SODA 2009 ] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for M ax -C ut and E dge D ominating S et by showing that both problems cannot be solved in time f ( t ) n o ( t ), unless Exponential Time Hypothesis (ETH) collapses; and can be solved in time n O ( t ), where f is an arbitrary function of t, on input of size n and clique-width at most t. We obtain our lower bounds by giving non-trivial structure-preserving “linear FPT reductions”.

Details

SODA Conference 2010 Conference Paper

Bidimensionality and Kernels

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Dimitrios M. Thilikos

Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [ J. ACM 2005 ] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on H -minor free graphs. Demaine and Hajiaghayi [ SODA 2005 ] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In parameterized complexity, each problem instance comes with a parameter k and the parameterized problem is said to admit a linear kernel if there is a polynomial time algorithm, called a kernelization algorithm, that reduces the input instance to an equivalent instance (called kernel ) with size linearly bounded by k. We show that “essentially” all bidimensional problems not only have sub-exponential time algorithms and PTASs but they also have linear kernels, affirmatively answering an open question from [ J. ACM 2005 ] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph H ) H as a minor. Recently, Bodlaender et al. [ FOCS 2009 ] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality we are able to extend these results to minor-free and apex-minor-free graphs. Our results imply that a multitude of bidimensional problems, which include D ominating S et, F eedback V ertex S et, E dge D ominating S et, V ertex C over, r -D ominating S et, C onnected D ominating S et, C ycle P acking, C onnected V ertex C over, A lmost C onstant T reewidth, and various other vertex covering and packing problems, admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H -minor-free graphs were known prior to our work.

Details

STOC Conference 2010 Conference Paper

Saving space by algebraization

  • Daniel Lokshtanov
  • Jesper Nederlof

The Subset Sum and Knapsack problems are fundamental NP-complete problems and the pseudo-polynomial time dynamic programming algorithms for them appear in every algorithms textbook. The algorithms require pseudo-polynomial time and space. Since we do not expect polynomial time algorithms for Subset Sum and Knapsack to exist, a very natural question is whether they can be solved in pseudo-polynomial time and polynomial space . In this paper we answer this question affirmatively, and give the first pseudo-polynomial time, polynomial space algorithms for these problems. Our approach is based on algebraic methods and turns out to be useful for several other problems as well. Then we show how the framework yields polynomial space exact algorithms for the classical Traveling Salesman, Weighted Set Cover and Weighted Steiner Tree problems as well. Our algorithms match the time bound of the best known pseudo-polynomial space algorithms for these problems.

Details

IJCAI Conference 2009 Conference Paper

  • Michael R. Fellows
  • Frances A. Rosamond
  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh
  • Yngve Villanger

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naı̈ve brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time O(τ(k) · nc ), where τ is a function depending on k only and c is a constant independent of k. We demonstrate the applicability of this approach on different problems like r-CENTER, VERTEX COVER, ODD CYCLE TRANSVERSAL, MAX-CUT, and MIN-BISECTION. In particular, on planar graphs, all our algorithms searching for a klocal improvement run in time O(2O(k) ·n2 ), which is polynomial for k = O(log n). We also complement the algorithms with complexity results indicating that—brute force search is unavoidable—in more general classes of sparse graphs.

PDF Details

FOCS Conference 2009 Conference Paper

(Meta) Kernelization

  • Hans L. Bodlaender
  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Eelko Penninkx
  • Saket Saurabh 0001
  • Dimitrios M. Thilikos

Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, we can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this paper, we show that all problems expressible in Counting Monadic Second Order Logic and satisfying a compactness property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker compactness condition admit a linear kernel on graphs of bounded genus. The study of kernels on planar graphs was initiated by a seminal paper of Alber, Fellows, and Niedermeier [J. ACM, 2004 ] who showed that Planar Dominating Set admits a linear kernel. Following this result, a multitude of problems have been shown to admit linear kernels on planar graphs by combining the ideas of Alber et al. with problem specific reduction rules. Our theorems unify and extend all previously known kernelization results for planar graph problems. Combining our theorems with the Erdos-Posa property we obtain various new results on linear kernels for a number of packing and covering problems.

Details

SODA Conference 2009 Conference Paper

Clique-width: on the price of generality

  • Fedor V. Fomin
  • Petr A. Golovach
  • Daniel Lokshtanov
  • Saket Saurabh 0001

Many hard problems can be solved efficiently when the input is restricted to graphs of bounded treewidth. By the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the treewidth of the input graph. Moreover, for every fixed k ≥ 0, such problems can be solved in linear time on graphs of treewidth at most k. In particular, this implies that basic problems like D ominating S et, G raph C oloring, C lique, and H amiltonian C ycle are solvable in linear time on graphs of bounded treewidth. A significant amount of research in graph algorithms has been devoted to extending this result to larger classes of graphs. It was shown that some of the algorithmic meta-theorems for treewidth can be carried over to graphs of bounded clique-width. Courcelle, Makowsky, and Rotics proved that the analogue of Courcelle's result holds for graphs of bounded clique-width when the logical formulas do not use edge set quantifications. Despite of its generality, this does not resolve the parameterized complexity of many basic problems concerning edge subsets (like Edge Dominating Set), vertex partitioning (like Graph Coloring), or global connectivity (like Hamiltonian Cycle). There are various algorithms solving some of these problems in polynomial time on graphs of clique-width at most k. However, these are not fixed parameter tractable algorithms and have typical running times O ( n f ( k ) ), where n is the input length and f is some function. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, i. e. solvable in time O ( g ( k )· n c ), for some function g and a constant c not depending on k. In this paper we resolve this problem by showing that E dge D ominating S et, H amiltonian C ycle, and G raph C oloring are W [1]-hard parameterized by clique-width. This shows that the running time O ( n f ( k ) ) of many clique-width based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W [1])—the price we pay for generality.

Details

MFCS Conference 2007 Conference Paper

On the Complexity of Computing Treelength

  • Daniel Lokshtanov

Abstract We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of bounded treelength [6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has treelength at most k is NP-complete for every fixed k ≥ 2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than \(\frac{3}{2}\). Additionally, we show that treelength can be computed in time O * (1. 8899 n ) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph.

Details
v2026.09.13