Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs.

An out‐branching Bu+ ${B}_{u}^{+}$ (in‐branching Bu− ${B}_{u}^{-}$) in a digraph D $D$ is a connected spanning subdigraph of D $D$ in which every vertex except the vertex u $u$, 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 k $k$ arc‐disjoint out‐branchings with prescribed roots (k $k$ 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 Bu+ ${B}_{u}^{+}$ which is arc‐disjoint from some in‐branching Bv− ${B}_{v}^{-}$ where u,v $u,v$ are prescribed vertices of D $D$. 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 u,v $u,v$ and construct a solution if one exists. This confirms a conjecture of Bang‐Jensen for the case of semicomplete digraphs. [ABSTRACT FROM AUTHOR]