An efficient algorithm for minimum-weight bibranching (Q1272485)

Let \(D=(V,A)\) be a directed graph, \(S\) a subset of \(V\), and \(T\) the complement of \(S\) in \(V\). A bibranching in \(D\) (with respect to \(S)\) is a set \(B\) of arcs such that for each \(v\in S\), \(B\) contains a directed path from \(v\) to a vertex in \(T\), and for each \(v\in T\), \(B\) contains a directed path from a vertex in \(S\) to \(v\). If \(S=\{r\}\), a minimal bibranching is an \(r\)-branching, a directed tree rooted at \(r\). The authors give a primal-dual algorithm that determines a minimum weight bibranching in a weighted digraph with running time \(O(n'(m+n\log n))\), where \(m=| A|\), \(n=| V|\) and \(n'=\min\{| S|,| T|\}\). This algorithm obtains the best known bounds for two special cases of the problem: bipartite edge covers and \(r\)-branching.