Packing branchings under cardinality constraints on their root sets

Edmonds' fundamental theorem on arborescences characterizes the existence of $k$ pairwise arc-disjoint spanning arborescences with prescribed root sets in a digraph. In this paper, we study the problem of packing branchings in digraphs under cardinality constraints on their root sets by arborescence augmentation. Let $D=(V+x,A)$ be a digraph, $\mathcal{P}=$ $\{I_{1}, \ldots, I_{l} \}$ be a partition of $[k]$, $c_{1}, \ldots, c_{l}, c'_{1}, \ldots, c'_{l}$ be nonnegative integers such that $c_α \leq c'_α$ for $α\in [l]$, $F_{1}, \ldots, F_{k}$ be $k$ arc-disjoint $x$-arborescences in $D$ such that $\sum_{i \in I_α}d_{F_{i}}^{+}(x)$ $\leq c'_α$ for $α\in [l]$. We give a characterization on when $F_{1}, \ldots, F_{k}$ can be completed to arc-disjoint spanning $x$-arborescences $F^{*}_{1}, \ldots, F^{*}_{k}$ such that for any $α\in [l]$, $c_α \leq \sum_{i \in I_α}d^{+}_{F^{*}_{i}}(x)$ $\leq c'_α$.

No reviews yet.

No comments yet.