A linear-time kernelization for the Rooted kk-Leaf Outbranching Problem

In the Rooted   kk-Leaf Outbranching Problem, a digraph G=(V,E)G=(V,E), a vertex  rr of  GG, and an integer kk are given, and the goal is to find an rr-rooted spanning outtree of  GG with ≥k≥k leaves (a subtree of  GG with vertex set  VV, all edges directed away from  rr, and ≥k≥k leaves). We present a linear-time algorithm that computes a problem kernel with O(k6)O(k6) vertices and O(k7)O(k7) edges for the Rooted   kk-Leaf Outbranching Problem. By combining the new result with a result of Daligault and Thomassé (2009), a kernel with a quadratic number of vertices and edges can be found on nn-vertex mm-edge digraphs in time O(n+m+k14)O(n+m+k14).