# Talk:Capacitated packing of k-arborescences

## Capacitated packing of k-braids -- Tamás Király 16:08, 4 January 2010 (UTC)

The analogous statement for the capacitated packing of k-braids is true in both undirected and directed graphs. This follows from the fact that the polyhedron of s-t flows of value k is a polyhedron defined by a TU matrix, so it has the integer decomposition property. Since each integer s-t flow of value k contains a k-braid, a capacity-obeying packing of k-braids can be obtained from the integer decomposition.

## Colourful k-trees -- Tamás Király 22:32, 13 January 2010 (UTC)

It may be interesting to formulate an undirected version of the equivalent conjecture on colourful k-arborescences. Here is my proposal, which is actually more general than the directed one:

Let us call the edge-disjoint union of k spanning trees a k-tree. Let G=(V,E) be a graph that is a kl-tree, and let $S_1,\dots,S_t$ be edge-disjoint star subgraphs of G, each of size at most l.

We want to decompose G into l disjoint k-trees $T_1,\dots,T_k$, such that $|T_i \cap S_j| \leq 1$ for every i and j. When is this possible?

### Re: Colourful k-trees -- Tamás Király 15:56, 5 February 2010 (UTC)

I thought about this and it is not always possible even for k=1 and l=2. Let $V=\{v_1,v_2,v_3,v_4\}$, and let G be the complete graph on V. We extend the node set by 3 new nodes: $w_1,w_2,w_3$, and add edges $v_1w_1,v_2w_2,v_3w_3$, and $v_4w_1,v_4w_2,v_4w_3$. Let $G'=(V',E')$ be the new graph; we prove that the answer is negative for $G'$. The stars that we consider are the following: $(v_4v_1,v_4w_3),(v_4v_2,v_4w_1),(v_4v_3,v_4w_2)$, and $(v_1v_3,v_1w_1),(v_2v_1,v_2w_2),(v_3v_2,v_3w_3)$. Because the nodes $w_i$ have degree 2, the structure of the stars implies that any two independent edges of G must be in different trees. But two trees with that property do not exist.

## When double arcs form a rooted connected subdigraph -- Tamás Király 18:38, 7 February 2010 (UTC)

Here is a special case that can be proved easily. Let k=2, l=2, and let us call an arc with capacity 2 a double arc; other arcs are called simple arcs. We consider the case when the subdigraph formed by double arcs is rooted connected, so it contains a spanning arborescence B. In this case the conjecture is true, and the sketch of the proof is the following.

• Let us call a set $X \subseteq V-r_0$ tight if $\varrho_c(X)=4$. We can assume that $\{v\}$ is tight for every $v \in V-r_0$, otherwise c could be decreased. In addition, we may assume that the only other possible tight set is $V-r_0$. To see this, consider another tight set X. We can define two smaller problems, by contracting X and V-X respectively. By induction, these smaller instances have solutions, and it is easy to see that these two solutions can be glued together (we use here that X is entered by a double arc).
• We can assume that B contains all double arcs, because we can replace other double arcs by 2 parallel arcs. Since each node has in-capacity 4, one entering double arc guarantees that the other 2 arcs are in different 2-arborescences.
• We can simplify the structure of simple arcs. Consider B as a rooted tree. We will give 3 types of modifications. At each type, we change the tail of one arc, which cannot create a deficient set because there are no non-trivial sight sets. Moreover, it can be seen that a good decomposition of the resulting graph into 2 2-arborescences can be easily transformed into a good decomposition of the original digraph. The 3 modifications are:
• Let uv be a simple arc where u is not a descendant of v (in the rooted tree defined by B), and not the root. Let w be the parent of v. Replace uv by wv.
• Let uv be a simple arc where u is a descendant of v. Let w be the child of v whose descendant is u. Replace uv by wv.
• Let $r_0v$ be a simple arc, and suppose that $V-r_0$ is not tight. Let w be the parent of v. Replace $r_0v$ by wv.
• After these modifications, simple arcs can only go between parent and child, except for 2 arcs form the root if $V-r_0$ is tight. For such instances, it is easy to see that the conjecture is true, by induction on the size of the digraph.

## Small cases, checked exhaustively -- Daveagp 17:33, 30 June 2011 (UTC)

An undergrad at EPFL, Fréd Pythoud, has done a brute-force calculation to find counterexamples, for a semester project. We focussed on the case k=2, l=2 and got as far as 6 vertices. There are no counter-examples up to that point.