License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.58
URN: urn:nbn:de:0030-drops-73788
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7378/
Go to the corresponding LIPIcs Volume Portal

Gutin, Gregory ; Reidl, Felix ; Wahlström, Magnus

k-Distinct In- and Out-Branchings in Digraphs

pdf-format:
LIPIcs-ICALP-2017-58.pdf (0.6 MB)

Abstract

An out-branching and an in-branching of a digraph D are called k-distinct if each of them has k arcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that the problem of deciding whether a strongly connected digraph D has k-distinct out-branching and in-branching is fixed-parameter tractable (FPT) when parameterized by k. They asked whether the problem remains FPT when extended to arbitrary digraphs. Bang-Jensen and Yeo (2008) asked whether the same problem is FPT when the out-branching and in-branching have the same root.

By linking the two problems with the problem of whether a digraph has an out-branching with at least k leaves (a leaf is a vertex of out-degree zero), we first solve the problem of Bang-Jensen and Yeo (2008). We then develop a new digraph decomposition called the rooted cut decomposition and using it we prove that the problem of Bang-Jensen et al. (2016) is FPT for all digraphs. We believe that the rooted cut decomposition will be useful for obtaining other results on digraphs.

BibTeX - Entry

@InProceedings{gutin_et_al:LIPIcs:2017:7378,
  author =	{Gregory Gutin and Felix Reidl and Magnus Wahlstr{\"o}m},
  title =	{{k-Distinct In- and Out-Branchings in Digraphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7378},
  URN =		{urn:nbn:de:0030-drops-73788},
  doi =		{10.4230/LIPIcs.ICALP.2017.58},
  annote =	{Keywords: Digraphs, Branchings, Decompositions, FPT algorithms}
}

Keywords: Digraphs, Branchings, Decompositions, FPT algorithms
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI