AbstractThe overwhelming majority of survivable (fault-tolerant) network design models assume auniform scenario set. Such a scenario set assumes that every subset of the network resources(edges or vertices) of a given cardinality k comprises a scenario. While this approach yieldsproblems with clean combinatorial structure and good algorithms, it often fails to capture thetrue nature of the scenario set coming from applications.One natural reﬁnement of the uniform model is obtained by partitioning the set of resourcesinto faulty and secure resources. The scenario set contains every subset of at most k faultyresources. This work studies the Fault-Tolerant Path (FTP) problem, the counterpart of theShortest Path problem in this failure model. We present complexity results alongside exact andapproximation algorithms for FTP. We emphasize the vast increase in the complexity of theproblem with respect to its uniform analogue, the Edge-Disjoint Paths problem. 1 Introduction The Minimum-Cost Edge-Disjoint Path (EDP) problem is a classical network design problem,deﬁned as follows. Given an edge-weighted graph G = (V,E), two terminals s,t ∈V and an integerparameter k ∈Z
The robustness model proposed in this paper is natural for various classical combinatorial optimization problems. Of particular interest is the counterpart of the Minimum Spanning Tree problem. This problem is closely related to the Minimum @math -Edge Connected Spanning Subgraph (ECSS) problem, a well-understood robust connection problem. Gabow, Goemans, Tardos and Williamson @cite_7 developed a polynomial time @math -approximation algorithm for ECSS, for some fixed constant @math . The authors also show that for some constant @math , the existence of a polynomial time @math -approximation algorithm implies P @math NP. An intriguing property of ECSS is that the problem becomes easier to approximate when @math grows. Concretely, while for every fixed @math , ECSS is NP-hard to approximate within some factor @math , the latter result asserts that there is function @math tending to one as @math tends to infinity such that ECSS is approximable within a factor @math . This phenomenon was already discovered by Cheriyan and Thurimella @cite_4 , who gave algorithms with a weaker approximation guarantee. The more general Generalized Steiner Network problem admits a polynomial @math -approximation algorithm due to Jain @cite_12 .
@cite_4 @cite_12 @cite_7
2134875769 2153014861 1992614365
An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of an (undirected or directed) simple graph G=(V,E). There are four versions of the problem, and the approximation guarantees are as follows: minimum-size k-node connected spanning subgraph of an undirected graph 1 + [1 k], minimum-size k-node connected spanning subgraph of a directed graph 1 + [1 k], minimum-size k-edge connected spanning subgraph of an undirected graph 1+[2 (k+1)], minimum-size k-edge connected spanning subgraph of a directed graph 1 + [4 k ]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple and deterministic and runs in time O(k|E|2). The following result on simple undirected graphs is used in the analysis: The number of edges required for augmenting a graph of minimum degree k to be k-edge connected is at most k,|V| (k+1). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or 2-edge connected) spanning subgraph whose size is within a factor of ( @math ) of minimum, where @math is a constant. We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem. The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k-edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3-k for undirected graphs with k > 1 odd, 1 + 2-k for undirected graphs with k even, and 1 + 2-k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2-k. On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2 (k ≥ 1), a polynomial-time algorithm approximating the smallest k-ECSS on undirected (directed) multigraphs to within ratio 1 + c-k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009