Approximation Algorithms for Steiner Connected Dominating Set

Steiner connected dominating set ( SCDS) is ageneralization of the famous connected dominating set problem,where only a specified set of required vertices has to be dominated bya connected dominating set, and known to be NP-hard. This paper firstlymodifies the SCDS algorithm of Guha and Khuller and achieves a worstcase approximation ratio of (2+1/(m-1))H((\D , k))+O(1), whichoutperforms the previous best result (c+1)H((\D, k))+O(1) in thecase of m 1+1/(c-1), where c is the best approximation ratio forSteiner tree, \D is the maximum degree of the graph,k is thecardinality of the set of required vertices, m is an optional integersatisfying 0 m (D, k) and H is the harmonic function. Thispaper also proposes another approximation algorithm which is based on agreedy approach. The second algorithm can establish a worst caseapproximation ratio of 2\ln(\min(\D, k))+O(1), which can also beimproved to 2\ln k if the optimal solution is greater than\fracc\cdot e^2c+12(c+1).