Independent Arborescences in Acyclic Digraphs: The Path Condition Suffices for All Roots and All Convex Sets

Let \(D\) be a finite acyclic digraph with root-nodes \(r_1,\dots,r_k\), not necessarily distinct, and convex node sets \(U_1,\dots,U_k\) with \(r_i\in U_i\). The EGRES Open collection lists as open the question, proposed by S. Fujishige, N. Kamiyama and N. Katoh, whether there are independent \(r_i\)-arborescences \(F_i\) with \(V(F_i)=U_i\) if and only if for every vertex \(v\) there are pairwise openly node-disjoint paths from \(r_i\) to \(v\), one for each \(i\) with \(v\in U_i\). This is Question 2 of Frank, Fujishige, Kamiyama and Katoh (Discrete Math. 313 (2013)) restricted to acyclic digraphs; their paper proves three cases and does not treat the general acyclic case. We prove that the answer is yes, for all finite acyclic digraphs (parallel arcs allowed), all roots and all convex sets, in the reading of the 2013 paper: the open node-disjointness of the EGRES problem page is used for the paths and for the root paths of the arborescences. With different notions on the two sides the equivalence fails for trivial reasons. Both conditions are equivalent to a local one, a bipartite matching problem at every vertex. The proof assigns to every vertex a real vector, chosen along a topological order by a minimum-cost assignment of the entering arcs and a strictly feasible dual solution; for two sets this is the classical ordering argument. We make no claim that the method is new: it was not found in the texts we read, among them Huck's paper of 1999 on spanning arborescences, whose proof removes one arborescence at a time; the dissertation of A. Hoyer (2019) was not accessible to us beyond its abstract. The equivalence is also proved for the weaker disjointness of Kamiyama's survey, which gives the same conditions on simple digraphs. The statement is false without convexity, and for digraphs with directed cycles (Huck 1995, known to us through the 2013 paper). No answer to the question was found in the literature accessible to us; a search that finds nothing is not a proof of novelty. Computations, among them one that covers all instances with at most seven vertices and three sets, are tests and no part of the proof. This is an unrefereed note.