We discuss a primal-dual based 2-approximation for the Steiner Forest problem^[1]. In the Steiner Forest problem there is a graph $G=(V,E)$$G=(V,E)$G=(V,E)G=(V, E) where each edge $e\in E$$e\in E$e in Ee \in E has a cost $c_e\in \mathbb{R}$$c_e\in \mathbb{R}$c_(e)inRc_{e} \in \mathbb{R}. We are given $k$$k$kk pairs of vertices $(s_1,t_1),(s_2,t_2),\dots (s_k,t_k)\in$$\left(s_1,t_1\right),\left(s_2,t_2\right),\dots \left(s_k,t_k\right)\in$(s_(1),t_(1)),(s_(2),t_(2)),dots(s_(k),t_(k))in\left(s_{1}, t_{1}\right),\left(s_{2}, t_{2}\right), \ldots\left(s_{k}, t_{k}\right) \in $V\times V$$V\times V$V xx VV \times V. The goal is to find the minimum cost set of edges $F$$F$FF such that in the graph $(V,F)$$(V,F)$(V,F)(V, F) the vertices $s_i$$s_i$s_(i)s_{i} and $t_i$$t_i$t_(i)t_{i} are in the same connected component for $1\le i\le k$$1\le i\le k$1 <= i <= k1 \leq i \leq k. We refer to the set $\{s_1,\dots ,s_k,t_1,\dots ,t_k\}$$\left\{s_1,\dots ,s_k,t_1,\dots ,t_k\right\}${s_(1),dots,s_(k),t_(1),dots,t_(k)}\left\{s_{1}, \ldots, s_{k}, t_{1}, \ldots, t_{k}\right\} as terminals. Notice that the graph $(V,F)$$(V,F)$(V,F)(V, F) can contain multiple connected components.

One can see that Steiner Forest generalizes the Steiner Tree problem. It is, however, much less easy to obtain a constant factor approximation for Steiner Forest. A natural greedy heuristic, similar to that for the online Steiner Tree problem is the following. We order the the pairs in some arbitrary fashion, say as $1$$1$11 to $k$$k$kk without loss of generality. We maintain a forest $F$$F$FF of edges that we have already bought. When considering pair $i$$i$ii we find a shortest path $P$$P$PP from $s_i$$s_i$s_(i)s_{i} to $t_i$$t_i$t_(i)t_{i} in the graph in which we reduce the cost of each edge in $F$$F$FF to $0$$0$00 (since we already paid for them). We add the new edges in $P$$P$PP to $F$$F$FF. Although simple to describe, the algorithm is not straight forward to analyze. In fact the best bound we have on the performance of this algorithm is $O({\log }^{2}k)$$O({\log }^{2}k)$O(log^(2)k)O(\log ^{2} k) (note that the corresponding bound for Steiner Tree tree is $O(\log k)$$O(\log k)$O(log k)O(\log k)) while the lower bound on its peformance is only $\mathrm{\Omega }(\log k)$$\mathrm{\Omega }(\log k)$Omega(log k)\Omega(\log k). The analysis of the upper bound requires appealing to certain extremal results ^[2] and closing the gap between the upper and lower bound on the analysis of this simplest of greedy algorithms is a very interesting open problem.

The first constant factor approximation for Steiner Forest is due to the influential work of Agarwal, Klein and Ravi ^[3] who gave a primal-dual 2-approximation which is still the best known. Their primal-dual algorithm has since been generalized for a wide variety of network design problems via the work of Goemans and Williamson (see their survey ^[4]) and several others. Steiner Forest has the advantage that one can visualize the algorithm and analysis more easily when compared to the more abstract settings that we will see shortly.

