Capacitated packing of k-arborescences

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph, with specified root $r$ and positive integers $k,\ell$. Parallel arcs, when present, are distinct members of $A$. A spanning out-arborescence rooted at $r$ is a directed spanning tree in which $r$ has indegree zero, each other vertex has indegree one, and every vertex is reachable from $r$.

Give each arc an integer capacity $c(a)$ with $0\le c(a)\le\ell$. A capacity-respecting packing of arborescences is a list in which any fixed arc $a$ is used at most $c(a)$ times. Suppose there is such a packing of $k\ell$ spanning out-arborescences rooted at $r$.

Must there exist $\ell$ subgraphs $F_1,\ldots,F_\ell$, each itself the union of $k$ pairwise arc-disjoint spanning out-arborescences rooted at $r$, such that \[ |\{i:a\in F_i\}|\le c(a) \quad(a\in A)? \] The original packing need not merely be regrouped; a new packing may be chosen. The extra demand is that no arc occur twice inside a single $k$-arborescence, even when its capacity permits repeated use across different subgraphs. Replacing an arc by several indistinguishable copies therefore does not remove this constraint. All arborescences span the same vertex set and have the same prescribed root.

Short English statement

Can a capacitated packing of $k\ell$ rooted spanning trees be reorganized into $\ell$ groups of $k$ internally arc-disjoint rooted trees?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000009 (AMR-029-0009), 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: Capacitated packing of k-arborescences. Original source indexed by AMR-029-0009. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Capacitated packing of k-arborescences. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Capacitated_packing_of_k-arborescences.