Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: An FPT Algorithm for Directed Spanning k-Leaf   An out-branching of a directed graph is a rooted spanning tree with all arcs
directed outwards from the root. We consider the problem of deciding whether a
given directed graph D has an out-branching with at least k leaves (Directed
Spanning k-Leaf). We prove that this problem is fixed parameter tractable, when
k is chosen as the parameter. Previously this was only known for restricted
classes of directed graphs.
  The main new ingredient in our approach is a lemma that shows that given a
locally optimal out-branching of a directed graph in which every arc is part of
at least one out-branching, either an out-branching with at least k leaves
exists, or a path decomposition with width O(k^3) can be found. This enables a
dynamic programming based algorithm of running time 2^{O(k^3 \log k)} n^{O(1)},
where n=|V(D)|.

33
The categories of this paper are: plasm-ph
12
The categories of this paper are: nucl-th
23
The categories of this paper are: solv-int
20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
2
The categories of this paper are: math
8
The categories of this paper are: hep-ex
29
The categories of this paper are: funct-an
4
The categories of this paper are: cond-mat
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
19
The categories of this paper are: eess
10
The categories of this paper are: q-bio
11
The categories of this paper are: hep-lat
17
The categories of this paper are: q-fin
7
The categories of this paper are: hep-th