FPT Algorithms and Kernels for the Directed k-Leaf Problem

Jean Daligault 1 Gregory Gutin 2 Anders Yeo 2 Eunjung Kim 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A subgraph $T$ of a digraph $D$ is an {\em out-branching} if $T$ is an oriented spanning tree with only one vertex of in-degree zero (called the {\em root}). The vertices of $T$ of out-degree zero are {\em leaves}. In the {\sc Directed Max Leaf} Problem, we wish to find the maximum number of leaves in an out-branching of a given digraph $D$ (or, to report that $D$ has no out-branching). In the {\sc Directed $k$-Leaf} Problem, we are given a digraph $D$ and an integral parameter $k$, and we are to decide whether $D$ has an out-branching with at least $k$ leaves. Recently, Kneis et al. (2008) obtained an algorithm for {\sc Directed $k$-Leaf} of running time $4^{k}\cdot n^{O(1)}$. We describe a new algorithm for {\sc Directed $k$-Leaf} of running time $3.72^{k}\cdot n^{O(1)}$. This algorithms leads to an $O(1.9973^n)$-time algorithm for solving {\sc Directed Max Leaf} on a digraph of order $n.$ The latter algorithm is the first algorithm of running time $O(\gamma^n)$ for {\sc Directed Max Leaf}, where $\gamma<2.$ In the {\sc Rooted Directed $k$-Leaf} Problem, apart from $D$ and $k$, we are given a vertex $r$ of $D$ and we are to decide whether $D$ has an out-branching rooted at $r$ with at least $k$ leaves. Very recently, Fernau et al. (2008) found an $O(k^3)$-size kernel for {\sc Rooted Directed $k$-Leaf}. In this paper, we obtain an $O(k)$ kernel for {\sc Rooted Directed $k$-Leaf} restricted to acyclic digraphs.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2010, 76 (2), pp.144-152. 〈10.1016/j.jcss.2009.06.005〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432901
Contributeur : Jean Daligault <>
Soumis le : mardi 17 novembre 2009 - 15:50:36
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : jeudi 17 juin 2010 - 20:42:57

Fichier

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

Identifiants

Collections

Citation

Jean Daligault, Gregory Gutin, Anders Yeo, Eunjung Kim. FPT Algorithms and Kernels for the Directed k-Leaf Problem. Journal of Computer and System Sciences, Elsevier, 2010, 76 (2), pp.144-152. 〈10.1016/j.jcss.2009.06.005〉. 〈lirmm-00432901〉

Partager

Métriques

Consultations de la notice

230

Téléchargements de fichiers

111