A primal-dual schema based approximation algorithm for the element connectivity problem

Abstract

The element connectivity problem falls in the category of survivable network design problems - it is intermediate to the versions that ask for edge-disjoint and vertex-disjoint paths. The edge version is by now well understood from the view-point of approximation algorithms [Williamson et al., Combinatorica 15 (1995) 435-454; Goemans et al., in: SODA '94, 223-232; Jain, Combinatorica 21 (2001) 39-60], but very little is known about the vertex version. In our problem, vertices are partitioned into two sets: terminals and nonterminals. Only edges and nonterminals can fail - we refer to them as elements - and only pairs of terminals have connectivity requirements, specifying the number of element-disjoint paths required. Our algorithm achieves an approximation guarantee of factor 2Hk, where k is the largest requirement and Hn = 1 + 1/2 + ⋯ + 1/n. Besides providing possible insights for solving the vertex-disjoint paths version, the element connectivity problem is of independent interest, since it models situation.