Packing of arborescences with matroid constraints via matroid intersection

• 成果类型: Article
• 署名作者: Kiraly, Csaba; Szigeti, Zoltan; Tanigawa, Shin-ichi
• 署名单位: Eotvos Lorand University; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); University of Tokyo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01377-0
• 发表日期: 2020
• 页码: 85-117

摘要

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. Kiraly 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.