# Union of a spanning arborescence and a directed spanning tree

Find a good characterization of directed graphs having two disjoint directed spanning trees such that one of the spanning trees is an arborescence rooted at a given node.

It was shown by Jørgen Bang-Jensen and Anders Yeo ^{[1]} that the problem is NP-complete. They also showed that it is NP-complete to decide if a strongly connected digraph contains a spanning strong subdigraph so that removing these arcs the rest stays connected.

## Remarks

This problem was proposed by Stéphan Thomassé. As a generalization, one may ask for *k* disjoint directed spanning trees, of which *l* are arborescences rooted at a given node.

Note that there are well-known characterizations of graphs that have *k* edge-disjoint spanning trees (Tutte's disjoint tree theorem ^{[2]}), as well as of digraphs that have *k* edge-disjoint spanning arborescences rooted at a given node (Edmonds' disjoint arborescences theorem ^{[3]}).

## Related questions

Kriesell and Bang-Jensen ^{[4]} proved that for a strongly connected digraph *D* it can be decided in polynomial time whether the underlying undirected graph contains two node-disjoint cycles, one of which is a directed cycle in *D*. However, the same problem is NP-complete if we drop the requirement of strong connectivity ^{[5]}.

Another related problem is the existence of Disjoint spanning in- and out-arborescences.

## References

- ↑ J. Bang-Jensen, A. Yeo,
*Arc-disjoint spanning sub(di)graphs in Digraphs*, DOI link, author link. - ↑ W.T. Tutte,
*On the problem of decomposing a graph into*n*connected factors*, J. London Math. Soc. 36 (1961) 221-230. DOI link - ↑ J. Edmonds,
*Edge-disjoint branchings*, in: B. Rustin, ed., Combinatorial Algorithms (Acad. Press, New York, 1973) 91-96. - ↑ M. Kriesell, J. Bang-Jensen,
*On the problem of finding disjoint cycles and dicycles in a digraph*, IMADA Preprint PP-2009-12 - ↑ J. Bang-Jensen, M. Kriesell, A. Maddaloni, S. Simonsen,
*Vertex-disjoint directed and undirected cycles in general digraphs*, arXiv link.