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.
Type de document :
Communication dans un congrès
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

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455210
Contributeur : Publications Loria <>
Soumis le : mardi 9 février 2010 - 17:11:06
Dernière modification le : mercredi 29 novembre 2017 - 10:26:31
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:47:14

Fichier

DornF.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

164