Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider the restriction to planar graphs where the problem remains NP-complete. Demaine et al. showed that the generic primal-dual algorithm of Goemans and Williamson is a 6-approximation on planar graphs. We present (1) two different analyses to prove an approximation factor of 3, (2) show that our analysis is best possible for the chosen proof strategy, and (3) generalize this result to feedback problems on planar graphs. We give a simple proof for the first result using contraction techniques and following a standard proof strategy for the generic primal-dual algorithm. Given this proof strategy our analysis is best possible which implies that proving a better upper bound for this algorithm, if possible, would require different proof methods. Then, we give a reduction on planar graphs of FEEDBACK VERTEX SET to NODE-WEIGHTED STEINER TREE, and SUBSET FEEDBACK VERTEX SET to NODE-WEIGHTED STEINER FOREST. This generalizes our result to the feedback problems studied by Goemans and Williamson. For the opposite direction, we show how our constructions can be combined with the proof idea for the feedback problems to yield an alternative proof of the same approximation guarantee for NODE-WEIGHTED STEINER FOREST. (C) 2012 Elsevier Inc. All rights reserved.

Published in:
Information And Computation, 222, 293-306
Presented at:
38th International Colloquium on Automata, Languages and Programming (ICALP) / Annual Meeting of the European-Association-for-Theoretical-Computer-Science (EATCS)', u'38th International Colloquium on Automata, Languages and Programming (ICALP), Zürich, July 2011
San Diego, Academic Press Inc Elsevier Science

 Record created 2013-03-28, last modified 2019-08-12

Rate this document:

Rate this document:
(Not yet reviewed)