skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Kernel(s) for problems with no kernel: On out-trees with many leaves

Binkele-Raible, Daniel ; Fernau, Henning ; Fomin, Fedor ; Lokshtanov, Daniel ; Saurabh, Saket ; Villanger, Yngve

ACM transactions on algorithms, 2012-09, Vol.8 (4), p.1-19 [Periódico revisado por pares]

ACM

Texto completo disponível

Citações Citado por
  • Título:
    Kernel(s) for problems with no kernel: On out-trees with many leaves
  • Autor: Binkele-Raible, Daniel ; Fernau, Henning ; Fomin, Fedor ; Lokshtanov, Daniel ; Saurabh, Saket ; Villanger, Yngve
  • Assuntos: Algorithms ; Kernelization ; lower bounds ; max-leaf spanning tree ; out-branching ; parameterized algorithms
  • É parte de: ACM transactions on algorithms, 2012-09, Vol.8 (4), p.1-19
  • Notas: ObjectType-Article-2
    SourceType-Scholarly Journals-1
    ObjectType-Feature-1
    content type line 23
  • Descrição: The 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 k -Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted k -Leaf-Out-Branching, a variant of k -Leaf-Out-Branching where the root of the tree searched for is also a part of the input. Our kernel with O ( k 3 ) vertices is obtained using extremal combinatorics. For the k -Leaf-Out-Branching problem, we show that no polynomial-sized kernel is possible unless coNP is in NP/poly . However, our positive results for Rooted k -Leaf-Out-Branching immediately imply that the seemingly intractable k -Leaf-Out-Branching problem admits a data reduction to n independent polynomial-sized kernels. These two results, tractability and intractability side by side, are the first ones separating Karp kernelization from Turing kernelization . This answers affirmatively an open problem regarding "cheat kernelization" raised by Mike Fellows and Jiong Guo independently.
  • Editor: ACM
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.