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 $$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?

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!