Search

In the Min k-Cut problem, the input consists of an edge weighted graph G and an integer k, and the task is to partition the vertex set into k nonempty 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, Lee, and Li [Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821--2837] initiated the study of FPT-approximation for the Min k-Cut problem and gave a 1.9997-approximation algorithm running in time 2\scrO (k6)n\scrO (1). Later, the same set of authors [Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113--123] designed a (1 + \epsilon)-approximation algorithm that runs in time (k/\epsilon)\scrO (k)nk+\scrO (1) and a 1.81-approximation algorithm running in time 2\scrO (k2)n\scrO (1). More, recently, Kawarabayashi and Lin [Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990--999] gave a (5/3+\epsilon)-approximation for Min k-Cut running in time 2\scrO (k2 log k)n\scrO (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 the exponential time hypothesis and constants in the exponent). In particular, for every \epsilon > 0, the algorithm obtains a (1 + \epsilon)-approximate solution in time (k/\epsilon)\scrO (k)n\scrO (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\scrO (k)n\scrO (1) on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The latter two are of independent interest. [ABSTRACT FROM AUTHOR]

A class of graphs ℱ ${\rm{ {\mathcal F} }}$ admits the Erdős–Pósa property if for any graph G $G$, either G $G$ has k $k$ vertex‐disjoint "copies" of the graphs in ℱ ${\rm{ {\mathcal F} }}$, or there is a set S⊆V(G) $S\subseteq V(G)$ of f(k) $f(k)$ vertices that intersects all copies of the graphs in ℱ ${\rm{ {\mathcal F} }}$. For any graph class G ${\mathscr{G}}$, it is natural to ask whether the family of obstructions to G ${\mathscr{G}}$ has the Erdős–Pósa property. In this paper, we prove that the family of obstructions to interval graphs—namely, the family of chordless cycles and asteroidal witnesses (AWs)—admits the Erdős–Pósa property. In turn, this yields an algorithm to decide whether a given graph G $G$ has k $k$ vertex‐disjoint AWs and chordless cycles, or there exists a set of O(k2logk) ${\mathscr{O}}({k}^{2}\mathrm{log}k)$ vertices in G $G$ that hits all AWs and chordless cycles. [ABSTRACT FROM AUTHOR]

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: A induces a subgraph of G of treewidth O(√k log k), and 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 (2O(√k log² k)⋅nO(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-time parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log² k)nO(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 could 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. [ABSTRACT FROM AUTHOR]

In a reconfiguration version of a decision problem Q the input is an instance of Q and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K d , d as a subgraph, for some constant d ≥ 1 . We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k + ℓ , the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs. [ABSTRACT FROM AUTHOR]

We prove that if (min ⁡ , +) - Convolution can be solved in O (τ (n)) time, then Bisection on treewidth t graphs can be solved in time O (8 t t O (1) log ⁡ n ⋅ τ (n)) , assuming a decomposition of width t as input. Plugging in the O (n 2) time algorithm for (min ⁡ , +) - Convolution yields a O (8 t t O (1) n 2 log ⁡ n) time algorithm for Bisection. This improves over the (dependence on n of the) O (2 t n 3) time algorithm of Jansen et al. [SICOMP 2005] at the cost of a worse dependence on t. "Conversely", we show that if Bisection can be solved in time O (β (n)) on edge weighted trees, then so can (min ⁡ , +) - Convolution. Thus, obtaining a sub-quadratic algorithm for Bisection on trees is extremely challenging, and could even be impossible. On the other hand, for unweighted graphs of treewidth t , by making use of the algorithm for Bounded Difference (min ⁡ , +) - Convolution of Chan and Lewenstein [STOC 2015], we obtain a sub-quadratic algorithm for Bisection with running time O (8 t t O (1) n 1.864 log ⁡ n). [ABSTRACT FROM AUTHOR]

We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(p k)(n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2o(p k)(n + m)O(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2O(p k)(n + m)O(1)-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a 2k-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time 2O(p k log k)(n + m). This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width O(p k). [ABSTRACT FROM AUTHOR]

We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in O (n + m ′) time, where m ′ is the number of edges in the completed graph. This matches the complexity of the algorithm in (Lokshtanov et al., 2010) and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to O (n + m log 2 n) when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only O (n) edges, require Ω (n 2) edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as O (n ∕ log 2 n). [ABSTRACT FROM AUTHOR]

Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional 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. [ABSTRACT FROM AUTHOR]

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

We give algorithms with running time 2 O (k log k) · n O (1) for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains a path on exactly/at least k vertices, a cycle on exactly k vertices, a cycle on at least k vertices, a feedback vertex set of size at most k, and a set of k pairwise vertex-disjoint cycles. For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time 2 O (k 0.75 log k) · n O (1) . Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to k O (1) and there exists a solution that crosses every separator at most O (k) times. The running times of our algorithms are optimal up to the log k factor in the exponent, assuming the exponential time hypothesis. [ABSTRACT FROM AUTHOR]

The family of judicious partitioning problems, introduced by Bollobàs and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection, and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB (BJB) also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobàs and Scott and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is fixed parameter tractable (FPT) (which also proves that JB is FPT). [ABSTRACT FROM AUTHOR]

The Cycle Packing problem asks whether a given undirected graph G = (V;E) con- tains k vertex-disjoint cycles. Since the publication of the classic Erd}os{Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particu- lar, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson{Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2O(k2) jV j using exponential space. In the case a solu- tion exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2O(k log2 k) jV j-time (deterministic) algorithm using exponential space, which is a consequence of the Erd}os{Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2o(k log2 k) jV jO(1), beating the bound 2O(k log2 k) jV jO(1), has been found. In light of this, it seems natural to ask whether the 2O(k log2 k) jV jO(1) bound is essentially optimal. In this paper, we answer this question negatively by developing a 2 O(k log2 k log log k) jV j-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2O(k log2 k) jV jO(1), our algorithm runs in time linear in jV j, and its space complexity is polynomial in the input size. [ABSTRACT FROM AUTHOR]

In the classic Minimum Bisection problem we are given as input an undirected graph G and an integer k. The task is to determine whether there is a partition of V (G) into two parts A and B such that | | A| | B| | \leq 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for Minimum Bisection with running time 2O(k3)n³ log³ n. This is the first fixed parameter tractable algorithm for Minimum Bisection parameterized by k. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected"" in the following sense: any separator of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek a bisection of minimum weight among solutions that contain at most k edges. [ABSTRACT FROM AUTHOR]

In algorithmic graph theory, a classic open question is to determine the complexity of the MAXIMUM INDEPENDENT SET problem on Pt-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t≤5 (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5-7, 2014, pp 570-581, 2014), and an algorithm for t=6 announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on P6-free graphs. CoRR, arXiv:1707.05491, 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any t≥1, there is an algorithm for MAXIMUM INDEPENDENT SET on Pt-free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in 2O(tnlogn) time on Pt-free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2O(|V(H)|n+mlog(n+m)), even if d is part of the input.Otherwise, assuming the Exponential-Time Hypothesis (ETH), there is no 2o(n+m)-time algorithm for d-SCATTERED SET for any fixed d≥3 on H-free graphs with n-vertices and m-edges. [ABSTRACT FROM AUTHOR]

A vertex subset S in a graph G is a dominating set if every vertex not contained in S has a neighbor in S. A dominating set S is a connected dominating set if the subgraph G[S] induced by S is connected. A connected dominating set S is a minimal connected dominating set if no proper subset of S is also a connected dominating set. We prove that there exists a constant \epsilon ∊10-50 such that every graph G on n vertices has at most O(2(1-∊)n) minimal connected dominating sets. For the same ∊ we also give an algorithm with running time 2(1-∊)n· nO(1) to enumerate all minimal connected dominating sets in an input graph G. [ABSTRACT FROM AUTHOR]

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP ⊆ coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t ≥ 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2c² k7+c log³ k) whenever c ∈ o(√k). Thus the kernel size varies from being subexponential when c ∈ o(√k), to quasi-polynomial when c ∈ o(logℓ k), ℓ ∈ R+, and polynomial when c ∈ O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t ∈ O(k∈) for any 0≤∈< 1, unless NP 埦 coNP/poly. [ABSTRACT FROM AUTHOR]

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k . We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set . We denote the former by Image 1 and the latter by Image 2 . Both Image 1 and Image 2 are PSPACE -complete on graphs of bounded bandwidth and W[1] -hard parameterized by k on general graphs. We show that Image 1 is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For Image 2 , we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques. [ABSTRACT FROM AUTHOR]

For a target rank r, the rigidity of a matrix A over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in computational complexity theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of parameterized complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of parameterized complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in the case F = R or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in real algebraic geometry, which are not well known in parameterized complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem. [ABSTRACT FROM AUTHOR]

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(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 the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings s1, ..., st over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings si, 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in times 2O(d log d) · nO(1) and 2O(d log |Σ|) · nO(1). We show that there are no 2o(d log d) · nO(1) or 2o(d log |Σ|) · nO(1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time 2O(w log w) ·nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. To obtain our results, 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. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future. [ABSTRACT FROM AUTHOR]

The ArtGallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ArtGallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of ArtGallery are all W[1]-hard with respect to k [Bonnet and Miltzow in 24th Annual European Symposium on Algorithms (Aarhus 2016)], the classic variant has an O (log k) -approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ R -complete [Abrahamsen et al. in 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ArtGallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of ArtGallery, this case can also be viewed as the classic DominatingSet problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-VertexArtGallery is solvable in time r O (r 2) · n O (1) . Furthermore, our approach extends to assert that Vertex-BoundaryArtGallery and Boundary-VertexArtGallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-VertexArtGallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions. [ABSTRACT FROM AUTHOR]

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph G, a subset of vertices T and a positive integer k and the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle containing a vertex from T. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726{1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time ƒ(k)mn³ using the theory of graph minors, where ƒ is some function, and n and m denote the number of vertices and edges in the graph. However, the dependence of this function on k is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on k is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time 2O(k³ log k)mn² log² n, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of "generalized" important separators to reduce the subset version of this problem to the standard version of the problem. [ABSTRACT FROM AUTHOR]

Let $${\mathcal {F}}$$ be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, such that $$G-S$$ belongs to $${\mathcal {F}}$$ , is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when $${\mathcal {F}}$$ is either the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ , the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time $$12^k n^{\mathcal {O}(1)}$$ for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of t he directed variant of the classical STEINER Tree problem on various classes of directed sparse graphs. While the parameterized complexity of STEINER Tree parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected STEINER Tree problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for DIRECTED STEINER Tree (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for DOMINATING SET on sparse undirected graphs. These algorithms are asymptotically optimal. [ABSTRACT FROM AUTHOR]

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1, G2, either concludes that one of these graphs has treewidth at least k or determines whether G1 and G2 are isomorphic. The running time of the algorithm on an n-vertex graph is ...⋅n5, 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 ...⋅n5 time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k or (i) finds in an isomorphic-invariant way a graph c(G) that is isomorphic to G; (ii) finds an isomorphism-invariant construction term--an algebraic expression that encodes G together with a tree decomposition of G of width less than k. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for G1 and G2 are equal. [ABSTRACT FROM AUTHOR]

In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G \ S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPTc for any constant c. In this paper we give an O(k5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on systems of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate. [ABSTRACT FROM AUTHOR]

We study a general class of problems called F-DELETION problems. In an F-DELETION problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and an approximation algorithm achieving an approximation ratio of O(log3/2 OPT), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph θc as a minor for a fixed integer c. The graph θc consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as VERTEX COVER, FEEDBACK VERTEX SET, and DIAMOND HITTING SET. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 n). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 n) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP⊆coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, ; SWAT, Springer, Berlin, ) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels. [ABSTRACT FROM AUTHOR]

Let η≥0 be an integer and G be a graph. A set X⊆ V( G) is called a η- treewidth modulator in G if G∖ X has treewidth at most η. Note that a 0-treewidth modulator is a vertex cover, while a 1-treewidth modulator is a feedback vertex set of G. In the η/ ρ- Treewidth Modulator problem we are given an undirected graph G, a ρ-treewidth modulator X⊆ V( G) in G, and an integer ℓ and the objective is to determine whether there exists an η-treewidth modulator Z⊆ V( G) in G of size at most ℓ. In this paper we study the kernelization complexity of η/ ρ- Treewidth Modulator parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1≤ η< ρ, or η=0 and 2≤ ρ, the η/ ρ- Treewidth Modulator problem does not admit a polynomial kernel unless NP⊆coNP/poly. This resolves an open problem raised by Bodlaender and Jansen (STACS, pp. 177-188, ). Finally, we complement our kernelization lower bounds by showing that ρ/0- Treewidth Modulator admits a polynomial kernel for any fixed ρ. [ABSTRACT FROM AUTHOR]

According to the classical Erdős-Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most [ABSTRACT FROM AUTHOR]

Abstract: 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 -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) . Our first result shows that if μ is an arbitrary polynomial-time computable monotone function, then -Partition can be solved in time , 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 -Partition can be solved in time and in time on n-vertex graphs, i.e., the problem is fixed-parameter tractable parameterized by p or by q. [Copyright &y& Elsevier]

Abstract: In the Subgraph Isomorphism problem we are given two graphs F and G on k and n vertices respectively as an input, and the question is whether there exists a subgraph of G isomorphic to F. We show that if the treewidth of F is at most t, then there is a randomized algorithm for the Subgraph Isomorphism problem running in time . Our proof is based on a novel construction of an arithmetic circuit of size at most for a new multivariate polynomial, Homomorphism Polynomial, of degree at most k, which in turn is used to solve the Subgraph Isomorphism problem. For the counting version of the Subgraph Isomorphism problem, where the objective is to count the number of distinct subgraphs of G that are isomorphic to F, we give a deterministic algorithm running in time and space or . We also give an algorithm running in time and taking space. Here p and t denote the pathwidth and the treewidth of F, respectively. Our work improves on the previous results on Subgraph Isomorphism, it also extends and unifies most of the known results on sub-path and sub-tree isomorphisms. [Copyright &y& Elsevier]

We give a linear-time algorithm to compute the cutwidth of threshold graphs, thereby resolving the computational complexity of cutwidth on this graph class. Threshold graphs are a well-studied subclass of interval graphs and of split graphs, both of which are unrelated subclasses of chordal graphs. To complement our result, we show that cutwidth is NP-complete on split graphs, and consequently also on chordal graphs. The cutwidth of interval graphs is still open, and only very few graph classes are known so far on which polynomial-time cutwidth algorithms exist. Thus we contribute to define the border between graph classes on which cutwidth is polynomially solvable and on which it remains NP-complete. [ABSTRACT FROM AUTHOR]

Abstract: Let be an unweighted connected graph on vertices. We show that an embedding of the shortest path metric of into the line with minimum distortion can be found in time . This is the first algorithm breaking the trivial -barrier. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

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 a bounded treelength Dourisboure and Gavoille (2007) . 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 a treelength at most is NP-complete for every fixed , and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than . Additionally, we show that treelength can be computed in time 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. [Copyright &y& Elsevier]

Abstract: A cograph completion of an arbitrary graph is a cograph supergraph of on the same vertex set. Such a completion is called minimal if the set of edges added to is inclusion minimal. In this paper we present two results on minimal cograph completions. The first is a characterization that allows us to check in linear time whether a given cograph completion is minimal. The second result is a vertex incremental algorithm to compute a minimal cograph completion of an arbitrary input graph in time. An extended abstract of the result has been already presented at FAW 2008 [D. Lokshtanov, F. Mancini, C. Papadopoulos, Characterizing and computing minimal cograph completions, in: Proceedings of FAW’08–2nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147158. ]. [Copyright &y& Elsevier]

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml( G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things: [ABSTRACT FROM AUTHOR]

Abstract: A cycle in a graph is isometric if the distance between two vertices in the cycle is equal to their distance in . Finding the longest isometric cycle of a graph is then a natural variant of the problem of finding a longest cycle. While most variants of the longest cycle problem are NP-complete, we show that quite surprisingly, one can find a longest isometric cycle in a graph in polynomial time. [Copyright &y& Elsevier]

Abstract: Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power to each vertex of a given graph, such that every vertex of the graph is within distance from some vertex having . The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in , and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach. [Copyright &y& Elsevier]

Motivation Bait enrichment is a protocol that is becoming increasingly ubiquitous as it has been shown to successfully amplify regions of interest in metagenomic samples. In this method, a set of synthetic probes ('baits') are designed, manufactured and applied to fragmented metagenomic DNA. The probes bind to the fragmented DNA and any unbound DNA is rinsed away, leaving the bound fragments to be amplified for sequencing. Metsky et al. demonstrated that bait-enrichment is capable of detecting a large number of human viral pathogens within metagenomic samples. Results We formalize the problem of designing baits by defining the Minimum Bait Cover problem, show that the problem is NP-hard even under very restrictive assumptions, and design an efficient heuristic that takes advantage of succinct data structures. We refer to our method as Syotti. The running time of Syotti shows linear scaling in practice, running at least an order of magnitude faster than state-of-the-art methods, including the method of Metsky et al. At the same time, our method produces bait sets that are smaller than the ones produced by the competing methods, while also leaving fewer positions uncovered. Lastly, we show that Syotti requires only 25 min to design baits for a dataset comprised of 3 billion nucleotides from 1000 related bacterial substrains, whereas the method of Metsky et al. shows clearly super-linear running time and fails to process even a subset of 17% of the data in 72 h. Availability and implementation https://github.com/jnalanko/syotti. Supplementary information Supplementary data are available at Bioinformatics online. [ABSTRACT FROM AUTHOR]

The computational complexity of the graph modification problems Threshold Editing and Chain Editing has been an important open question in computational graph theory for more than 15 years. These problems consist of adding and deleting the fewest possible edges to transform a graph into a threshold or chain graph. We show that both problems are NP -hard, resolving a conjecture by Natanzon, Shamir, and Sharan from 2001. On the positive side, we show both problems admit quadratic vertex kernels and give subexponential time parameterized algorithms solving both problems in 2 O (k log ⁡ k) + n O (1) time. Few natural problems are known to be in this complexity class. These results also extend to the completion and deletion variants of both problems, and threshold/chain graphs are the only known graph classes for which all three versions—completion, deletion, and editing—are both NP -complete and solvable in subexponential parameterized time. [ABSTRACT FROM AUTHOR]

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d > 1 contains a cycle of length at least d + 1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d + 1. But can we decide in polynomial time whether a graph contains a cycle of length at least d + 2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d + k can be done in time 2O(k) .| V (G)| O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log n can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2O(k) .nO(1). We complement these results by showing that the choice of degeneracy as the ``above guarantee parameterization"" is optimal in the following sense: For any ε > 0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1 + ε )d. [ABSTRACT FROM AUTHOR]

Consider a secure environment (say an airport) that has a unique entry and a unique exit point with multiple inter-crossing paths between them. We want to place (minimum number of) trackers (or check points) at some specific intersections so that based on the sequence of trackers a person has encountered, we can identify the exact path traversed by the person. Motivated by such applications, we study the Tracking Paths problem in this paper. Given an undirected graph with a source s, a destination t and a non-negative integer k, the goal is to find a set of at most k vertices, a tracking set, that intersects each s–t path in a unique sequence. Such a set enables a central controller to track all the paths from s to t. We first show that the problem is NP-complete. Then we show that finding a tracking set of size at most k is fixed-parameter tractable when parameterized by the solution size. More specifically, given an undirected graph on n vertices and an integer k, we give a polynomial time algorithm that either determines that the graph cannot be tracked by k trackers or produces an equivalent instance with O (k 7) edges. [ABSTRACT FROM AUTHOR]

In the Steiner Tree problem, we are given as input a connected n-vertex graph with edge weights in {1,2,...,W}, and a set of k terminal vertices. Our task is to compute a minimum-weight tree that contains all of the terminals. The main result of the paper is an algorithm solving Steiner Tree in time O(7.97k·n4·logW) and using O(n3·lognW·logk) space. This is the first single-exponential time, polynomial space FPT algorithm for the weighted Steiner Tree problem. Whereas our main result seeks to optimize the polynomial dependency in n for both the running time and space usage, it is possible to trade between polynomial dependence in n and the single-exponential dependence in k to obtain faster running time as a function of k, but at the cost of increased running time and space usage as a function of n. In particular, we show that there exists a polynomial space algorithm for Steiner Tree running in O(6.751knO(1)logW) time. Finally, by pushing such a trade-off between a polynomial in n and an exponential in k dependencies, we show that for any ϵ > 0 there is an n O(f(ϵ))logW space 4(1+ϵ)kn O(f(ϵ))logW time algorithm for Steiner Tree, where f is a computable function depending only on ϵ. [ABSTRACT FROM AUTHOR]

Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, in the SPACE COVER problem, we are given a matrix M and a subset of its columns T; the task is to find a minimum set F of columns of M disjoint with T such that the linear span of F contains all vectors of T. For graphic matroids this problem is essentially Steiner Forest and for cographic matroids this is a generalization of MULTIWAY CUT. Our main result is the algorithm with running time 2Oh(k). | | M| |Oh(1) solving SPACE COVER in the case when M is a totally unimodular matrix over rationals, where k is the size of F. In other words, we show that on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace. [ABSTRACT FROM AUTHOR]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]

In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs $$G$$ and $$H$$ , each with a linear order defined on its vertices, a function $$L$$ that associates with every vertex in $$G$$ a list of vertices in $$H$$ , and a parameter $$k$$ . The question is to decide if there is a subset $$S \subseteq V(G)$$ of $$k$$ vertices and a mapping/embedding from $$S$$ to $$V(H)$$ such that: (1) every vertex of $$S$$ is mapped to a vertex from its associated list, (2) the linear orders inherited by $$S$$ and its image under the mapping are respected, and (3) if there is an edge between two vertices in $$S$$ then there is an edge between their images. If we change condition (3) to 'there is an edge between two vertices in $$S$$ if and only if there is an edge between their images', we obtain the Ordered List Induced Subgraph Embedding problem (p-OLISE). The p-OLSE and p-OLISE problems model various problems in Bioinformatics related to structural comparison/alignment of proteins. We investigate the complexity of p-OLSE and p-OLISE with respect to the following structural parameters: the width $$\Delta _L$$ of the function $$L$$ (size of the largest list), and the maximum degree $$\Delta _H$$ of $$H$$ and $$\Delta _G$$ of $$G$$ . In terms of the structural parameters under consideration, we draw a complete complexity landscape of p-OLSE and p-OLISE (and their optimization versions) with respect to the computational frameworks of classical complexity, parameterized complexity, and approximation. [ABSTRACT FROM AUTHOR]

We determine the maximum number of edges that a chordal graph G can have if its degree, Δ (G) , and its matching number, ν (G) , are bounded. To do so, we show that for every d , ν ∈ N , there exists a chordal graph G with Δ (G) < d and ν (G) < ν whose number of edges matches the upper bound, while having a simple structure: G is a disjoint union of cliques and stars. [ABSTRACT FROM AUTHOR]

We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an n-vertex graph of clique-width t both problems (1) cannot be solved in time f(t)no(t) for any function f of t unless exponential time hypothesis fails, and (2) can be solved in time nO(t). [ABSTRACT FROM AUTHOR]

Abstract: 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 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 . 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 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 , for any , 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. [Copyright &y& Elsevier]