Packing of maximal independent mixed arborescences.

This paper studies the following packing problem: Given a mixed graph F with vertex set V , a matroid M on a set S = { s 1 , ... , s k } along with a map π : S → V , find k mutually edge and arc-disjoint mixed arborescences T 1 , ... , T k in F with roots π (s 1) , ... , π (s k) , such that, for any v ∈ V , the set { s i : v ∈ V (T i) } is independent and its rank reaches the theoretical maximum. This problem was mentioned by Fortier, Király, Léonard, Szigeti and Talon in [Old and new results on packing arborescences in directed hypergraphs, Discrete Appl. Math. 242 (2018), 26-33]; Matsuoka and Tanigawa gave a solution to this in [On reachability mixed arborescence packing, Discrete Optimization 32 (2019) 1-10]. In this paper, we give a new characterization for above packing problem. This new characterization is simplified to the form of finding a supermodular function that should be covered by an orientation of each strong component of a matroid-based rooted mixed graph. Our proofs come along with a polynomial-time algorithm. The technique of using components opens some new ways to explore arborescence packings. [ABSTRACT FROM AUTHOR]