A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem

• Input:
  • Graph $G = (V, E)$ with edge weights $c_e\geq0$
  • A root vertex $r$
  • $k$ groups of vertices $g_1, g_2, \ldots, g_k$
• Goal: Obtain a tree $T$ that
  • Connects each group $g_i$ to $r$
  • Has minimum cost

• This paper
  • $O(\log n \, \log k)$ approximation for trees
  • $O(\log^2 n \, \log k)$ approximation for general graphs
• Other Results
  • Hardness of $\Omega(\log^{2-\epsilon} n)$ (trees)
  • Some quasi-polynomial algorithms
  • $O(\log^{1+\epsilon} n \, \log k)$ approximation for trees

• Solve the problem on Trees
  • Solve linear program
  • Round solution
  • Multiple rounds
• Extend to general graphs

• Pick $e$ with probability $x_e$?
  • Doesn't work
• Do dependent rounding:
  • mark $e$ with probability $x_e/x_{p(e)}$
  • pick marked $e$ if $p(e)$ is picked

• Lemma 1: This algorithm outputs $E^\prime \subseteq E$ such that:
• $P[e\text{ is picked}] = x_e$
• $E[\text{Cost of } E^\prime] = OPT$
• For any group $g$, $$P[E^\prime \text{ connects }r\text{ to }g] \geq \Omega\left(\frac1{\log |g|}\right)$$

• The probability of success is too low
• Run $L=O(\log k \, \log n)$ rounds of the algorithm
• Lemma 2: Let $\hat E = \bigcup_{i\in [L]} \hat E_i$ after $L$ rounds. Then,
  • $P[\hat E\text{ connects all groups to }r] \geq 3/4$
  • $E[\text{Cost of } \hat E] = O(\log n \, \log k) \, OPT$

Lemma 2: Let $\hat E = \bigcup_{i\in [L]} \hat E_i$ after $L$ rounds. Then,

• $P[\hat E\text{ connects all groups to }r] \geq 3/4$
• $E[\text{Cost of } \hat E] = O(\log n \, \log k) \, OPT$

Lemma 1.3: For any group $g$, $$P[\hat E \text{ connects }r\text{ to }g] \geq \Omega\left(\frac1{\log |g|}\right)$$

Steps:

• Apply a transformation
• Bound probability with Jansen's inequality

Claim 3: If $x^\prime_e \leq x_e$ for all $e \in E$,   $$P[connect(g,x^\prime)] \leq P[connect(g, x)]$$

• Transformation:
• Remove unnecessary edges (not leading to $g$)
• Reduce $x$ such that it is minimally feasible
• Round down all $x_e$ to the nearest power of $2$
• Delete all edges with $x_e \leq 1/4|g|$
• If $x_e = x_{p(e)}$, contract $e$

• Jansen's inequality:
  • Let $S$ be a ground set and $P_1, P_2, \ldots$ subsets of $S$
  • Let $S^\prime$ be a random independent sample of $S$
  • Let $\mathcal{E}_i$ be the event that $P_i \subseteq S^\prime$
  • Let $\mu = \sum_i P[\mathcal{E}_i]$ and $\Delta = \sum_{i\sim j} P[\mathcal{E}_i \cap \mathcal{E}_j]$
  • Then, $$P\left[\cap_i \bar{\mathcal{E}}_i\right] \leq \exp\left\{\frac{-\mu^2}{2\Delta}\right\}$$

• Claim 4:
  • Let $S$ be the set of edges
  • $P_v$ the set of edges in the path from $r$ to $v$
  • Let $S^\prime$ be a set of edges marked w. p. $x_e/x_{p(e)}$.
  • Then, $1/4 \leq \mu \leq 1$ and $\Delta \leq 2 \log n $

Lemma 1.3: For any group $g$, $$P[\hat E \text{ connects }r\text{ to }g] \geq \Omega\left(\frac1{\log |g|}\right)$$

Steps:

• Apply a transformation
• Bound probability with Jansen's inequality

• Approximate edge costs by a tree metric
  • Possible to do with $O(\log n)$ distortion
  • This transforms the graph into a tree
• Result: $O(\log^2 n \, \log k)$ approximation

• $O(\log n \, \log k)$ approximation for trees
• $O(\log^2 n \, \log k)$ approximation for general graphs
• Hardness of $\Omega(\log^{2-\epsilon} n)$ (trees)