Packing of mixed hyperarborescences with flexible roots via matroid intersection

12/27/2020

∙

by   Florian Hörsch, et al.

∙

0

∙

share

Given a mixed hypergraph ℱ=(V,𝒜∪ℰ), functions f,g:V→ℤ_+ and an integer k, a packing of k spanning mixed hyperarborescences is called (k,f,g)-flexible if every v ∈ V is the root of at least f(v) and at most g(v) of the mixed hyperarborescences. We give a characterization of the mixed hypergraphs admitting such packings. This generalizes results of Frank and, more recently, Gao and Yang. Our approach is based on matroid intersection, generalizing a construction of Edmonds. We also obtain an algorithm for finding a minimum weight solution to the above mentioned problem.