Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs

Abstract : 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.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.251-262, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00455210
Contributor : Publications Loria <>
Submitted on : Tuesday, February 9, 2010 - 5:11:06 PM
Last modification on : Tuesday, February 9, 2010 - 5:23:19 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 7:47:14 PM

File

DornF.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455210, version 1

Collections

Citation

Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.251-262, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455210>

Share

Metrics

Record views

132

Document downloads

135