On packing spanning arborescences with matroid constraint

Let us be given a rooted digraph D = ( V + s , A ) with a designated root vertex s . Edmonds' seminal result [Edmonds, J., Edge-disjoint branchings , in: B. Rustin (ed.) Combinatorial Algorithms, Academic Press, New York, 91–96 (1973] states that D has a packing of k spanning s -arborescences if and only if D has a packing of k ( s , t )-paths for all t ∈ V , where a packing means arc-disjoint subgraphs. Let M be a matroid on the set of arcs leaving s . A packing of ( s , t )-paths is called M -based if their arcs leaving s form a base of M while a packing of s -arborescences is called M -based if, for all t ∈ V , the packing of ( s , t )-paths provided by the arborescences is M -based. Durand de Gevigney, Nguyen and Szigeti proved in [Durand de Gevigney, O., V.H. Nguyen, and Z. Szigeti, Matroid-based packing of arborescences , SIAM J. Discrete Math., 27 (2013), 567–574] that D has an M -based packing of s -arborescences if and only if D has an M -based packing of ( s , t )-paths for all t ∈ V . Berczi and Frank conjectured that this statement can be strengthened in the sense of Edmonds' theorem such that each s -arborescence is required to be spanning. Specifically, they conjectured that D has an M -based packing of spanning s -arborescences if and only if D has an M -based packing of ( s , t )-paths for all t ∈ V . We disprove this conjecture in its general form and we prove that the corresponding decision problem is NP-complete. However, we prove that the conjecture holds for several fundamental classes of matroids, such as graphic matroids and transversal matroids.