In this paper, we study a survivable network design problem on directed graphs, 2-Connected Directed Steiner Tree (2-DST): given an @math -vertex weighted directed graph, a root @math , and a set of @math terminals @math , find a min-cost subgraph @math that has two edge vertex disjoint paths from @math to any @math . 2-DST is a natural generalization of the classical Directed Steiner Tree problem (DST), where we have an additional requirement that the network must tolerate one failure. No non-trivial approximation is known for 2-DST. This was left as an open problem by , [SODA'09; JCSS] and has then been studied by [SODA'12; TALG] and Laekhanukit SODA'14]. However, no positive result was known except for the special case of a @math -shallow instance [Laekhanukit, ICALP'16]. We present an @math approximation algorithm for 2-DST that runs in time @math , for any @math . This implies a polynomial-time @math approximation for any constant @math , and a poly-logarithmic approximation running in quasi-polynomial time. We remark that this is essentially the best-known even for the classical DST, and the latter problem is @math -hard to approximate [Halperin and Krauthgamer, STOC'03]. As a by product, we obtain an algorithm with the same approximation guarantee for the @math -Connected Directed Steiner Subgraph problem, where the goal is to find a min-cost subgraph such that every pair of terminals are @math -edge vertex connected.
Concerning vertex connectivity, two of the most well-studied problems are the @math -Vertex Connected Steiner Tree ( @math -ST) and @math -Vertex Connected Steiner Subgraph ( @math -SS) problems, i.e., the undirected versions of and , respectively. There are @math -approximation algorithms for @math -ST and @math -SS by Fleischer et al. @cite_38 using the iterative rounding method. For @math , Nutov devised an @math -approximation algorithm for @math -ST in @cite_32 and an @math -approximation algorithm for @math -SS in @cite_15 (also, see @cite_29 ). A special case of @math -SS with metric-costs is studied by Cheriyan and Vetta in @cite_36 who gave an @math -approximation algorithm for the problem. The most extensively studied special case of @math -SS is when all vertices are terminals, namely the @math -Vertex Connected Spanning Subgraph problem, which has been studied, e.g., in @cite_10 @cite_1 @cite_16 @cite_37 @cite_18 . The current best approximation guarantees are @math @cite_37 , and @math for the case @math @cite_18 @cite_7 . More references can be found in @cite_8 @cite_14 @cite_4 .
@cite_38 @cite_37 @cite_18 @cite_14 @cite_4 @cite_7 @cite_8 @cite_36 @cite_29 @cite_1 @cite_32 @cite_15 @cite_16 @cite_10
1968690018 1983217642 2178196238 2174245573 2079430060 2163546498 1967595345 2052656799 1975776599 2058521212 1986011879
The survivable network design problem (SNDP) is the following problem: given an undirected graph and values rij for each pair of vertices i and j, find a minimum-cost subgraph such that there are at least rij disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. The element connectivity problem (ELC-SNDP, or ELC) is a problem of intermediate difficulty. In this problem, the set of vertices is partitioned into terminals and nonterminals. The edges and nonterminals of the graph are called elements. The values rij are only specified for pairs of terminals i, j, and the paths from i to j must be element disjoint. Thus if rij-1 elements fail, terminals i and j are still connected by a path in the network.These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O(log k)-approximation algorithm, where k = maxi,j rij. Since this work first appeared as an extended abstract, it has been shown that it is hard to approximate VC-SNDP to factor 2log1-en.In this paper we investigate applying iterative rounding to ELC and VC-SNDP We show that iterative rounding will not yield a constant factor approximation algorithm for general VC-SNDP. On the other hand, we show how to extend the analysis of iterative rounding applied to EC-SNDP to yield 2-approximation algorithms for both general ELC, and for the case of VC-SNDP when rij ∈ 0, 1, 2 . The latter result improves on an existing 3-approximation algorithm. The former is the first constant factor approximation algorithm for a general survivable network design problem that allows node failures. We consider Degree Constrained Survivable Network problems. For the directed Degree Constrained k -Edge-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof. Our main contribution is giving a framework to handle node-connectivity degree constrained problems with the iterative rounding method. In particular, for the degree constrained versions of the Element-Connectivity Survivable Network problem on undirected graphs, and of the k -Outconnected Subgraph problem on both directed and undirected graphs, our algorithm computes a solution J of cost O(logk) times the optimal, with degrees O(2 k )?b(v). Similar result are obtained for the k -Connected Subgraph problem. The latter improves on the only degree approximation O(klogn)?b(v) in O(n k ) time on undirected graphs by Feder, Motwani, and Zhu. We present a 6-approximation algorithm for the minimum-cost @math -node connected spanning subgraph problem, assuming that the number of nodes is at least @math . We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for @math -outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of @math . We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and @math -out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node @math in the solution is at most @math , where @math is the degree upper bound on @math . For undirected graphs and element-connectivity requirements with maximum connectivity requirement @math , our algorithm computes a solution that is a @math -approximation on the cost, and the degree of each node @math in the solution is at most @math . These ratios improve the previous @math -approximation on the cost and @math -approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k... We study undirected networks with edge costs that satisfy the triangle inequality. Let @math denote the number of nodes. We present an @math -approximation algorithm for a generalization of the metric-cost subset @math -node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each @math , there exists a @math -node connected graph whose cost is within a factor of @math of the cost of any simple @math -edge connected graph. Based on our @math -approximation algorithm, we present an @math -approximation algorithm for the metric-cost node-connectivity survivable network design problem, where @math denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704-720] recently proved, assuming NP @math DTIME( @math ), a hardness-of-approximation lower bound of @math for the subset @math -node-connectivity problem, where @math denotes a small positive number. The minimum cost subset k-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph G=(V,E) with costs on edges and a set of terminals T⊆V. The goal is to find a minimum cost subgraph such that every pair of terminals are connected by k openly (vertex) disjoint paths. In this paper, we present an approximation algorithm for the subset k-connected subgraph problem which improves on the previous best approximation guarantee of O(k2logk) by Nutov (ACM Trans. Algorithms 9(1):1, 2012). Our approximation guarantee, ?(|T|), depends upon the number of terminals: @math (|T|) = O(k ^2 k) & if 2k |T| k. This suggests that the hardest instances of the problem are when |T|?k. We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were @math for both directed and undirected graphs, and @math for undirected graphs with @math , where @math is the number of nodes in the input graph. Our first algorithm has approximation ratio @math , which is @math except for very large values of @math , namely, @math . This algorithm is based on a new result on @math -connected @math -critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio @math for all values of @math . Combining these two gives an algorithm with approximation ratio @math , which asymptotically improves the best known approximation guarantee for directed graphs for all values of @math , and for undirected graphs for @math . Moreover, this is the first algorithm that has an approximation guarantee better than @math for all values of @math . Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation. We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V,E) with edge node-costs, a node subset S ⊆ V, and connectivity requirements r(s,t):s,t ∈ T ⊆ V . The goal is to find a minimum cost subgraph H of G that for all s,t ∈ T contains r(s,t) pairwise edge-disjoint st-paths such that no two of them have a node in S s s,t in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network (S = ∅), Node-Connectivity Survivable Network (S = V), and Element-Connectivity Survivable Network (r(s,t) = 0 whenever s ∈ S or t ∈ S). Let k = maxs,t ∈ T r(s,t). In Rooted Survivable Network, there is s ∈ T such that r(u,t) = 0 for all u ≠ s, and in the Subset k-Connected Subgraph problem r(s,t) = k for all s,t ∈ T. For edge-costs, our ratios are O(k log k) for Rooted Survivable Network and O(k2 log k) for Subset k-Connected Subgraph. This improves the previous ratio O(k2 log n), and for constant values of k settles the approximability of these problems to a constant. For node-costs, our ratios are as follows. —O(k log |T|) for Element-Connectivity Survivable Network, matching the best known ratio for Edge-Connectivity Survivable Network. —O(k2 log |T|) for Rooted Survivable Network and O(k3 log |T|) for Subset k-Connected Subgraph, improving the ratio O(k8 log2 |T|). —O(k4 log2 |T|) for Survivable Network; this is the first nontrivial approximation algorithm for the node-costs version of the problem. A subset T@?V of terminals is k-connected to a root s in a directed undirected graph J if J has k internally-disjoint vs-paths for every v@?T; T is k-connected in J if for every s@?T the set T@? s is k-connected to s in J. We consider the Subsetk-ConnectivityAugmentation problem: given a graph G=(V,E) with edge node-costs, a node subset T@?V, and a subgraph J=(V,E"J) of G such that T is (k-1)-connected in J, find a minimum-cost augmenting edge-set F@?E@?E"J such that T is k-connected in J@?F. The problem admits trivial ratio O(|T|^2). We consider the case |T|>k and prove that for directed undirected graphs and edge node-costs, a @r-approximation algorithm for Rooted Subsetk-Connectivity Augmentation implies the following approximation ratios for Subsetk-Connectivity Augmentation:(i)b(@r+k)+(|T||T|-k)^2O(log|T||T|-k), where b=1 for undirected graphs and b=2 for directed graphs. (ii)@r@?O(|T||T|-klogk). The best known values of @r on undirected graphs are min |T|,O(k) for edge-costs and min |T|,O(klog|T|) for node-costs; for directed graphs @r=|T| for both versions. Our results imply that unless k=|T|-o(|T|), Subsetk-Connectivity Augmentation admits the same ratios as the best known ones for the rooted version. This improves the ratios in Nutov (2009) [19] and Laekhanukit (2011) [15]. We present an @math -approximation algorithm for the problem of finding a @math -vertex connected spanning subgraph of minimum cost, where @math is the number of vertices in an input graph, and @math is a connectivity requirement. Our algorithm is the first that achieves a polylogarithmic approximation ratio for all values of @math and @math , and it works for both directed and undirected graphs. As in previous works, we use the Frank--Tardos algorithm for finding @math -outconnected subgraphs as a subroutine. However, with our structural lemmas, we are able to show that we need only partial solutions returned by the Frank--Tardos algorithm; thus, we can avoid paying the whole cost of an optimal solution every time the algorithm is applied. We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k 2 . The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.