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 [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.
• 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.