On Rooted k-Connectivity Problems in Quasi-bipartite Digraphs

We consider the directed Rooted Subset k -Edge-Connectivity problem: given a digraph G= (V, E) with edge costs, a set T⊂ V of terminals, a root node r, and an integer k, find a min-cost subgraph of G that contains k edge disjoint rt-paths for all t∈ T. The case when every edge of positive cost has head in T admits a polynomial time algorithm due to Frank [9], and the case when all positive cost edges are incident to r is equivalent to the k -Multicover problem. Recently, Chan et al. [2] obtained ratio O(ln kln | T| ) for quasi-bipartite instances, when every edge in G has an end (tail and/or head) in T+ r. We give a simple proof for the same ratio for a more general problem of covering an arbitrary T-intersecting supermodular set function by a minimum cost edge set, and for the case when only every positive cost edge has an end in T+ r.