# zbMATH — the first resource for mathematics

A linear-time kernelization for the rooted $$k$$-leaf outbranching problem. (English) Zbl 1417.05086
Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 39th international workshop, WG 2013, Lübeck, Germany, June 19–21, 2013. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 8165, 310-320 (2013).
Summary: In the Rooted $$k$$-Leaf Outbranching Problem, a digraph $$G = (V,E)$$, a vertex $$r$$ of $$G$$, and an integer $$k$$ are given, and the goal is to find an $$r$$-rooted spanning outtree of $$G$$ with $$\geq k$$ leaves (a tree with vertex set $$V$$, all edges directed away from $$r$$, and $$\geq k$$ leaves). We present a linear-time algorithm to compute a problem kernel with $$O(k ^{6})$$ vertices and $$O(k ^{6})$$ edges for the Rooted $$k$$-Leaf Outbranching Problem. By combining the new result with a result of J. Daligault and S. Thomassé [ibid. 5917, 86–97 (2009; Zbl 1273.68162)], a kernel with a quadratic number of vertices and edges can be found on $$n$$-vertex $$m$$-edge digraphs in time $$O(n + m + k ^{14})$$.
For the entire collection see [Zbl 1276.68009].

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C05 Trees 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 68Q25 Analysis of algorithms and problem complexity
Full Text: