Independent arborescences in acyclic digraphs

Definitions and mathematical statement

Let $D=(V,A)$ be a finite acyclic digraph. Choose roots $r_1,\ldots,r_k$, which need not be distinct, and convex sets $U_i\subseteq V$ with $r_i\in U_i$. A set is convex here if every directed path whose endpoints lie in that set has all its vertices in the set. An $r_i$-arborescence on $U_i$ is an outward-directed tree spanning exactly $U_i$.

For a vertex $v$, put $I(v)=\{i:v\in U_i\}$. Paths $P_i$ from $r_i$ to $v$, indexed by $I(v)$, are openly disjoint when, for $i\ne j$, \[ A(P_i)\cap A(P_j)=\varnothing,\qquad V(P_i)\cap V(P_j)=\{v\}\cup(\{r_i\}\cap\{r_j\}). \] A length-zero path is allowed when $r_i=v$.

Is the following condition sufficient for independent arborescences $T_i$ on the prescribed $U_i$: for each $v$ there exists such an openly disjoint family of $r_i$--$v$ paths? Independence requires that the unique $r_i$--$v$ paths in the chosen $T_i$ satisfy the displayed conditions for every $v$. Necessity is immediate, so sufficiency gives the requested equivalence.

The local path families may depend on $v$; the conclusion must realize all of them compatibly through one fixed family of trees. Convexity ensures that paths with endpoints $r_i,v\in U_i$ remain in $U_i$. No bound is imposed on the number of sets containing a vertex.

Short English statement

For convex vertex sets in an acyclic digraph, do local disjoint-path conditions guarantee a compatible family of independent rooted trees?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000044 (AMR-029-0044), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Independent arborescences in acyclic digraphs. Original source indexed by AMR-029-0044. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Independent arborescences in acyclic digraphs. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Independent_arborescences_in_acyclic_digraphs.
• S4 A. Frank and collaborators, Independent arborescences in directed graphs, including convex-set definitions and the bounded-overlap special case. https://andrasfrank.web.elte.hu/cikkek/FrankJ63.pdf.