Covering Intersecting Bi-set Families under Matroid Constraints
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi · SIAM Journal on Discrete Mathematics · 2016
Edmonds's fundamental theorem on arborescences in [J. Edmonds, Edge-disjoint branchings, in Combinatorial Algorithms, Courant Comput. Sci. Sympos. 9, Algorithmics Press, New York, 1973, pp. 91--96] characterizes the existence of $k$ pairwise arc-disjoint spanning arborescences with the same root in a directed graph. In [L. Lovász, J. Combinatorial Theory Ser. B, 21 (1976), pp. 96--103], Lovász gave an elegant alternative proof which became the basis of many extensions of Edmonds's result. In this paper, we use a modification of Lovász's method to prove a theorem on covering intersecting bi-set families under matroid constraints. Our result can be considered as an extension of previous results on packing arborescences. We also investigate the algorithmic aspects of the problem and present a polynomial-time algorithm for solving the corresponding optimization problem.