Improved methods for approximating node weighted Steiner trees and connected dominating sets

In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy appr oximation algorithm based on "spider decompositions" was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximat ion ratio of 2 In k, where k is the number of terminals. However, the best known lower bound on the approximation ratio is (1 - o(1)) In k, assuming t hat NP not subset of or equal to DTIME[n(O(log log) (n))], by a reduction f rom set cover. We show that for the unweighted case we can obtain an approx imation factor of In k. For the weighted case we develop a new decompositio n theorem and generalize the notion of "spiders" to "branch-spiders" that a re used to design a new algorithm with a worst case approximation factor of 1.5 In k. We then generalize the method to yield an approximation factor o f (1.35 + epsilon) In k, for any constant epsilon > 0. These algorithms, al though polynomial, are not very practical due to their high running time, s ince we need to repeatedly find many minimum weight matchings in each itera tion. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1.6103 In k. The techniques developed f or this algorithm imply a method of approximating node weighted network des ign problems defined by 0-1 proper functions as well. These new ideas also lead to improved approximation guarantees for the problem of finding a mini mum node weighted connected dominating set. The previous best approximation guarantee for this problem was 3 In n by Guha and Khuller. By a direct app lication of the methods developed in this paper we are able to develop an a lgorithm with an approximation factor of (1.35 + epsilon) In n for any fixe d epsilon > 0. (C) 1999 Academic Press.