|
Published in:
Let $D=(V+s,A)$ be a digraph with a designated root vertex $s$.
Edmonds' seminal result [4] implies 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\in V$, where a packing means arc-disjoint subgraphs.
Let $\cM$ be a matroid on the set of arcs leaving $s$.
A packing of $(s,t)$-paths is called $\cM$-based if their arcs leaving $s$ form a base of $\cM$ while
a packing of $s$-arborescences is called $\cM$-based if, for all $t\in V,$ the packing of $(s,t)$-paths
provided by the arborescences is $\cM$-based.
Durand de Gevigney, Nguyen and Szigeti proved in [3] that $D$ has an $\cM$-based packing of $s$-arborescences
if and only if $D$ has an $\cM$-based packing of $(s,t)$-paths for all $t\in V.$
Bérczi 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 $\cM$-based packing of
spanning $s$-arborescences if and only if $D$ has an $\cM$-based packing of $(s,t)$-paths for all $t\in 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.
For all the results presented in this paper, the undirected counterpart also holds.
Bibtex entry:
| AUTHOR | = | {Fortier, Quentin and Kir{\'a}ly, Csaba and Szigeti, Zolt{\'a}n and Tanigawa, Shin-ichi}, |
| TITLE | = | {On packing spanning arborescences with matroid constraint}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2016}, |
| NUMBER | = | {TR-2016-18} |