Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

الأصل · EN

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 2O(√k k) n+ nᵒ⁽¹⁾ 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 2O(√k)n + nᵒ⁽¹⁾. 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 2O(√k k) + nᵒ⁽¹⁾ on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that for any ε>0, the k-Directed Path problem is solvable in time O((1+ε)ᵏ nᶠ⁽ε⁾), 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.