|
Published in:
Edmonds' arborescence packing theorem characterizes directed graphs that have arc-disjoint spanning arborescences in terms of connectivity. Later he also observed a characterization in terms of matroid intersection.
Since these fundamental results, intensive research
has been done for understanding and extending
these results.
In this paper we shall extend the second characterization to the setting of
reachability-based packing of arborescences.
The reachability-based packing problem was introduced by Cs.~Kir{\'a}ly as a common generalization of
two different
extensions of the spanning arborescence packing problem, one is due to Kamiyama, Katoh, and Takizawa, and the other is due to Durand de Gevigney, Nguyen, and Szigeti.
Our new characterization of the arc sets of reachability-based packing in terms of matroid intersection gives an efficient algorithm for the minimum weight reachability-based packing problem, and it also enables us to unify
further arborescence packing theorems and Edmonds' matroid intersection theorem.
For the proof, we also show how a new class of matroids can be defined by extending an earlier construction of matroids from intersecting submodular functions to bi-set functions based on an idea of Frank.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Csaba and Szigeti, Zolt{\'a}n and Tanigawa, Shin-ichi}, |
| TITLE | = | {Packing of arborescences with matroid constraints via matroid intersection}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2018}, |
| NUMBER | = | {TR-2018-08} |