Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Details Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

2010-01-06

arxiv.org/abs/1001.0821v1

Computer Science

Data Structures and Algorithms

Scientific paper

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, {\sc $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(\sqrt{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(\sqrt{k})}n + n^{O(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely {\sc $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(\sqrt{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 for any $\epsilon>0$, the {\sc $k$-Directed Path} problem is solvable in time $O((1+\epsilon)^k n^{f(\epsilon)})$, 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.

Affiliated with

Also associated with

No associations

Rating

Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163897