# «Abstract In 2000 Alber et al. [SWAT 2000 ] obtained the ﬁrst parameterized subexponential algorithm on √ undirected planar graphs by showing that ...»

Beyond Bidimensionality: Parameterized Subexponential

Algorithms on Directed Graphs

Frederic Dorn∗ Fedor V. Fomin∗ Daniel Lokshtanov ∗ Venkatesh Raman†

Saket Saurabh∗

Abstract

In 2000 Alber et al. [SWAT 2000 ] obtained the ﬁrst parameterized subexponential algorithm on

√

undirected planar graphs by showing that k-DOMINATING SET is solvable in time 2O( k) nO(1),

where n is the input size. This result triggered an extensive study of parameterized problems on planar and more general classes of sparse graphs and culminated in the creation of Bidimensionality Theory by Demaine et al. [J. ACM 2005 ]. The theory utilizes deep theorems from Graph Minor Theory of Robertson and Seymour, and provides a simple criteria for checking whether a parameterized problem is solvable in subexponential time on sparse graphs.

While bidimensionality theory is an algorithmic framework on undirected graphs, it remains unclear how to apply it to problems on directed graphs. The main reason is that Graph Minor Theory for directed graphs is still in a nascent stage and there are no suitable obstruction theorems so far.

Even the analogue of treewidth for directed graphs is not unique and several alternative deﬁnitions have been proposed.

In this paper we make the ﬁrst 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 ﬁrst problem, k-LEAF OUT-BRANCHING, which is to ﬁnd an oriented spanning tree with at least k leaves, we obtain an algorithm solving the √ problem in time 2O( k log k) n + nO(1) on directed graphs whose underlying undirected graph excludes some ﬁxed graph H as a minor. For the special case when the input directed graph is planar, √ the running time can be improved to 2O( k) n + nO(1). The second example is a generalization of the DIRECTED HAMILTONIAN PATH problem, namely k-INTERNAL OUT-BRANCHING, which is to ﬁnd an oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the √ problem in time 2O( k log k) +nO(1) on directed graphs whose underlying undirected graph excludes some ﬁxed apex graph H as a minor. Finally, we observe that for anyε 0, the k-DIRECTED PATH problem is solvable in time O((1 + ε)k nf (ε) ), where f is some function of ε.

Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem speciﬁc combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

1 Introduction Parameterized complexity theory is a framework for a reﬁned analysis of hard (NP-hard) problems.

Here, every input instance I of a problem Π is accompanied with an integer parameter k and Π is said to be ﬁxed parameter tractable (FPT) if there is an algorithm running in time f (k) · nO(1), where n = |I| and f is a computable function. A central problem in parameterized algorithms is to obtain algorithms ∗ Department of Informatics, University of Bergen, Norway.

{dorn|fedor.fomin|daniello|saket.saurabh}@ii.uib.no.

† The Institute of Mathematical Sciences, Chennai, India.

vraman@imsc.res.in with running time f (k) · nO(1) such that f is as slow growing function as possible. This has led to the development of various graph algorithms with running time 2O(k) nO(1) — notable ones include kFEEDBACK VERTEX SET [7], k-LEAF SPANNING TREE [28], k-ODD CYCLE TRANSVERSAL [31], k-PATH [4], and k-VERTEX COVER [8] in undirected graphs. A natural question was whether we can get subexponential time algorithms for these problems, that is, can we have algorithms with running time 2o(k) nO(1). It is now possible to show that these problems do not admit algorithms with running time 2o(k) nO(1) unless Exponential Time Hypothesis (ETH) [22, 27] fails. Finding algorithms with subexponential running time on general undirected graphs is a trait uncommon to parameterized algorithms.

However, the situation changes completely when we consider problems on topological graph classes like planar graphs or graphs of bounded genus. In 2000, Alber et al. [1] obtained the ﬁrst parameterized subexponential algorithm on undirected planar graphs by showing that k-DOMINATING SET is solvable √ in time 2O( k) nO(1). This result triggered an extensive study of parameterized problems on planar and more general classes of sparse graphs like graphs of bounded genus, apex minor-free graphs and H-minor free graphs. All this work led to subexponential time algorithms for several fundamental problems like k-FEEDBACK VERTEX SET, k-EDGE DOMINATING SET, k-LEAF SPANNING TREE, k-PATH, k-r-DOMINATING SET, k-VERTEX COVER to name a few on planar graphs [1, 12, 25], and more generally, on H-minor-free graphs [13, 15, 16]. These algorithms are obtained by showing a combinatorial relation between the parameter and the structure of the input graph and proofs require strong graph theoretic arguments. This graph-theoretic and combinatorial component in the design of subexponential time parameterized algorithms makes it of an independent interest.

