Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs
Jørgen Bang‐Jensen, Jing Huang · Journal of Graph Theory · 2014
Abstract 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 .