Primal-Dual-Based Algorithms for a Directed Network Design Problem

We present efficient algorithms for a special case of network design problems, the strong-connectivity problem. Given a directed graph G, the strong-connectivity problem seeks a minimum cost strongly connected spanning subgraph of G. Our algorithms include the primal-dual method, penalty algorithms, and drop algorithms. Primal-dual methods have been quite successful for developing algorithms for undirected network design problems. However, no results are known for extending them to the directed counterparts. We apply the primal-dual method to the strong-connectivity problem, and show that the new algorithm has an approximation guarantee of three. Our computational results over randomly created instances show that the primal-dual is efficient. We develop two improved algorithms, penalty and drop, building on primal-dual as a subroutine.