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

Abstract

Let D be a finite acyclic digraph with root-nodes r_1, ..., r_k, not necessarily distinct, and convex node sets U_1, ..., U_k with r_i ∈ 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 ∈ 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. Unrefereed preprint released for independent mathematical scrutiny. Publication on Zenodo does not constitute peer review. AI-assisted tools supported research, computation, proof development, and manuscript preparation. The author remains responsible for all claims and the final text. Corpus identifier: AMR-029-0044 (EGRES Open, Independent arborescences in acyclic digraphs; Question 2 of Frank-Fujishige-Kamiyama-Katoh, Discrete Math. 313 (2013), for acyclic digraphs).