Linear Kernels for Outbranching Problems in Sparse Digraphs
Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała · Algorithmica · 2016
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.