The minimum degree arborescence problem involves computing an (out-)arborescence in a given directed graph that minimizes the maximum out-degree. This problem is NP-complete since it generalizes Hamiltonian path. We present a "plus 2" additive approximation algorithm for minimum degree arborescence. This result is then extended to a large class of degree-bounded connectivity problems on digraphs. As a byproduct of these results, we also obtain a short proof of the recent "plus 1" approximation result for degree-bounded MST.
This is joint work with Nikhil Bansal and Rohit Khandekar.