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.
