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 NPcomplete problem (as proved by Thomassen, see [2]). This problem has been shown to be polynomial time solvable for semicomplete digraphs [2] and for quasi-transitive digraphs [6]. 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 [2] for semicomplete digraphs and solves an open problem from [4].