• Calendar

April 8, Tuesday
12:00 – 14:00

An out-tree T in a digraph D is subgraph of D which is an orientation of a tree that has only one vertex of in-degree 0 (root). A vertex of T is a leaf if it has out-degree 0. A spanning out-tree is called an out-branching. We overview the following recent results:

• the problem of finding an out-branching with minimum number of leaves is polynomial-time solvable for acyclic digraphs (it is NP-hard for general digraphs) [Gutin, Kim, Razgon, 2008]
• the problem of finding an out-branching with at least k non-leaves is fixed-parameter tractable (FPT) [Gutin, Kim, Razgon, 2008]
• the problem of finding an out-tree with at least k leaves is FPT [Alon, Fomin, Gutin, Krivelevich, Saurabh, 2007]
• the problem of finding an out-branching with at least k leaves is FPT [Bonsma and Dorn, 2007]