We now describe an integer programming formulation for the problem. In the IP we will have a variable $x_e$$x_e$x_(e)x_{e} for each edge $e\in E$$e\in E$e in Ee \in E such that $x_e$$x_e$x_(e)x_{e} is $1$$1$11 if and only if $e$$e$ee is part of the solution. Let the set $\mathcal{S}$$\mathcal{S}$S\mathcal{S} be the collection of all sets $S\subset V$$S\subset V$S sub VS \subset V such that $|S\cap \{s_i,t_i\}|=1$$\left|S\cap \left\{s_i,t_i\right\}\right|=1$|S nn{s_(i),t_(i)}|=1\left|S \cap\left\{s_{i}, t_{i}\right\}\right|=1 for some $1\le i\le k$$1\le i\le k$1 <= i <= k1 \leq i \leq k. For a set $S\subset V$$S\subset V$S sub VS \subset V let $\delta (S)$$\delta (S)$delta(S)\delta(S) denote the set of edges crossing the cut $(S,V\mathrm{\setminus }S)$$(S,V\mathrm{\setminus }S)$(S,V\\S)(S, V \backslash S). The IP can be written as the following.

We can obtain an LP-relaxation by changing the constraint that $x_e\in \{0,1\}$$x_e\in \{0,1\}$x_(e)in{0,1}x_{e} \in\{0,1\} to $x_e\ge 0$$x_e\ge 0$x_(e) >= 0x_{e} \geq 0. The dual of the LP-relaxation can be written as the following.

Before we continue, some definitions will be stated which will help to define our algorithm for the problem.

Definition 11.1. Given a set of edges $X\subseteq E$$X\subseteq E$X sube EX \subseteq E, a set $S\in \mathcal{S}$$S\in \mathcal{S}$S inSS \in \mathcal{S} is violated with respect to $X$$X$XX if $\delta (S)\cap X=\mathrm{\varnothing }$$\delta (S)\cap X=\mathrm{\varnothing }$delta(S)nn X=O/\delta(S) \cap X=\emptyset. In other words $S$$S$SS is violated even with edge set $X$$X$XX included.

Definition 11.2. Given a set of edges $X\subseteq E$$X\subseteq E$X sube EX \subseteq E, a set $S\in \mathcal{S}$$S\in \mathcal{S}$S inSS \in \mathcal{S} is minimally violated with respect to $X$$X$XX if $S$$S$SS is violated with respect to $X$$X$XX and there is no $S^{\mathrm{\prime }}\subset S$$S^{\mathrm{\prime }}\subset S$S^(')sub SS^{\prime} \subset S that is also violated with respect to $X$$X$XX.

Next we show that any two minimally violated sets are disjoint.

Claim 11.0.1. $\mathrm{\forall }X\subseteq E$$\mathrm{\forall }X\subseteq E$AA X sube E\forall X \subseteq E if $S$$S$SS and $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} are minimally violated sets then $S\cap S^{\mathrm{\prime }}=\mathrm{\varnothing }$$S\cap S^{\mathrm{\prime }}=\mathrm{\varnothing }$S nnS^(')=O/S \cap S^{\prime}=\emptyset, i.e. $S$$S$SS and $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} are disjoint.

In fact we will prove the following claim which implies the preceding one.

Claim 11.0.2. Let $X\subseteq E$$X\subseteq E$X sube EX \subseteq E. The minimially violated sets with respect to $X$$X$XX are the connected components of the graph $(V,X)$$(V,X)$(V,X)(V, X) that are violated with respect to $X$$X$XX.

Proof. Consider a minimal violated set $S$$S$SS. We may assume the set $S$$S$SS contains $s_i$$s_i$s_(i)s_{i} but not $t_i$$t_i$t_(i)t_{i} for some $i$$i$ii. If $S$$S$SS is not a connected component of $(V,X)$$(V,X)$(V,X)(V, X) then there must be some connected component $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} of $G[S]$$G[S]$G[S]G[S] that contains $s_i$$s_i$s_(i)s_{i}. But ${\delta }_X\left(S^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$${\delta }_X\left(S^{\mathrm{\prime }}\right)=\mathrm{\varnothing }$delta_(X)(S^('))=O/\delta_{X}\left(S^{\prime}\right)=\emptyset, and hence $S^{\mathrm{\prime }}$$S^{\mathrm{\prime }}$S^(')S^{\prime} is violated; this contradicts the fact that $S$$S$SS is minimal. Therefore, if a set $S$$S$SS is a minimal violated set then it must be connected in the graph $(V,X)$$(V,X)$(V,X)(V, X).

Now suppose that $S$$S$SS is a connected component of $(V,X)$$(V,X)$(V,X)(V, X); it is easy to see that no proper subset of $S$$S$SS can be violated since some edge will cross any such set. Thus, if $S$$S$SS is a violated set then it is minimal violated set.

Thus, the minimal violated sets with respect to $X$$X$XX are the conected components of the graph $(V,X)$$(V,X)$(V,X)(V, X) that are themselves violated sets. It follows that any two distinct minimal violated sets are disjoint.

The primal-dual algorithm for Steiner Forest is described below.

The first thing to notice about the algorithm above is that it is closely related to our solution to the Vertex Cover problem, however, there are two main differences. In the Vertex Cover we raised the dual variables for all uncovered edges uniformly, however, in this algorithm we were more careful on which dual variables are raised. In this algorithm, we chose to only raise the variables which correspond to the minimally violated sets. Unlike the case of Steiner Tree, in Steiner Forest, there can be non-trivial connected components that are not violated and hence become inactive. A temporarily inactive component may become part of an active component later if an active component merges with it. The other main difference is that when we finally output the solution, we prune $F$$F$FF to get $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime}. This is done for technical reasons, but the intuition is that we should include no edge in the solution which is not needed to obtain a feasible solution. To understand this algorithm, there is a non-trivial example in the textbook ^[5] that demonstrates the algorithm's finer points.

Lemma 11.1. At the end of the algorithm, $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime} and $\mathbf{y}$$\mathbf{y}$y\mathbf{y} are primal and dual feasible solutions, respectively.