Demaine et al. [13] abstracted out the “common theme” among the parameterized subexponential time algorithms on sparse graphs and created the meta-algorithmic theory of Bidimensionality. The bidimensionality theory uniﬁes and improves almost all known previous subexponential algorithms on spare graphs. The theory is based on algorithmic and combinatorial extensions to various parts of Graph Minors Theory of Robertson and Seymour [32] and provides a simple criteria for checking whether a parameterized problem is solvable in subexponential time on sparse graphs. The theory applies to graph problems that are bidimensional in the sense that the value of the solution for the problem in question on k × k grid or “grid like graph” is at least Ω(k 2 ) and the value of solution decreases while contracting or sometime deleting the edges. Problems that are bidimensional include k-FEEDBACK VERTEX SET, k-EDGE DOMINATING SET, k-LEAF SPANNING TREE, k-PATH, k-r-DOMINATING SET, k-VERTEX COVER and many others. In most cases we obtain subexponential time algorithms for a problem using bidimensionality theory in following steps. Given an instance (G, k) to a bidimensional problem Π, √ in polynomial time we either decide that it is an yes instance to Π or the treewidth of G is O( k).

In the second case, using known constant factor approximation algorithm for the treewidth, we ﬁnd a √ tree decomposition of width O( k) for G and then solve the problem by doing dynamic programming over the obtained tree decomposition. This approach combined with Catalan structure based dynamic √ programming over graphs of bounded treewidth has led to 2O( k) nO(1) time algorithm for k-FEEDBACK VERTEX SET, k-EDGE DOMINATING SET, k-LEAF SPANNING TREE, k-PATH, k-r-DOMINATING SET, k-VERTEX COVER and many others on planar graphs [12, 13, 20] and in some cases like kDOMINATING SET and k-PATH on H-minor free graphs [13, 18]. We refer to surveys by Demaine and Hajiaghayi [15] and Dorn et al. [19] for further details on bidimensionality and subexponential parameterized algorithms.

While bidimensionality theory is a powerful algorithmic framework on undirected graphs, it remains unclear how to apply it to problems on directed graphs (or digraphs). The main reason is that Graph Minor Theory for digraphs is still in a nascent stage and there are no suitable obstruction theorems so far. For an example, even the ﬁrst step of the framework does not work easily on digraphs, as there is no unique notion of directed k × k grid. Given a k × k undirected grid we can make 2O(k ) distinct directed grids by choosing orientations for the edges. Hence, unless we can guarantee a lower bound of Ω(k 2 ) on the size of solution of a problem for any directed k × k grid, the bidimensionality theory does not look applicable for problems on digraphs. Even the analogue of treewidth for digraphs is not unique and several alternative deﬁnitions have been proposed. Only recently the ﬁrst non-trivial subexponential parameterized algorithms on digraphs was obtained. Alon et al. [3] introduced the method√ chromatic of coding, a variant of color coding [4], and combined it with divide and conquer to obtain 2O( k log k) nO(1) for k-FEEDBACK ARC SET in tournaments.

Our contribution. In this paper we make the ﬁrst step beyond bidimensionality by obtaining subexponential time algorithms for problems on sparse digraphs. We develop two different methods to achieve subexponential time parameterized algorithms for digraph problems when the input graph can be embedded on some surface or the underlying undirected graph excludes some ﬁxed graph H as a minor.

Quasi-bidimensionality. Our ﬁrst technique can be thought of as “bidimensionality in disguise”. We observe that given a digraph D, whose underlying undirected graph U G(D) excludes some ﬁxed graph H as a minor, if we can remove o(k 2 ) vertices from the given digraph to obtain a digraph whose underlying undirected graph has a constant treewidth, then the treewidth of U G(D) is o(k). So given an instance (D, k) to a problem Π, in polynomial time we either decide that it is an yes instance to Π or the treewidth of U G(D) is o(k). In the second case, as in the framework based on bidimensionality, we solve the problem by doing dynamic programming over the tree decomposition of U G(D). The dynamic programming part of the framework is problem-speciﬁc and runs in time 2o(k) + nO(1). We exemplify this technique on a well studied problem of k-LEAF OUT-BRANCHING.

