Capacitated packing of k-arborescences

Let D=(V,A) be a digraph with arc-capacities $$c : A \to \mathbb{N}$$ and a root node $$r_0\in V$$ . A k-arborescence is the arc-disjoint union of k spanning arborescences rooted at $$r_0$$ . Is it true that if $$c(a)\leq l$$ for every $$a \in A$$ and there is a capacity-obeying packing of kl spanning arborescences, then there is a capacity-obeying packing of l k-arborescences?

Remarks

The undirected version of the conjecture can be formulated as a base packing problem in a matroid, and it is not hard to see using the Matroid union theorem that it is true. However, the directed version involves packing common bases of two matroids, for which no min-max formula is known. Note that even the first non-trivial case, k=l=2, is open. The conjecture has several equivalent forms:

Integer decomposition property of the k-arborescence polyhedron

Does the following polyhedron, which is the convex hull of k-arborescences by Edmonds' disjoint arborescences theorem, have the integer decomposition property:

$$P = \{ x\in \mathbb{R}^A: 0\le x\le 1, x(A)=k(|V|-1), \varrho_x(Z)\ge k\ \forall \emptyset\neq Z\subseteq V-r_0\}?$$

Colourful k-arborescences

In a digraph D=(V,A) (with no capacities on the arcs), let us have a colouring of the arcs so that two arcs may have the same colour only if their heads coincide. A k-arboresence is called colourful if it does not contain two arcs of the same colour. Is it true that if there are at most l arcs of each colour and D has kl disjoint spanning arboresences, then it has l disjoint colourful k-arborescences?

This conjecture seems to be stronger, but it is actually equivalent to the original conjecture. The reduction goes roughly as follows. Suppose that the colour classes of incoming arcs at node v are $$A_1,\dots,A_t$$ . We replace v by a cycle on t new nodes $$v_1,\dots,v_t$$ . Each arc of the cycle has k parallel copies; k-1 of them have capacity l, while the last one has capacity $$l-|E_i|$$ for arc $$v_{i-1}v_i$$ . The arcs in $$E_i$$ enter $$v_i$$ in the new digraph, while the arcs originally leaving v are leaving $$v_1$$ .

After doing this transformation for each node $$v \in V-r_0$$ , the resulting digraph has a capacity-obeying packing of kl spanning arborescences, and a capacity-obeying packing of l k-arborescences determines a packing of l colourful k-arborescences in the original digraph.

This reduction also shows that in this colourful version of the conjecture we can assume that D is a kl-arborescence and there are exactly l arcs of each colour.

Covering by k-branchings

A k-branching is the arc-disjoint union of k branchings. Let D=(V,A) be a digraph and $$f : A \to \{1,\dots,l\}$$ a function on the arcs. Is it true that if $$\varrho_f(v) \leq kl$$ for every $$v \in V$$ and $$i_f(Z) \leq kl (|Z|-1)$$ for every non-empty $$Z \subseteq V$$ , then there are l k-branchings such that every arc $$a \in A$$ is in at least f(a) of them?

The equivalence of this problem can be seen by adding a new node $$r_0$$ to V and adding $$kl-\varrho_f(v)$$ parallel arcs $$r_0v$$ for each $$v \in V$$ .