Problem of the month February 2010

We decided to extend the Problem of the Month status of Capacitated packing of k-arborescences to February:

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

In January, we checked random examples of the colourful version (see the problem page) on up to 20 nodes, and found no counterexamples. We plan to do a more extensive search for counterexamples this month.

Please visit the discussion page of the problem if you have any observations, ideas or questions!