On k-Connectivity Problems with Sharpened Triangle Inequality

The k-connectivity problem is to find a minimum-cost k-edge- or k-vertex-connected spanning subgraph of an edge-weighted, undirected graph G for any given G and k. Here, we consider its NP-hard subproblems with respect to the parameter β, with frac(1, 2) < β < 1, where G = (V, E) is a complete graph with a cost function c satisfying the sharpened triangle inequality c ({u, v}) ≤ β ṡ (c ({u, w}) + c ({w, v})) for all u, v, w ∈ V. First, we give a simple linear-time approximation algorithm for these optimization problems with approximation ratio frac(β, 1 - β) for any frac(1, 2) ≤ β < 1, which improves the known approximation ratios for frac(1, 2) < β < frac(2, 3). The analysis of the algorithm above is based on a rough combinatorial argumentation. As the main result of this paper, for k = 3, we sophisticate the combinatorial consideration in order to design a (1 + frac(5 (2 β - 1), 9 (1 - β)) + O (frac(1, | V |)))-approximation algorithm for the 3-connectivity problem on graphs satisfying the sharpened triangle inequality for frac(1, 2) ≤ β ≤ frac(2, 3). As part of the proof, we show that for each spanning 3-edge-connected subgraph H, there exists a spanning 3-regular 2-vertex-connected subgraph H′ of at most the same cost, and H can be transformed into H′ efficiently.