Proof. In each iteration of the while loop, only the dual variables corresponding to connected components were raised. Therefore, no edge that is contained within the same component can become tight, and, therefore, $F$$F$FF is acyclic. To see that none of the dual constraints are violated, observe that when a constraint becomes tight (that is, it holds with equality), the corresponding edge $e$$e$ee is added to $F$$F$FF. Subsequently, since $e$$e$ee is contained in some connected component of $F$$F$FF, no set $S$$S$SS with $e\in \delta (S)$$e\in \delta (S)$e in delta(S)e \in \delta(S) ever has $y_S$$y_S$y_(S)y_{S} raised. Therefore, the constraint for $e$$e$ee cannot be violated, and so $\mathrm{y}$$\mathrm{y}$y\mathrm{y} is dual feasible.

As long as $F$$F$FF is not feasible, the while loop will not terminate, and there are some minimal violated sets that can have their dual variables raised. Therefore, at the end of the algorithm $F$$F$FF is feasible. Moreover, since $F$$F$FF is acyclic (it is a forest), there is a unique $s_i-t_i$$s_i-t_i$s_(i)-t_(i)s_{i}-t_{i} path in $F$$F$FF for each $1\le i\le k$$1\le i\le k$1 <= i <= k1 \leq i \leq k. Thus, each edge on a $s_i-t_i$$s_i-t_i$s_(i)-t_(i)s_{i}-t_{i} path is not redundant and is not deleted when pruning $F$$F$FF to get $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime}.

Theorem 11.3. The primal-dual algorithm for Steiner Forest gives a $2$$2$22-approximation.

