Strongly edge-disjoint arborescences

From Egres Open
Jump to: navigation, search

Let D=(V,A) be a digraph with a designated root node r. We call two arc-disjoint directed paths strongly edge-disjoint if they do not contain a pair of symmetric arcs. Two arcs are symmetric if they have the same endnodes but have opposite orientations. Is it true that there exist k arc-disjoint spanning arborescences rooted at r such that for every node v the paths from r to v in the arborescences are strongly edge-disjoint if an only if [math]\varrho(X)\geq k[/math] for each nonempty [math]X\subseteq V-r[/math]?

Solved b.jpg

Bérczi and Kovács gave a disproof of the conjecture for [math]k\geq 3[/math] [1]. They also gave a generalization for the case k=2.


The conjecture was proposed by Colussi, Conforti and Zambelli[2] where the case k=2 was verified. For [math]k\geq 3[/math] the question is still open. It is easy to see that a similar statement holds for strongly edge-disjoint directed s-t paths. Hence the conjecture, if it is true, can be considered as a common generalization of Edmonds' disjoint arborescences theorem and Menger's theorem. Note that the conjecture does not require the k arborescences to be strongly edge-disjoint, that is, they may share a pair of symmetric arcs.


  1. K. Bérczi and E.R. Kovács, A note on strongly edge-disjoint arborescences, Technical Report EGRES 2011-03, Department of Operations Research, Eötvös Loránd University, Budapest, March 2011. PDF
  2. L. Colussi, M. Conforti and G. Zambelli: Disjoint paths in arborescences, Discrete Mathematics, Volume 292, Issues 1-3, 28 March 2005, Pages 187--191. PDF, DOI link