Arc-disjoint paths and trees in 2-regular digraphs

An out-branching (in-branching) Bs+(Bs−) in a digraph DD is a connected spanning subdigraph of DD in which every vertex x≠sx≠s has precisely one arc entering (leaving) it and ss has no arcs entering (leaving) it. We settle the complexity of the following two problems: •Given a 2-regular digraph DD, decide whether it contains two arc-disjoint branchings Bu+, Bv−.•Given a 2-regular digraph DD, decide whether it contains an out-branching Bu+ such that DD remains connected after removing the arcs of Bu+. Both problems are NP-complete for general digraphs (Bang-Jensen (1991) [1], Bang-Jensen and Yeo (2012) [7]). We prove that the first problem remains NP-complete for 2-regular digraphs, whereas the second problem turns out to be polynomial when we do not prescribe the root in advance. The complexity when the root is prescribed in advance is still open. We also prove that, for 2-regular digraphs, the second problem is in fact equivalent to deciding whether DD contains two arc-disjoint out-branchings.