Paper Info
Title
Arc-Disjoint Paths and Trees in 2-Regular Digraphs
Abstract
An out-branching (in-branching) Bs+(Bs−) in a digraph D is a connected spanning subdigraph of D in which every vertex x≠s has precisely one arc entering (leaving) it and s has no arcs entering (leaving) it. We settle the complexity of the following two problems: •Given a 2-regular digraph D, decide whether it contains two arc-disjoint branchings Bu+, Bv−.•Given a 2-regular digraph D, decide whether it contains an out-branching Bu+ such that D 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 D contains two arc-disjoint out-branchings.
Year
DOI
Venue
2012
10.1016/j.dam.2013.04.018
Discrete Applied Mathematics
Keywords
DocType
Volume
Spanning tree,Out-branching,In-branching,Connected spanning subgraph,Mixed problem,Polynomial time,NP,2-regular digraph
Journal
161
Issue
ISSN
Citations 
16
0166-218X
3
PageRank 
References 
Authors
0.43
7
2
Name
Order
Citations
PageRank
Jørgen Bang-Jensen157368.96
Sven Simonsen292.09