Making the union of two directed spanning trees strongly connected

Definitions and mathematical statement

Let $D=(V,E)$ be a finite digraph whose arc set can be partitioned into two directed spanning trees. "Disjoint" here must mean arc-disjoint, since both trees span $V$. The source asks for a characterization of when there exists a possibly different partition \[ E=T\mathbin{\dot\cup}(E\setminus T) \] into directed spanning trees such that reversing precisely the arcs of $T$ gives a strongly connected digraph $D_T$. Reversal preserves each arc's identity and exchanges its head and tail; all other arcs retain their orientations. Strong connectivity means a directed path exists from every vertex to every other vertex.

For $S\subset V$, let $\delta_D^+(S)$ and $\delta_D^-(S)$ be arcs leaving and entering $S$. The requested feasibility property can be stated explicitly as existence of a tree partition satisfying \[ |\delta_D^+(S)\setminus T|+|\delta_D^-(S)\cap T|\ge1 \qquad(\varnothing\ne S\subsetneq V), \] which is exactly the no-empty-directed-cut condition for $D_T$. This merely specifies the property to characterize; it is not offered as the sought structural characterization or algorithm.

A directed spanning tree may mean an arbitrary orientation of an undirected spanning tree, or a rooted in-/out-arborescence with orientation constraints. The excerpt gives no definition, roots, or direction convention. Under the former reading each underlying edge set is a spanning tree; under an arborescence reading additional indegree/outdegree and root constraints must be retained. Loops and parallel-arc conventions are also unspecified. No polynomial-time or min--max characterization requirement is supplied. The research summary reports OPEN-TRIAGE, saying no correct characterization or resolving citation was verified.

Short English statement

Characterize when a digraph decomposable into two spanning trees has such a decomposition for which reversing one tree makes the whole digraph strongly connected. The meaning of directed tree and the intended characterization format are unspecified.

Sources

• Local UnsolvedMath registry, permanent ID $3000050$, exact source code catalogue entry, "Making the union of two directed spanning trees strongly connected."
• Egres Open, List of open problems, page of the same title; supplied index https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems. HTML extraction; recorded access 2026-07-29.
• No authoritative research-paper citation or definition of the directed-tree convention is supplied; the research summary reports only an unverified no-resolution search.