We say that a subdigraph T on vertex set V (T ) of a digraph D on vertex set V (D) is an out-tree if T is an oriented tree with only one vertex r of in-degree zero (called the root). The vertices of T of out-degree zero are called leaves and every other vertex is called an internal vertex. If T is a spanning out-tree, that is, V (T ) = V (D), then T is called an out-branching of D. Now we are in position to deﬁne the problem formally.

k-LEAF OUT-BRANCHING (k-LOB): Given a digraph D with the vertex set V (D) and the arc set A(D) and a positive integer k, check whether there exists an out-branching with at least k leaves.

The study of k-LEAF OUT-BRANCHING has been at forefront of research in parameterized algorithms in the last few years. Alon et al. [2] showed that the problem is ﬁxed parameter tractable by giving an algorithm that decides in time O(f (k)n) whether a strongly connected digraph has an outbranching with at least k leaves. Bonsma and Dorn [6] extended this result to all digraphs, and improved the running time of the algorithm. Recently, Kneis et al. [28] provided a parameterized algorithm solving the problem in time 4k nO(1). This result was further improved to 3.72k nO(1) by Daligaut et al. [10].

Fernau et al. [21] showed that for the rooted version of the problem, where apart from the input instance we are also given a root r and one asks for a k-leaf out-branching rooted at r, admits a O(k 3 ) kernel.

Furthermore they also show that k-LOB does not admit polynomial kernel unless polynomial hierarchy collapses to third level. Finally, Daligault and Thomass´ [11] obtained a O(k 2 ) kernel for the rooted e version of the k-LOB problem and gave a constant factor approximation algorithm for k-LOB.

Using our new technique √ combination with kernelization result of [21], we get an algorithm for in O( k log k) n + nO(1) for digraphs whose underlying undirected graph is Hk-LOB that runs in time 2 √ minor-free. For planar digraphs our algorithm runs in 2O( k) n + nO(1) time.

Kernelization and Divide & Conquer. Our second technique is a combination of divide and conquer, kernelization and dynamic programming over graphs of bounded treewidth. Here, using a combination of kernelization and a Baker style layering technique for obtaining polynomial time approximation schemes [5], we reduce the instance of a given problem to 2o(k) nO(1) many new instances of the same problem. These new instances have the following properties: (a) the treewidth of the underlying undirected graph of these instances is bounded by o(k); and (b) the original input is an yes instance if and only if at least one of the newly generated instance is. We exhibit this technique on the k-INTERNAL OUT-BRANCHING problem, a parameterized version of a generalization of DIRECTED HAMILTONIAN PATH.

k-INTERNAL OUT-BRANCHING (k-IOB): Given a digraph D with the vertex set V (D) and the arc set A(D) and a positive integer k, check whether there exists an out-branching with at least k internal vertices.

Prieto and Sloper [30] studied the undirected version of this problem and gave an algorithm with running time 24k log k nO(1) and obtained a kernel of size O(k 2 ). Recently, Fomin et al. [23] obtained a vertex kernel of size 3k and gave an algorithm for the undirected version of k-IOB running in time 8k nO(1).

Gutin et al. [26] obtained an algorithm of running time 2O(k log k) nO(1) for k-IOB and gave a kernel of size of O(k 2 ) using the well known method of crown-decomposition. Cohen et al. [9] improved the algorithm for k-IOB and gave an algorithm with running time 49.4k nO(1). Here, we obtain a subexpo nential time algorithm for k-IOB with running time 2O( k log k) + nO(1) on directed planar graphs and digraphs whose underlying undirected graphs are apex minor-free.

Finally, we also observe that for any ε 0, there is an algorithm ﬁnding in time O((1 + ε)k nf (ε) ) a directed path of length at least k (the k-DIRECTED PATH problem) in a digraph which underlying undirected graph excludes a ﬁxed apex graph as a minor. The existence of subexponential parameterized algorithm for this problem remains open.

2 Preliminaries Let D be a digraph. By V (D) and A(D) we represent the vertex set and arc set of D, respectively.