A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph

Suppose that we are given a directed graph D=(V,A) with specified vertices r1,r2∈V. In this paper, we consider the problem of discerning the existence of a pair of arc-disjoint spanning in-arborescence rooted at r1 and out-arborescence rooted at r2, and finding such arborescences if they exist. It is known (Bang-Jensen (1991) [1], ) that this problem is NP-complete even if r1=r2. As a special case, it is only known (Bang-Jensen (1991) [1]) that this problem in a tournament can be solved in polynomial time. In this paper, we give a linear-time algorithm for this problem in a directed acyclic graph. We also consider an extension of our problem to the case where we have multiple roots for in-arborescences and out-arborescences, respectively.