Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
 
conference paper

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

Moldenhauer, Carsten  
2011
Information And Computation
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)

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1016/j.ic.2012.10.017
Web of Science ID

WOS:000313861100020

Author(s)
Moldenhauer, Carsten  
Date Issued

2011

Publisher

Academic Press Inc Elsevier Science

Publisher place

San Diego

Published in
Information And Computation
Total of pages

14

Volume

222

Start page

293

End page

306

Subjects

Node-Weighted Steiner Forest

•

Generalized Steiner Tree

•

Vertex feedback set

•

Primal-dual algorithm

•

Approximation algorithms

•

Planar graphs

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
DISOPT  
Event nameEvent placeEvent date
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

Available on Infoscience
March 28, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/90958
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés