The aim of directed Eulerian extension problems is to make a given directed, possibly arc-weighted, (multi-)graph Eulerian by adding a minimum-cost set of arcs. These problems have natural applications in scheduling and arc routing and are closely related to the Chinese Postman and Rural Postman problems. Our main result is to show that the NP-hard Weighted Multigraph Eulerian Extension problem is fixed-parameter tractable with respect to the number ${k}$ of extension arcs. For a directed $n$-vertex multigraph, the corresponding running time amounts to ${\ensuremath{O(4^{k}\cdot n^3)}}$. This also implies a fixed-parameter tractability result for the “equivalent” Rural Postman problem parameterized above guarantee. In addition, we present several polynomial-time algorithms for natural Eulerian extension problems, including undirected variants which can be defined analogously to the directed ones.

An out-tree T of a directed graph D is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By ℓ( D ) and ℓ s ( D ), we denote the maximum number of leaves over all out-trees and out-branchings of D , respectively. We give fixed parameter tractable algorithms for deciding whether ℓ s ( D ) ≥ k and whether ℓ( D ) ≥ k for a digraph D on n vertices, both with time complexity 2 O ( k log k ) · n O (1) . This answers an open question whether the problem for out-branchings is in FPT, and improves on the previous complexity of 2 O ( k log 2 k ) · n O (1) in the case of out-trees. To obtain the complexity bound in the case of out-branchings, we prove that when all arcs of D are part of at least one out-branching, ℓ s ( D ) ≥ ℓ( D )/3. The second bound we prove in this article states that for strongly connected digraphs D with minimum in-degree 3, ℓ s ( D ) ≥ Θ(√ n ), where previously ℓ s ( D ) ≥ Θ(3√ n ) was the best known bound. This bound is tight, and also holds for the larger class of digraphs with minimum in-degree 3 in which every arc is part of at least one out-branching.

The problem of {\sc Subgraph Isomorphism} is defined as follows: Given a \emph{pattern} $H$ and a \emph{host graph} $G$ on $n$ vertices, does $G$ contain a subgraph that is isomorphic to $H$? Eppstein [SODA 95, J'GAA 99] gives the first linear time algorithm for subgraph isomorphism for a fixed-size pattern, say of order $k$, and arbitrary planar host graph, improving upon the $O(n^{\sqrt{k}})$-time algorithm when using the ``Color-coding'' technique of Alon et al [J'ACM 95]. Eppstein's algorithm runs in time $k^{O(k)} n$, that is, the dependency on $k$ is superexponential. We improve the running time to $2^{O(k)} n$, that is, single exponential in $k$ while keeping the term in $n$ linear. Next to deciding subgraph isomorphism, we can construct a solution and count all solutions in the same asymptotic running time. We may enumerate $\omega$ subgraphs with an additive term $O(\omega k)$ in the running time of our algorithm. We introduce the technique of ``embedded dynamic programming'' on a suitably structured graph decomposition, which exploits the number and topology of the underlying drawings of the subgraph pattern (rather than of the host graph).

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^{\cO(\sqrt{k} \log k)} n+ n^{\cO(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^{\cO(\sqrt{k} )}n + n^{\cO(1)}$. The second example is a generalization of the {\sc 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^{\cO(\sqrt{k} \log k)} + n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $\ve>0$, the $k$-Directed Path problem is solvable in time $\cO((1+\ve)^k n^{f(\ve)})$, where $f$ is some function of $\ve$. 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.