Independent arborescences in acyclic digraphs

Let D=(V,A) be an acyclic digraph with designated root-nodes [math]r_1,...,r_k\in V[/math]. Let [math]U_1,...,U_k[/math] be convex node sets with [math]r_i\in U_i[/math]. Is it true that there exist independent [math]r_i[/math]-arborescences [math]F_i[/math] with [math]V(F_i)=U_i[/math] if and only if there exist openly node-disjoint [math]r_i-v[/math] paths [math]P_i[/math] ([math]v\in U_i[/math]) for each [math]v\in V[/math]? (We call the [math]r_i-v[/math] and [math]r_j-v[/math] paths [math]P_i[/math] and [math]P_j[/math] openly node-disjoint if they are edge-disjoint and [math]V(P_i)\cap V(P_j)=\{v\}\cup(\{r_i\}\cap\{r_j\})[/math].)

Remarks

The problem was proposed by S. Fujishige, N. Kamiyama and N. Katoh. As a node-disjoint analogue of Edmonds' disjoint arborescences theorem, Frank conjectured that if there exist k internally node-disjoint r-s paths in an arbitrary digraph D for each [math]s\in V[/math] then there exist k independent spanning r-arborescences. For k=2, this was proved by Whitty in . Huck found a counterexample for [math]k\geq 3[/math] , and also showed that the conjecture holds for acyclic digraphs .

Frank, Fujushige, Kamiyama, and Katoh verified the above conjecture for the following two cases:

• the r_i's are identical,
• each node [math]v\in V[/math] is contained in at most two of the convex sets.

They also proved that if both of the above (the second for [math]v\in V-r[/math]) are satisfied, then the conjecture is true even for not necessarily acyclic digraphs.

Related open problems

Independent trees