Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves

Details Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves

2008-10-27

arxiv.org/abs/0810.4796v2

Computer Science

Data Structures and Algorithms

Scientific paper

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}.

Affiliated with

Also associated with

No associations

Rating

Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-323899