dc.contributor.author | Fernau, Henning | |
dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Lokshtanov, Daniel | |
dc.contributor.author | Raible, Daniel | |
dc.contributor.author | Saurabh, Saket | |
dc.contributor.author | Villanger, Yngve | |
dc.date.accessioned | 2016-05-30T10:47:12Z | |
dc.date.available | 2016-05-30T10:47:12Z | |
dc.date.issued | 2009 | |
dc.identifier.isbn | 978-3-939897-09-5 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/1956/12035 | |
dc.description.abstract | The {\sc \(k\)-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least \(k\) leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc \(k\)-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted \(k\)-Leaf-Out-Branching}, a variant of {\sc \(k\)-Leaf-Out-Branching} where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the {\sc \(k\)-Leaf-Out-Branching} problem, we show that no polynomial kernel is possible unless the polynomial hierarchy collapses to third level by applying a recent breakthrough result by Bodlaender et al. (ICALP 2008) in a non-trivial fashion. However, our positive results for {\sc Rooted \(k\)-Leaf-Out-Branching} immediately imply that the seemingly intractable {\sc \(k\)-Leaf-Out-Branching} problem admits a data reduction to \(n\) independent \(O(k^3)\) kernels. These two results, tractability and intractability side by side, are the first ones separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding ``cheat kernelization'' raised by Mike Fellows and Jiong Guo independently. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Attribution CC BY-ND 3.0 | eng |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/3.0/ | eng |
dc.subject | Parameterized algorithms | eng |
dc.subject | Kernelization | eng |
dc.subject | Out-branching | eng |
dc.subject | Max-leaf | eng |
dc.subject | Lower bounds | eng |
dc.title | Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2016-04-07T06:45:22Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible, S. Saurabh, and Y. Villanger | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.stacs.2009.1843 | |
dc.identifier.cristin | 343066 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.source.pagenumber | 421-432 | |
dc.subject.nsi | VDP::Matematikk og naturvitenskap: 400::Matematikk: 410 | |
dc.subject.nsi | VDP::Mathematics and natural scienses: 400::Mathematics: 410 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics 2009, 3:421-432 | |
dc.source.volume | 3 | |