×

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
PDF BibTeX XML Cite
Full Text: DOI