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.
