k-Distinct In- and Out-Branchings in Digraphs. / Gutin, Gregory; Reidl, Felix; Wahlstrom, Magnus.

44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Dagstuhl, 2017. p. 1-13 (Leibniz International Proceedings in Informatics ; Vol. 80).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Standard

k-Distinct In- and Out-Branchings in Digraphs. / Gutin, Gregory; Reidl, Felix; Wahlstrom, Magnus.

44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Dagstuhl, 2017. p. 1-13 (Leibniz International Proceedings in Informatics ; Vol. 80).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Gutin, G, Reidl, F & Wahlstrom, M 2017, k-Distinct In- and Out-Branchings in Digraphs. in 44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Leibniz International Proceedings in Informatics , vol. 80, Dagstuhl, pp. 1-13. https://doi.org/10.4230/LIPIcs.ICALP.2017.58

APA

Gutin, G., Reidl, F., & Wahlstrom, M. (2017). k-Distinct In- and Out-Branchings in Digraphs. In 44th International Colloquium on Automata, Languages, and Programming: ICALP 2017 (pp. 1-13). (Leibniz International Proceedings in Informatics ; Vol. 80). Dagstuhl. https://doi.org/10.4230/LIPIcs.ICALP.2017.58

Vancouver

Gutin G, Reidl F, Wahlstrom M. k-Distinct In- and Out-Branchings in Digraphs. In 44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Dagstuhl. 2017. p. 1-13. (Leibniz International Proceedings in Informatics ). https://doi.org/10.4230/LIPIcs.ICALP.2017.58

Author

Gutin, Gregory ; Reidl, Felix ; Wahlstrom, Magnus. / k-Distinct In- and Out-Branchings in Digraphs. 44th International Colloquium on Automata, Languages, and Programming: ICALP 2017. Dagstuhl, 2017. pp. 1-13 (Leibniz International Proceedings in Informatics ).

BibTeX

@inproceedings{6d73db0cefdc4d9982333cd52c72fcda,
title = "k-Distinct In- and Out-Branchings in Digraphs",
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.",
author = "Gregory Gutin and Felix Reidl and Magnus Wahlstrom",
year = "2017",
doi = "10.4230/LIPIcs.ICALP.2017.58",
language = "English",
isbn = "978-3-95977-041-5",
series = "Leibniz International Proceedings in Informatics",
publisher = "Dagstuhl",
pages = "1--13",
booktitle = "44th International Colloquium on Automata, Languages, and Programming",

}

RIS

TY - GEN

T1 - k-Distinct In- and Out-Branchings in Digraphs

AU - Gutin, Gregory

AU - Reidl, Felix

AU - Wahlstrom, Magnus

PY - 2017

Y1 - 2017

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

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

U2 - 10.4230/LIPIcs.ICALP.2017.58

DO - 10.4230/LIPIcs.ICALP.2017.58

M3 - Conference contribution

SN - 978-3-95977-041-5

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 13

BT - 44th International Colloquium on Automata, Languages, and Programming

PB - Dagstuhl

ER -