Arc-disjoint out- and in-branchings in compositions of digraphs (Q6568855)

An out-branching \(B^+_u\) (in-branching \(B^-_u\) ) in a digraph \(D\) is a connected spanning subdigraph of \(D\) in which every vertex except the vertex \(u\), called the root, has in-degree (out-degree) one. A good \((u, v)\)-pair in \(D\) is a pair of branchings \(B^+_u\), \(B^-_v\) which have no arc in common.\N\NA digraph is semicomplete if it has no pair of non-adjacent vertices. A semicomplete composition is any digraph \(D\) which is obtained from a semicomplete digraph \(S\) by substituting an arbitrary digraph \(H_x\) for each vertex \(x\) of \(S\). The authors completely solve the problem of characterizing semicomplete compositions that have a good \((u, v)\)-pair for given vertices \(u\), \(v\). As a consequence, they show that there is a polynomial algorithm for deciding whether a given quasitransitive digraph \(D\) has a good \((u, v)\)-pair for given vertices \(u\), \(v\) of \(D\).