|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves | | Henning Fernau
; Fedor V. Fomin
; Daniel Lokshtanov
; Daniel Raible
; Saket Saurabh
; Yngve Villanger
; | | Date: |
27 Oct 2008 | | Abstract: | The {sc $k$-Leaf Out-Branching} problem is to find an out-branching (i.e. 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 {alonLNCS4596,AlonFGKS07fsttcs,BoDo2,KnLaRo}. In this
paper we step aside and 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 polynomial hierarchy collapses to third level
%$PH=Sigma_p^3$ by applying a recent breakthrough result by Bodlaender et al.
{BDFH08} in a non-trivial fashion. However our positive results for {sc Rooted
$k$-Leaf-Out-Branching} immediately imply that the seemingly intractable the
{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 separating {it many-to-one kernelization} from {it Turing
kernelization}. This answers affirmatively an open problem regarding "cheat
kernelization" raised in {IWPECOPEN08}. | | Source: | arXiv, 0810.4796 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER