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 1 2 < ? < 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?V u , v , w ? V . First, we give a simple linear-time approximation algorithm for these optimization problems with approximation ratio ? 1 ? ? for any 1 2 ? ? < 1 , which improves the known approximation ratios for 1 2 < ? < 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 k = 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 1 2 ? ? ? 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? H ? of at most the same cost, and H  can be transformed into H? H ? efficiently.
approximation algorithms combinatorial problems minimum-cost k-connected spanning subgraph graph algorithms