# Talk:Capacitated packing of k-arborescences

## Contents

- 1 Capacitated packing of k-braids -- Tamás Király 16:08, 4 January 2010 (UTC)
- 2 Colourful k-trees -- Tamás Király 22:32, 13 January 2010 (UTC)
- 3 When double arcs form a rooted connected subdigraph -- Tamás Király 18:38, 7 February 2010 (UTC)
- 4 Small cases, checked exhaustively -- Daveagp 17:33, 30 June 2011 (UTC)

## 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 [math]S_1,\dots,S_t[/math] be edge-disjoint star subgraphs of *G*, each of size at most *l*.

We want to decompose *G* into *l* disjoint *k*-trees [math]T_1,\dots,T_k[/math], such that [math]|T_i \cap S_j| \leq 1[/math] 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 [math]V=\{v_1,v_2,v_3,v_4\}[/math], and let*G*be the complete graph on*V*. We extend the node set by 3 new nodes: [math]w_1,w_2,w_3[/math], and add edges [math]v_1w_1,v_2w_2,v_3w_3[/math], and [math]v_4w_1,v_4w_2,v_4w_3[/math]. Let [math]G'=(V',E')[/math] be the new graph; we prove that the answer is negative for [math]G'[/math]. The stars that we consider are the following: [math](v_4v_1,v_4w_3),(v_4v_2,v_4w_1),(v_4v_3,v_4w_2)[/math], and [math](v_1v_3,v_1w_1),(v_2v_1,v_2w_2),(v_3v_2,v_3w_3)[/math]. Because the nodes [math]w_i[/math] 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 [math]X \subseteq V-r_0[/math]
**tight**if [math]\varrho_c(X)=4[/math]. We can assume that [math]\{v\}[/math] is tight for every [math]v \in V-r_0[/math], otherwise*c*could be decreased. In addition, we may assume that the only other possible tight set is [math]V-r_0[/math]. 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 [math]r_0v[/math] be a simple arc, and suppose that [math]V-r_0[/math] is not tight. Let
*w*be the parent of*v*. Replace [math]r_0v[/math] by*wv*.

- Let
- After these modifications, simple arcs can only go between parent and child, except for 2 arcs form the root if [math]V-r_0[/math] 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.