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

作者：Kammer Frank^*

来源：Discrete Applied Mathematics, 2015, 193: 126-138.

DOI：10.1016/j.dam.2015.04.028

• Parameterized complexity
• Linear-time data reduction
• NP-hard graph problems
• Dominator trees

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 >= k leaves (a subtree of G with vertex set V, all edges directed away from r, and >= k leaves). We present a linear-time algorithm that computes a problem kernel with O(k(6)) vertices and O(k(7)) edges for the ROOTED k-LEAF OUTBRANCHING PROBLEM. By combining the new result with a result of Daligault and Thomasse (2009), 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)).

• 出版日期2015-10-1