DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2009.1843

Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

Authors: Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, and Yngve Villanger

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

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.

Cite as

Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, and Yngve Villanger. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{fernau_et_al:LIPIcs.STACS.2009.1843,
  author =	{Fernau, Henning and Fomin, Fedor V. and Lokshtanov, Daniel and Raible, Daniel and Saurabh, Saket and Villanger, Yngve},
  title =	{{Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{421--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1843},
  URN =		{urn:nbn:de:0030-drops-18437},
  doi =		{10.4230/LIPIcs.STACS.2009.1843},
  annote =	{Keywords: Parameterized algorithms, Kernelization, Out-branching, Max-leaf, Lower bounds}
}

Document

DOI: 10.4230/DagSemProc.07281.6

Exact Elimination of Cycles in Graphs

Authors: Daniel Raible and Henning Fernau

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract

One of the standard basic steps in drawing hierarchical graphs is to invert some arcs of the given graph to make the graph acyclic. We discuss exact and parameterized algorithms for this problem. In particular we examine a graph class called $(1,n)$-graphs, which contains cubic graphs. For both exact and parameterized algorithms we use a non-standard measure approach for the analysis. The analysis of the parameterized algorithm is of special interest, as it is not an amortized analysis modelled by 'finite states' but rather a 'top-down' amortized analysis. For $(1,n)$-graphs we achieve a running time of $Oh^*(1.1871^m)$ and $Oh^*(1.212^k)$, for cubic graphs $Oh^*(1.1798^m)$ and $Oh^*(1.201^k)$, respectively. As a by-product the trivial bound of $2^n$ for {sc Feedback Vertex Set} on planar directed graphs is broken.

Cite as

Daniel Raible and Henning Fernau. Exact Elimination of Cycles in Graphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{raible_et_al:DagSemProc.07281.6,
  author =	{Raible, Daniel and Fernau, Henning},
  title =	{{Exact Elimination of Cycles in Graphs}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.6},
  URN =		{urn:nbn:de:0030-drops-12353},
  doi =		{10.4230/DagSemProc.07281.6},
  annote =	{Keywords: Maximum Acyclic Subgraph, Feedback Arc Set, Amortized Analysis, Exact exponential algorthms}
}

Search Results

Documents authored by Raible, Daniel

Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

Abstract

Cite as

Exact Elimination of Cycles in Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message