The Vital Core Connectivity Problem
Sylvia C. Boyd, Amy Cameron · 2012
Let G = (V, E) be an edge-weighted complete graph representing a network in which the edges represent potential links, and the vertices (centres) are partitioned into two classes – vital vertices, which represent the vital core of the network, and secondary vertices. We consider the vital core connectivity problem (VCC), which is the problem of finding a minimum weight spanning multi-subgraph of G which is k-edge connected overall and whose vital core remains at least l-edge connected even if some or all of the secondary vertices are removed. The VCC arises naturally in many practical applications in which one wishes to design a network at minimum cost which will not only survive the loss of a certain number of links overall, but for which the vital core remains at least l-edge connected even if some or all of the secondary centres are lost. We show that the VCC is, in general, NP-hard, and present the first constant factor approximation algorithm for this problem, as well as give an upper bound on the integrality gap of its linear programming relaxation. In particular, we show an approximation guarantee (and upper bound on the integrality gap) of 8 3 for l ≥ ⌈