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

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.