Talk:Disjoint spanning in- and out-arborescences

A special case -- Berkri 10:11, 9 February 2010 (UTC)

Assume that [math]D=(V,A')[/math] is a directed graph and [math]r\in V[/math] is a designated root-node for which [math]D-r[/math] is acyclic. Then the existence of disjoint spanning in- and out-arborescences rooted at [math]r[/math] can be decided easily as follows.

Define a bipartite graph [math]G=(V^+\cup V^-,A;E)[/math] where [math]V^+[/math] and [math]V^-[/math] are two copies of [math]V-r[/math], each node in [math]A[/math] corresponds to an arc of [math]D[/math] and [math]E[/math] contains the edges [math]av^+[/math] and [math]au^-[/math] for each [math]uv=a\in A'[/math] (if [math]u,v\neq r[/math], in other case one of the edges is missing from [math]E[/math]). Since [math]D-r[/math] is acyclic, a matching covering [math]V^+\cup V^-[/math] corresponds to a pair of disjoint spanning in- and out-arborescences, hence Hall's theorem gives a necessary and sufficient condition. However, as each node in [math]A[/math] has degree at most [math]2[/math], it is easy to see that -for example- [math]\varrho(v),\delta(v)\geq 2\ \forall v\in V-r[/math] ensures the existence of such arborescences in this very special case.

A natural idea could be the following. Leave out edges from a highly-edge-connected directed graph in such a way that the resulting graph contains a node covering each directed cycle and every other node has in- and out-degree at least [math]2[/math]. Unfortunately this approach does not work in general. Take the same directed cycle [math]v_1,...,v_{2k}[/math] [math]k[/math]-times, do the same with another directed cycle [math]w_1,...,w_{2k}[/math] and finally add the edges [math]v_{2i-1}w_{2i-1}[/math], [math]w_{2i}v_{2i}[/math] for [math]i=1,...,k[/math]. The resulting digraph is clearly [math]k[/math]-edge-connected. In order to make each directed cycle to go through the same node we have to completely cut through at least one of the cycles by leaving out edges. Then in this cycle a node with in- or out-degree at most [math]1[/math] certainly appears.

It is worth mentioning here that it is [math]\mathcal{NP}[/math]-complete to find a maximal acyclic subgraph in a digraph.