Approximation algorithms for priority Steiner tree problems

Abstract

In the Priority Steiner Tree (PST) problem, we are given an undirected graph $G=(V,E)$ with a source $s\in V$ and terminals $T\subseteq V\setminus \{s\}$, where each terminal $v\in T$ requires a nonnegative priority $P(v)$. The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from $s$ to each terminal $v$ consists of edges of rate greater than or equal to $P(v)$. The PST problem with $k$ priorities admits a $\min \{2\ln |T|+2,k\rho \}$-approximation [Charikar et al., 2004], and is hard to approximate with ratio $c\log \log n$ for some constant $c$ [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the $(2\ln |T|+2)$-approximation to show an approximation ratio of $\lceil {\log }_2|T|\rceil +1\le 1.443\ln |T|+2$, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a $(2\ln |T|+2)$-approximation using extensions of the spider decomposition by [Klein \& Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight.