An Efficient Algorithm for Minimum-Weight Bibranching

Given a directed graphD=(V, A) and a setS⊆V, a bibranching is a set of arcsB⊆Athat contains av−(V\S) path for everyv∈Sand anS−vpath for everyv∈V\S. In this paper, we describe a primal–dual algorithm that determines a minimum weight bibranching in a weighted digraph. It has running timeO(n′(m+n log n)), wherem=|A|,n=|V| andn′=min{|S|, |V\S|}. Thus, our algorithm obtains the best known bounds for two important special cases of the problem: bipartite edge cover andr-branching.