Arc-Disjoint In- and Out-Branchings With the Same Root in Locally Semicomplete Digraphs

Deciding whether a digraph contains a pair of arc-disjoint in- and out-branchings rooted at a specified vertex is a well-known NP-complete problem as proved by Thomassen, see . This problem has been shown to be polynomial time solvable for semicomplete digraphs and for quasi-transitive digraphs . In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc-disjoint in- and out-branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from for semicomplete digraphs and solves an open problem from .