Independent arborescences in acyclic digraphs

From Egres Open
Jump to: navigation, search

Let D=(V,A) be an acyclic digraph with designated root-nodes [math]r_1,...,r_k\in V[/math]. Let [math]U_1,...,U_k[/math] be convex node sets with [math]r_i\in U_i[/math]. Is it true that there exist independent [math]r_i[/math]-arborescences [math]F_i[/math] with [math]V(F_i)=U_i[/math] if and only if there exist openly node-disjoint [math]r_i-v[/math] paths [math]P_i[/math] ([math]v\in U_i[/math]) for each [math]v\in V[/math]? (We call the [math]r_i-v[/math] and [math]r_j-v[/math] paths [math]P_i[/math] and [math]P_j[/math] openly node-disjoint if they are edge-disjoint and [math]V(P_i)\cap V(P_j)=\{v\}\cup(\{r_i\}\cap\{r_j\})[/math].)


The problem was proposed by S. Fujishige, N. Kamiyama and N. Katoh. As a node-disjoint analogue of Edmonds' disjoint arborescences theorem, Frank conjectured that if there exist k internally node-disjoint r-s paths in an arbitrary digraph D for each [math]s\in V[/math] then there exist k independent spanning r-arborescences. For k=2, this was proved by Whitty in [1]. Huck found a counterexample for [math]k\geq 3[/math] [2], and also showed that the conjecture holds for acyclic digraphs [3].

Frank, Fujushige, Kamiyama, and Katoh [4] verified the above conjecture for the following two cases:

  • the r_i's are identical,
  • each node [math]v\in V[/math] is contained in at most two of the convex sets.

They also proved that if both of the above (the second for [math]v\in V-r[/math]) are satisfied, then the conjecture is true even for not necessarily acyclic digraphs.

Related open problems

Independent trees


  1. R.W. Whitty, Vertex-disjoint paths and edge-disjoint branchings in directed graphs, Journal of Graph Theory, 11, 349-358 (1987), DOI link
  2. A. Huck, Disproof of a conjecture about independent branchings in k-connected directed graphs, Journal of Graph Theory, 20, 235-239 (1995), DOI link
  3. A. Huck, Independent branchings in acyclic digraphs, Discrete Mathematics, 199, 245-249 (1999), DOI link
  4. A. Frank, S. Fujishige, N. Kamiyama, N. Katoh, Independent arborescences in directed graphs, DOI link, author link