文章基本信息

标题：Linear Kernels for Outbranching Problems in Sparse Digraphs
本地全文：下载
作者：Marthe Bonamy ; Lukasz Kowalik ; Michal Pilipczuk 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：43
页码：199-211
DOI：10.4230/LIPIcs.IPEC.2015.199
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 to determine the existence of an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems were intensively 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 H-minor-free graphs, for any fixed H, whereas k-Internal Out-Branching admits a kernel with O(k) vertices on any graph class of bounded expansion.
关键词：FPT algorithm; kernelization; outbranching; sparse graphs