# Strongly edge-disjoint arborescences

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 $\varrho(X)\geq k$ for each nonempty $X\subseteq V-r$?

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

## Remarks

The conjecture was proposed by Colussi, Conforti and Zambelli[2] where the case k=2 was verified. For $k\geq 3$ 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.

## References

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