Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems

摘要

Abstract Let κ ~( G )( s , t ) denote the maximum number of pairwise internally disjoint st -paths in a graph G = ( V , E ). For a set T ⊆ V $T subseteq V$ of terminals, G is k - T -connected if κ ~( G )( s , t ) ≥ k for all s , t ∈ T ; if T = V then G is k -connected. Given a root node s , G is k - ( T , s )-connected if κ ~( G )( t , s ) ≥ k for all t ∈ T . We consider the corresponding min-cost connectivity augmentation problems, where we are given a graph G = ( V , E ) of connectivity k , and an additional edge set Ê $hat E$ on V with costs. The goal is to compute a minimum cost edge set J ⊆ Ê $J subseteq hat {E}$ such that G ∪ J $G cup J$ has connectivity k + 1. For the k - T - Connectivity Augmentation problem when Ê $hat {E}$ is an edge set on T we obtain ratio O ln | T | | T | − k $Oleft (ln frac {|T|}{|T|-k}right )$ , improving the ratio O | T | | T | − k ⋅ ln | T | | T | − k $Oleft (frac {|T|}{|T|-k} cdot ln frac {|T|}{|T|-k}right )$ of Nutov (Combinatorica, 34 (1), 95–114, 2014). For the k -Connectivity Augmentation problem we obtain the following approximation ratios. For n ≥ 3 k − 5, we obtain ratio 3 for directed graphs and 4 for undirected graphs, improving the previous ratio 5 of Nutov (Combinatorica, 34 (1), 95–114, 2014). For directed graphs and k = 1, or k = 2 and n odd, we further improve to 2.5 the previous ratios 3 and 4, respectively. For the undirected 2-( T , s )- Connectivity Augmentation problem we achieve ratio 4 2 3 $4frac {2}{3}$ , improving the previous best ratio 12 of Nutov (ACM Trans. Algorithms, 9 (1), 1, 2014). For the special case when all the edges in Ê $hat E$ are incident to s , we give a polynomial time algorithm, improving the ratio 4 17 30 $4frac {17}{30}$ of Kortsarz and Nutov, (2015) and Nutov (Algorithmica, 63 (1-2), 398–410, 2012) for this variant.