Proof. Let $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime} be the output from our algorithm. To prove this theorem, we want to show that $c\left(F^{\mathrm{\prime }}\right)\le 2\sum _{s\in \mathcal{S}}{y}_S$$c\left(F^{\mathrm{\prime }}\right)\le 2\sum _{s\in \mathcal{S}} y_S$c(F^(')) <= 2sum_(s inS)y_(S)c\left(F^{\prime}\right) \leq 2 \sum_{s \in \mathcal{S}} y_{S} where $y_S$$y_S$y_(S)y_{S} is the feasible dual constructed by the algorithm. It follows from this that the algorithm is in fact a 2-approximation. First, we know that $c\left(F^{\mathrm{\prime }}\right)=\sum _{e\in F^{\mathrm{\prime }}}{c}_e=\sum _{e\in F^{\mathrm{\prime }}}\sum _{S\in \mathcal{S}:e\in \delta (S)}{y}_s$$c\left(F^{\mathrm{\prime }}\right)=\sum _{e\in F^{\mathrm{\prime }}} c_e=\sum _{e\in F^{\mathrm{\prime }}} \sum _{S\in \mathcal{S}:e\in \delta (S)} y_s$c(F^('))=sum_(e inF^('))c_(e)=sum_(e inF^('))sum_(S inS:e in delta(S))y_(s)c\left(F^{\prime}\right)=\sum_{e \in F^{\prime}} c_{e}=\sum_{e \in F^{\prime}} \sum_{S \in \mathcal{S}: e \in \delta(S)} y_{s} because every edge picked is tight. Let ${\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$${\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$deg_(F^('))(S)\operatorname{deg}_{F^{\prime}}(S) denote the number of edges of $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime} that cross the cut $(S,V\mathrm{\setminus }S)$$(S,V\mathrm{\setminus }S)$(S,V\\S)(S, V \backslash S). It can be seen that $\sum _{e\in F^{\mathrm{\prime }}}\sum _{S\in \mathcal{S}:e\in \delta (S)}{y}_s=\sum _{s\in \mathcal{S}}{y}_S{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$$\sum _{e\in F^{\mathrm{\prime }}} \sum _{S\in \mathcal{S}:e\in \delta (S)} y_s=\sum _{s\in \mathcal{S}} y_S{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$sum_(e inF^('))sum_(S inS:e in delta(S))y_(s)=sum_(s inS)y_(S)deg_(F^('))(S)\sum_{e \in F^{\prime}} \sum_{S \in \mathcal{S}: e \in \delta(S)} y_{s}=\sum_{s \in \mathcal{S}} y_{S} \operatorname{deg}_{F^{\prime}}(S).

Let $A_i$$A_i$A_(i)A_{i} contain the minimally violated sets in iteration $i$$i$ii and let ${\mathrm{\Delta }}_i$${\mathrm{\Delta }}_i$Delta_(i)\Delta_{i} denote the amount of dual growth in the $i$$i$ii th iteration. Say that our algorithm runs for $\alpha$$\alpha$alpha\alpha iterations. We can then rewrite $\sum _{s\in \mathcal{S}}{y}_S{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$$\sum _{s\in \mathcal{S}} y_S{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$sum_(s inS)y_(S)deg_(F^('))(S)\sum_{s \in \mathcal{S}} y_{S} \operatorname{deg}_{F^{\prime}}(S) as the double summation $\sum _{i=1}^{\alpha }\sum _{S\in A_i}{\mathrm{\Delta }}_i{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$$\sum _{i=1}^{\alpha } \sum _{S\in A_i} {\mathrm{\Delta }}_i{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$sum_(i=1)^(alpha)sum_(S inA_(i))Delta_(i)deg_(F^('))(S)\sum_{i=1}^{\alpha} \sum_{S \in A_{i}} \Delta_{i} \operatorname{deg}_{F^{\prime}}(S). In the next lemma it will be shown for any iteration $i$$i$ii that $\sum _{S\in A_i}{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)\le 2\left|A_i\right|$$\sum _{S\in A_i} {\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)\le 2\left|A_i\right|$sum_(S inA_(i))deg_(F^('))(S) <= 2|A_(i)|\sum_{S \in A_{i}} \operatorname{deg}_{F^{\prime}}(S) \leq 2\left|A_{i}\right|. Knowing this we can prove the theorem:

Now we show the lemma used in the previous theorem. It is in this lemma that we use the fact that we prune $F$$F$FF to get $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime}.

We need a simple claim.

Lemma 11.2. Let $T=(V,E)$$T=(V,E)$T=(V,E)T=(V, E) be a tree/forest and let $\mathrm{Z}\subseteq V$$\mathrm{Z}\subseteq V$Zsube V\mathrm{Z} \subseteq V be a subset of the nodes such that every leaf of $T$$T$TT is in $Z$$Z$ZZ. Then $\sum _{v\in Z}{\mathrm{deg}}_T(v)\le 2|Z|-2$$\sum _{v\in Z} {\mathrm{deg}}_T(v)\le 2|Z|-2$sum_(v in Z)deg_(T)(v) <= 2|Z|-2\sum_{v \in Z} \operatorname{deg}_{T}(v) \leq 2|Z|-2 where ${\mathrm{deg}}_T(v)$${\mathrm{deg}}_T(v)$deg_(T)(v)\operatorname{deg}_{T}(v) is the degree of $v$$v$vv in $T$$T$TT.

Proof. We will prove it for a tree. We have $\sum _{v\in V}{\mathrm{deg}}_T(V)=2|V|-2$$\sum _{v\in V} {\mathrm{deg}}_T(V)=2|V|-2$sum_(v in V)deg_(T)(V)=2|V|-2\sum_{v \in V} \operatorname{deg}_{T}(V)=2|V|-2 since a tree has $|V|-1$$|V|-1$|V|-1|V|-1 edges. Every node $u\in V-Z$$u\in V-Z$u in V-Zu \in V-Z has degree at least 2 since it is not a leaf. Thus $\sum _{u\in V-Z}{\mathrm{deg}}_T(u)\ge 2|V-Z|$$\sum _{u\in V-Z} {\mathrm{deg}}_T(u)\ge 2|V-Z|$sum_(u in V-Z)deg_(T)(u) >= 2|V-Z|\sum_{u \in V-Z} \operatorname{deg}_{T}(u) \geq 2|V-Z|. Thus,

Lemma 11.3. For any iteration $i$$i$ii of our algorithm, $\sum _{s\in A_i}{\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)\le 2\left|A_i\right|-2$$\sum _{s\in A_i} {\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)\le 2\left|A_i\right|-2$sum_(s inA_(i))deg_(F^('))(S) <= 2|A_(i)|-2\sum_{s \in A_{i}} \operatorname{deg}_{F^{\prime}}(S) \leq 2\left|A_{i}\right|-2.

Proof. Consider the graph $(V,F^{\mathrm{\prime }})$$\left(V,F^{\mathrm{\prime }}\right)$(V,F^('))\left(V, F^{\prime}\right), and fix an iteration $i$$i$ii. In this graph, contract each set $S$$S$SS active in iteration $i$$i$ii to a single node (call such a node an active node), and each inactive set to a single node. Let the resulting graph be denoted by $H$$H$HH. We know that $F$$F$FF is a forest and we have contracted connected subsets of vertices in $F$$F$FF; as $F^{\mathrm{\prime }}\subseteq F$$F^{\mathrm{\prime }}\subseteq F$F^(')sube FF^{\prime} \subseteq F, we conclude that $H$$H$HH is also a forest.

Claim 11.0.3. Every leaf of $H$$H$HH is an active node.

Proof. If not, consider leaf node $v$$v$vv of $H$$H$HH which is an inactive node and let $e\in F^{\mathrm{\prime }}$$e\in F^{\mathrm{\prime }}$e inF^(')e \in F^{\prime} be the edge incident to it. We claim that $F^{\mathrm{\prime }}-e$$F^{\mathrm{\prime }}-e$F^(')-eF^{\prime}-e is feasible which would contradict the minimality of $F^{\mathrm{\prime }}$$F^{\mathrm{\prime }}$F^(')F^{\prime}. To see this, if $x,y$$x,y$x,yx, y are two nodes in $H$$H$HH where $v\ne x,v\ne y$$v\ne x,v\ne y$v!=x,v!=yv \neq x, v \neq y then $x$$x$xx and $y$$y$yy are connected also in $H-e$$H-e$H-eH-e since $v$$v$vv is a leaf. Thus the utility of $e$$e$ee is to connect $v$$v$vv to other nodes in $H$$H$HH but if this is the case $v$$v$vv would be an active node at the start of the iteration which is not the case.

The degree in $H$$H$HH of an active node corresponding to violated set $S$$S$SS is ${\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$${\mathrm{deg}}_{F^{\mathrm{\prime }}}(S)$deg_(F^('))(S)\operatorname{deg}_{F^{\prime}}(S). Now we apply Lemma 11.2.