Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.199
URN: urn:nbn:de:0030-drops-55839
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5583/
Bonamy, Marthe ; Kowalik, Lukasz ; Pilipczuk, Michal ; Socala, Arkadiusz
Linear Kernels for Outbranching Problems in Sparse Digraphs
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{bonamy_et_al:LIPIcs:2015:5583,
author = {Marthe Bonamy and Lukasz Kowalik and Michal Pilipczuk and Arkadiusz Socala},
title = {{Linear Kernels for Outbranching Problems in Sparse Digraphs}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {199--211},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5583},
URN = {urn:nbn:de:0030-drops-55839},
doi = {10.4230/LIPIcs.IPEC.2015.199},
annote = {Keywords: FPT algorithm, kernelization, outbranching, sparse graphs}
}
| Keywords: | FPT algorithm, kernelization, outbranching, sparse graphs | |
| Seminar: | 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 19.11.2015 |
