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.