Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein · ACM Transactions on Algorithms · 2014
We improve the approximation ratios for two optimization problems in planar graphs. For node-weighted Steiner tree, a classical network-optimization problem, the best achievable approximation ratio in general graphs is Θ (log n ), and nothing better was previously known for planar graphs. We give a constant-factor approximation for planar graphs. Our algorithm generalizes to allow as input any nontrivial minor-closed graph family, and also generalizes to address other optimization problems such as Steiner forest, prize-collecting Steiner tree, and network-formation games. The second problem we address is group Steiner tree: given a graph with edge weights and a collection of groups (subsets of nodes), find a minimum-weight connected subgraph that includes at least one node from each group. The best approximation ratio known in general graphs is O (log 3 n ), or O (log 2 n ) when the host graph is a tree. We obtain an O (log n polyloglog n ) approximation algorithm for the special case where the graph is planar embedded and each group is the set of nodes on a face. We obtain the same approximation ratio for the minimum-weight tour that must visit each group.