Two remarks on the optimum arborescence problem

Abstract

Given a digraph with arc costs and a prescribed root vertex r, one asks to find a cheapest spanning r-arborescence, i.e. a spanning out-tree growing from r with the least total cost. There are known several algorithms for this problem and they are very similar. The essence of those algorithms is usually called as Edmonds' algorithm. We slightly generalize the algorithm and give an easy proof. Further, we study variations of the problem where a restriction on out-degrees is considered and show that they are NP-hard and inapproximable even for simplified digraphs.