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].

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: DOI