Arc-disjoint out-branchings and in-branchings in semicomplete digraphs

J. Bang-Jensen*, Y. Wang

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

An out-branching (Formula presented.) (in-branching (Formula presented.)) in a digraph (Formula presented.) is a connected spanning subdigraph of (Formula presented.) in which every vertex except the vertex (Formula presented.), called the root, has in-degree (out-degree) one. It is well known that there exists a polynomial algorithm for deciding whether a given digraph has (Formula presented.) arc-disjoint out-branchings with prescribed roots ((Formula presented.) is part of the input). In sharp contrast to this, it is already NP-complete to decide if a digraph has one out-branching which is arc-disjoint from some in-branching. A digraph is semicomplete if it has no pair of nonadjacent vertices. A tournament is a semicomplete digraph without directed cycles of length 2. In this paper we give a complete classification of semicomplete digraphs that have an out-branching (Formula presented.) which is arc-disjoint from some in-branching (Formula presented.) where (Formula presented.) are prescribed vertices of (Formula presented.). Our characterization, which is surprisingly simple, generalizes a complicated characterization for tournaments from 1991 by the first author and our proof implies the existence of a polynomial algorithm for checking whether a given semicomplete digraph has such a pair of branchings for prescribed vertices (Formula presented.) and construct a solution if one exists. This confirms a conjecture of Bang-Jensen for the case of semicomplete digraphs.

Original languageEnglish
JournalJournal of Graph Theory
ISSN0364-9024
DOIs
Publication statusE-pub ahead of print - 3. Jan 2024

Keywords

  • arc-disjoint subdigraphs
  • in-branchings
  • out-branchings
  • polynomial algorithm
  • semicomplete digraph

Fingerprint

Dive into the research topics of 'Arc-disjoint out-branchings and in-branchings in semicomplete digraphs'. Together they form a unique fingerprint.

Cite this