Making the union of two directed spanning trees strongly connected
Let D=(V,E) be a directed graph that is the union of two disjoint directed spanning trees. Can we characterize when does D have a directed spanning tree [math]T \subseteq E[/math] such that E-T is also a directed spanning tree and reversing the orientation of each edge of T results in a strongly connected digraph?
Remarks
The condition that no cut consists of a pair of oppositely directed edges is clearly necessary for the existence of a directed tree with the prescribed properties. Gil Kalai proposed that this may also be sufficient, but a counterexample was found by Maria Chudnovsky and Paul Seymour, see the figure.
More generally, they gave the following additional necessary condition:
- There is no induced cycle of even length such that the arcs of the cycle alternate in direction, each node of the cycle is cubic, and none of them is a source or sink.
An obvious sufficient condition is that D is rooted 2-arc-connected from some root r, since then it decomposes into 2 r-arborescences by Edmonds' disjoint arborescences theorem, and the reversal of one of them results in a strongly connected digraph.
