2026-07-22T06:26:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5583 2024-03-06T10:36:36Z ddc:004 open_access

Linear Kernels for Outbranching Problems in Sparse Digraphs Bonamy, Marthe Kowalik, Lukasz Pilipczuk, Michal Socala, Arkadiusz FPT algorithm kernelization outbranching sparse graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marthe Bonamy and Lukasz Kowalik and Michal Pilipczuk and Arkadiusz Socala 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.199 urn:nbn:de:0030-drops-55839 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.199 eng https://creativecommons.org/licenses/by/3.0/legalcode