Packing of mixed hyperarborescences with flexible roots via matroid intersection (Q2048562): Difference between revisions

Summary: Given a mixed hypergraph \(\mathcal{F}=(V,\mathcal{A}\cup \mathcal{E})\), a non-negative integer \(k\) and functions \(f,g:V\rightarrow \mathbb{Z}_{\geq 0} \), a packing of \(k\) spanning mixed hyperarborescences of \(\mathcal{F}\) is called \((k,f,g)\)-flexible if every \(v \in 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 \textit{A. Frank} [in: Algebraic methods in graph theory. Vol. I, II. Conference held in Szeged, August 24--31, 1978. Amsterdam-Oxford-New York: North-Holland Publishing Company. 159--169 (1981; Zbl 0507.05054)] and, more recently, \textit{H. Gao} and \textit{D. Yang} [``Packing of spanning mixed arborescences'', Preprint, \url{arXiv:2005.03218}]. 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 problem mentioned above.