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 12<β<1, where G=(V,E)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}))c({u,v})⩽β⋅(c({u,w})+c({w,v})) for all u,v,w∈Vu,v,w∈V.First, we give a simple linear-time approximation algorithm for these optimization problems with approximation ratio β1−β for any 12⩽β<1, which improves the known approximation ratios for 12<β<23.The analysis of the algorithm above is based on a rough combinatorial argumentation. As the main result of this paper, for k=3k=3, we sophisticate the combinatorial consideration in order to design a (1+5(2β−1)9(1−β)+O(1|V|))-approximation algorithm for the 3-connectivity problem on graphs satisfying the sharpened triangle inequality for 12⩽β⩽23.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′H′ of at most the same cost, and H   can be transformed into H′H′ efficiently.