Problem of the month January 2010

The problem we chose for the first Problem of the month is a longtime favourite. It is referred to as the Splendid Conjecture in Egres circles, the more conventional name being Capacitated packing of k-arborescences:

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?

We had several unsuccessful attempts to solve this problem before, and some of us doubt the validity of the conjecture. On the other hand, if it was true, it would imply very interesting structural properties of arborescences, as the equivalent formulations on the problem page show.

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