Combinatorics Seminar
When: Sunday, April 13, 10am
Where: Schreiber 309
Speaker: Gregory Gutin, Royal Holloway, University of London
Title: Extremal out-branchings and out-trees in digraphs
Abstract:
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:
(a) 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]
(b) the problem of finding an out-branching with at least k
non-leaves is fixed-parameter tractable (FPT) [Gutin, Kim, Razgon,
2008]
(c) the problem of finding an out-tree with at least k leaves is FPT
[Alon, Fomin, Gutin, Krivelevich, Saurabh, 2007]
(d) the problem of finding an out-branching with at least k leaves
is FPT [Bonsma and Dorn, 2007].