The lecture was held within the framework of the follow-up workshop to the Hausdorff Trimester Program: Combinatorial Optimization.
Abstract:
Edmonds characterized digraphs having a packing of k spanning arborescences in terms of connectivity and later in terms of matroid intersection. Durand de Gevigney, Nguyen, and Szigeti characterized digraphs having a packing of (not necessarily spanning) arborescences with some matroid constraint and gave an algorithm for the weighted case using submodular function minimization. Kamiyama, Katoh, and Takizawa characterized digraphs that have a packing of reachability arborescences. Cs. Király provided a common generalization of these results and an algorithm for the cardinality case. Bérczi, T. Király, and Kobayashi showed, using bi-set functions, that the weighted case of Cs. Király's problem can be solved with submodular flows.We show in this talk that this weighted problem can be solved with the weighted matroid intersection algorithm of Edmonds. In the reduction we show a construction of matroids from intersecting submodular bi-set functions.
Joint work with Cs. Király and S. Tanigawa
