Linear Kernels for Outbranching Problems in Sparse Digraphs

In the $k$ ‐Leaf Out‐Branching and $k$ ‐Internal Out‐Branching problems we are given a directed graph D with a designated root r and a nonnegative integer k. The question is whether there exists an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems have been studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with $O(k^2)$ vertices are known on general graphs. In this work we show that $k$ ‐Leaf Out‐Branching admits a kernel with O(k) vertices on $\mathcal{H}$ ‐minor‐free graphs, for any fixed family of graphs $\mathcal{H}$ , whereas $k$ ‐Internal Out‐Branching admits a kernel with O(k) vertices on any graph class of bounded expansion.