# Independent arborescences in acyclic digraphs

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

## 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 $s\in V$ then there exist k independent spanning r-arborescences. For k=2, this was proved by Whitty in [1]. Huck found a counterexample for $k\geq 3$ [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 $v\in V$ is contained in at most two of the convex sets.

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

## References

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