A faster algorithm for packing branchings in digraphs

We consider the problem of finding an integral (and fractional) packing of branchings in a capacitated digraph with root-set demands. Schrijver described an algorithm that returns a packing with at most m+n3+rm+n3+r branchings that makes at most m(m+n3+r)m(m+n3+r) calls to an oracle that basically computes a minimum cut, where nn is the number of vertices, mm is the number of arcs and rr is the number of root-sets of the input digraph. Leston-Rey and Wakabayashi described an algorithm that returns a packing with at most m+r−1m+r−1 branchings but makes a large number of oracle calls. In this work we provide an algorithm, inspired on ideas of Schrijver and in a paper of Gabow and Manu, that returns a packing with at most m+r−1m+r−1 branchings and makes at most (m+r+2)n(m+r+2)n oracle calls. Moreover, for the arborescence packing problem our algorithm provides a packing with at most m−n+2m−n+2 arborescences–thus improving the bound of mm of Leston-Rey and Wakabayashi–and makes at most (m−n+5)n(m−n+5)n oracle calls.