English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching (i.e. arooted oriented spanning tree) with at least $k$ leaves in a given digraph. Theproblem has recently received much attention from the viewpoint ofparameterized algorithms {alonLNCS4596,AlonFGKS07fsttcs,BoDo2,KnLaRo}. In thispaper we step aside and take a kernelization based approach to the {\sc$k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\scRooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} wherethe root of the tree searched for is also a part of the input. Our kernel hascubic size and is obtained using extremal combinatorics.  For the {\sc $k$-Leaf-Out-Branching} problem we show that no polynomialkernel 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 byside, are the first separating {\it many-to-one kernelization} from {\it Turingkernelization}. This answers affirmatively an open problem regarding "cheatkernelization" raised in {IWPECOPEN08}.

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