Packing of maximal independent mixed arborescences

Abstract

Király in [On maximal independent arborescence packing, SIAM J. Discrete. Math. 30 (4) (2016), 2107-2114] solved the following packing problem: Given a digraph $D=(V,A)$, a matroid $M$ on a set $S=\{s_1,\dots ,s_k\}$ along with a map $\pi :S\to V$, find $k$ arc-disjoint maximal arborescences $T_1,\dots ,T_k$ with roots $\pi (s_1),\dots ,\pi (s_k)$, such that, for any $v\in V$, the set $\{s_i:v\in V(T_i)\}$ is independent and its rank reaches the theoretical maximum. In this paper, we give a new characterization for packing of maximal independent mixed arborescences under matroid constraints. 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. Note that our new characterization extends Király's result to mixed graphs, this answers a question that has already attracted some attentions.