# 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 ^{[1]}. Huck found a counterexample for [math]k\geq 3[/math] ^{[2]}, and also showed that the conjecture holds for acyclic digraphs ^{[3]}.

Frank, Fujushige, Kamiyama, and Katoh ^{[4]} 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

## References

- ↑ R.W. Whitty,
*Vertex-disjoint paths and edge-disjoint branchings in directed graphs*, Journal of Graph Theory, 11, 349-358 (1987), DOI link - ↑ A. Huck,
*Disproof of a conjecture about independent branchings in k-connected directed graphs*, Journal of Graph Theory, 20, 235-239 (1995), DOI link - ↑ A. Huck,
*Independent branchings in acyclic digraphs*, Discrete Mathematics, 199, 245-249 (1999), DOI link - ↑ A. Frank, S. Fujishige, N. Kamiyama, N. Katoh,
*Independent arborescences in directed graphs*, DOI link, author link