Arc-disjoint spanning sub(di)graphs in digraphs

We prove that a number of natural problems concerning the existence of arc-disjoint directed and “undirected” (spanning) subdigraphs in a digraph are N P -complete. Among these are the following of which the first settles an open problem due to Thomassé (see e. g. Bang-Jensen and Gutin (2009) [1, Problem 9. 9. 7] and Bang-Jensen and Kriesell (2009) [5, 4]) and the second settles an open problem posed in Bang-Jensen and Kriesell (2009) [5]. • Given a directed graph D and a vertex s of D; does D contain an out-branching B s + rooted at s such that the digraph remains connected (in the underlying sense) after removing all arcs of B s +? • Given a strongly connected directed graph D; does D contain a spanning strong subdigraph D ′ such that the digraph remains connected (in the underlying sense) after removing all arcs of D ′?

Authors

• Jørgen Bang-Jensen
• Anders Yeo

Keywords

• Paths and cycles
• Branchings
• Spanning trees
• NP-completeness
• Arc-disjoint subdigraphs