Approximation Algorithms: Primal Dual for Constrained Forest Problems

This is the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 12: Primal Dual for Constrained Forest Problems. You can read Chapter 13: Survivable Network Design Problem, here. Chapter 11: Steiner Forest Problem, here.
Chapter 12
We previously saw a primal-dual based 2-approximation for the Steiner Forest problem. The algorithm can be generalized to a much wider class of problems that involve finding a min-cost forest in an undirected edge-weighted graph that needs to satisfy some constraint. The resulting machinery is a more abstract and requires more advanced tools. We start with some problems all of which are NP-Hard.
Point to point connection problem: Given edge-weighted graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and two disjoint sets X = { s 1 , , s k } X = s 1 , , s k X={s_(1),dots,s_(k)}X=\left\{s_{1}, \ldots, s_{k}\right\} and Y = { t 1 , , t k } Y = t 1 , , t k Y={t_(1),dots,t_(k)}Y=\left\{t_{1}, \ldots, t_{k}\right\} of terminals find the min-cost forest in G G GG such that each connected component contains same number of terminals from X X XX and Y Y YY.
Lower Capacitated Tree Problem: Given G = ( V , E ) , c : E R + G = ( V , E ) , c : E R + G=(V,E),c:E rarrR^(+)G=(V, E), c: E \rightarrow \mathbb{R}^{+} and a k Z + k Z + k inZ^(+)k \in \mathbb{Z}^{+} find a set E E E E E^(')sube EE^{\prime} \subseteq E of minimum cost such that every connected component in ( V , E ) V , E (V,E^('))\left(V, E^{\prime}\right) has at least k k kk edges.
Connectivity Augmentation: Given an undirected k k kk-edge connected graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and a set of edges E aug V × V E E aug  V × V E E^("aug ")sube V xx V-EE^{\text {aug }} \subseteq V \times V-E, find a set E E aug E E aug  E^(')subeE^("aug ")E^{\prime} \subseteq E^{\text {aug }} of minimum cost such that G = ( V , E E ) G = V , E E G=(V,E uuE^('))G=\left(V, E \cup E^{\prime}\right) is ( k + 1 ) ( k + 1 ) (k+1)(k+1)-edge connected.
Steiner Connectivity Augmentation: Let G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) be an edge-weighted graphs and let ( s 1 , t 1 ) , , ( s h , t h ) s 1 , t 1 , , s h , t h (s_(1),t_(1)),dots,(s_(h),t_(h))\left(s_{1}, t_{1}\right), \ldots,\left(s_{h}, t_{h}\right) be k k kk pairs such that each pair is k k kk-edgeconnected in G G GG. Given a set of edges E aug V × V E E aug  V × V E E^("aug ")sube V xx V-EE^{\text {aug }} \subseteq V \times V-E, find a set E E aug E E aug  E^(')subeE^("aug ")E^{\prime} \subseteq E^{\text {aug }} of minimum cost such that in G = ( V , E E ) G = V , E E G^(')=(V,E uuE^('))G^{\prime}=\left(V, E \cup E^{\prime}\right) each pair ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) is ( k + 1 ) ( k + 1 ) (k+1)(k+1)-edge connected.
Each of the preceding problems can be cast as a special case of the following abstract problem. Given an edge-weighted graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and a function f : 2 V { 0 , 1 } f : 2 V { 0 , 1 } f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\}, find a min-cost subset of edges E E E^(')E^{\prime} such that | δ E ( S ) | f ( S ) δ E ( S ) f ( S ) |delta_(E^('))(S)| >= f(S)\left|\delta_{E^{\prime}}(S)\right| \geq f(S) for each S V S V S sube VS \subseteq V. We use the notation δ F ( S ) δ F ( S ) delta_(F)(S)\delta_{F}(S) to denote the edges from an edge set F F FF that cross the set/cut S S SS. Alternatively we want a min-cost subset of edges E E E^(')E^{\prime} such that each set S S S S S inSS \in \mathcal{S} is crossed by an edge of E E E^(')E^{\prime} where S = { S f ( S ) = 1 } S = { S f ( S ) = 1 } S={S∣f(S)=1}\mathcal{S}=\{S \mid f(S)=1\}. It is easy to observe that a minimal solution to this abstract problem is a forest since any cut needs to be covered at most once. This formulation is too general since f f ff may be completely arbitrary. The goal is to find a sufficiently general class that captures interesting problems while still being tractable. The advantage of { 0 , 1 } { 0 , 1 } {0,1}\{0,1\} functions is precisely because the minimal solutions are forests. We will later consider integer valued functions.
Definition 12.1. Given a graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and an integer valued function f : 2 V Z f : 2 V Z f:2^(V)rarrZf: 2^{V} \rightarrow \mathbb{Z} we say that a susbet of edges F F FF is feasible for f f ff or covers f f ff iff | δ F ( S ) | f ( S ) δ F ( S ) f ( S ) |delta_(F)(S)| >= f(S)\left|\delta_{F}(S)\right| \geq f(S) for all S V S V S sube VS \subseteq V.
Remark 12.1. Even though it may seem natural to restrict attention to requirement functions that only have non-negative entries, we will see later that the flexibility of negative requirements is useful.
Given a network design problem Π Π Pi\Pi in an undirected graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and an integer valued function f : 2 V Z + f : 2 V Z + f:2^(V)rarrZ_(+)f: 2^{V} \rightarrow \mathbb{Z}_{+} we say that the requirement function of Π Π Pi\Pi is f f ff if covering f f ff is equivalent to satisfing the constraints of Π Π Pi\Pi.

12.1 Classes of Functions and Setup

Here we consider classes of requirement functions f : 2 V Z f : 2 V Z f:2^(V)rarrZf: 2^{V} \rightarrow \mathbb{Z} and their relationship. Even though we define more generally, for this chapter the focus will be on { 0 , 1 } { 0 , 1 } {0,1}\{0,1\} functions.
Definition 12.2. f f ff is maximal if for all disjoint A A AA and B B BB we have f ( A B ) f ( A B ) f(A uu B) <=f(A \cup B) \leq max { f ( A ) , f ( B ) } max { f ( A ) , f ( B ) } max{f(A),f(B)}\max \{f(A), f(B)\}.
Exercise 12.1. Prove that the requirement function of Steiner Forest is maximal.
Definition 12.3. f f ff is proper if it is symmetric, maximal and f ( V ) = 0 f ( V ) = 0 f(V)=0f(V)=0.
Exercise 12.2. Prove that the requirement function of Steiner Forest is proper.
Exercise 12.3. Prove that the requirement function Steiner Connectivity Augmentation is proper.
Definition 12.4. f f ff is downward monotone if f ( A ) f ( B ) f ( A ) f ( B ) f(A) <= f(B)f(A) \leq f(B) for all B A B A O/!=B sub A\emptyset \neq B \subset A.
Exercise 12.4. Prove that the requirement function of the Lower Capacitated Tree problem as downward monotone.
A very general class is the one given below.
Definition 12.5. f f ff is skew-supermodular (also called weakly-supermodular) if for all A A AA and B B BB one of the following conditions hold,
1. f ( A ) + f ( B ) f ( A B ) + f ( A B ) f ( A ) + f ( B ) f ( A B ) + f ( A B ) f(A)+f(B) <= f(A uu B)+f(A nn B)f(A)+f(B) \leq f(A \cup B)+f(A \cap B)
2. f ( A ) + f ( B ) f ( A B ) + f ( B A ) f ( A ) + f ( B ) f ( A B ) + f ( B A ) f(A)+f(B) <= f(A-B)+f(B-A)f(A)+f(B) \leq f(A-B)+f(B-A)
A specialization of skew-supermodular for { 0 , 1 } { 0 , 1 } {0,1}\{0,1\} functions will be the focus of this chapter.
Definition 12.6. A { 0 , 1 } { 0 , 1 } {0,1}\{0,1\} valued f f ff is uncrossable if for all A A AA and B B BB such that f ( A ) f ( A ) f(A)f(A) and f ( B ) = 1 f ( B ) = 1 f(B)=1f(B)=1, one of the following conditions hold,
1. f ( A B ) = 1 f ( A B ) = 1 f(A uu B)=1f(A \cup B)=1 and f ( A B ) = 1 f ( A B ) = 1 f(A nn B)=1f(A \cap B)=1
2. f ( A B ) = 1 f ( A B ) = 1 f(A-B)=1f(A-B)=1 and f ( B A ) = 1 f ( B A ) = 1 f(B-A)=1f(B-A)=1.
Claim 12.1.1. If f f ff is downward monotone then it is skew-supermodular.
Proof. Since f f ff is downward monotone, A B A A B A A-B sub AA-B \subset A and B A B B A B B-A sub BB-A \subset B we get:
f ( A ) f ( A B ) f ( B ) f ( B A ) f ( A ) f ( A B ) f ( B ) f ( B A ) {:[f(A) <= f(A-B)],[f(B) <= f(B-A)]:}\begin{aligned} &f(A) \leq f(A-B) \\ &f(B) \leq f(B-A) \end{aligned}
and hence the second condition of skew-supermodularity always holds.
Lemma 12.1. If f f ff is proper then it is skew-supermodular.
Proof. Consider two sets A , B A , B A,BA, B. By considering A A AA as disjoint union of A B A B A-BA-B and A B A B A nn BA \cap B we have ( i ) f ( A ) max { f ( A B ) , f ( A B ) } ( i ) f ( A ) max { f ( A B ) , f ( A B ) } (i)f(A) <= max{f(A-B),f(A nn B)}(i) f(A) \leq \max \{f(A-B), f(A \cap B)\}. Similarly (ii) f ( B ) f ( B ) f(B) <=f(B) \leq max { f ( B A ) , f ( A B ) } max { f ( B A ) , f ( A B ) } max{f(B-A),f(A nn B)}\max \{f(B-A), f(A \cap B)\}.
Now we apply symmetry of f f ff and note that f ( A ) = f ( V A ) f ( A ) = f ( V A ) f(A)=f(V-A)f(A)=f(V-A). Write V A V A V-AV-A as disjoint union of B A B A B-AB-A and V ( A B ) V ( A B ) V-(A uu B)V-(A \cup B). Hence (iii) f ( A ) = f ( V A ) f ( A ) = f ( V A ) f(A)=f(V-A) <=f(A)=f(V-A) \leq max { f ( B A ) , f ( V ( A B ) } = max { f ( B A ) , f ( A B ) } max { f ( B A ) , f ( V ( A B ) } = max { f ( B A ) , f ( A B ) } max{f(B-A),f(V-(A uu B)}=max{f(B-A),f(A uu B)}\max \{f(B-A), f(V-(A \cup B)\}=\max \{f(B-A), f(A \cup B)\} where we used symmetry of f f ff in the second equality. Similary, (iv) f ( B ) max { f ( A B ) , f ( A B } f ( B ) max { f ( A B ) , f ( A B } f(B) <= max{f(A-B),f(A uu B}f(B) \leq \max \{f(A-B), f(A \cup B\}.
Summing up the four inequalities and replacing max { x , y } max { x , y } max{x,y}\max \{x, y\} by ( x + y ) / 2 ( x + y ) / 2 (x+y)//2(x+y) / 2 we obtain
2 ( f ( A ) + f ( B ) ) f ( A B ) + f ( B A ) + f ( A B ) + f ( A B ) 2 ( f ( A ) + f ( B ) ) f ( A B ) + f ( B A ) + f ( A B ) + f ( A B ) 2(f(A)+f(B)) <= f(A-B)+f(B-A)+f(A nn B)+f(A uu B)2(f(A)+f(B)) \leq f(A-B)+f(B-A)+f(A \cap B)+f(A \cup B)
which implies that f ( A ) + f ( B ) f ( A B ) + f ( B A ) f ( A ) + f ( B ) f ( A B ) + f ( B A ) f(A)+f(B) <= f(A-B)+f(B-A)f(A)+f(B) \leq f(A-B)+f(B-A) or f ( A ) + f ( B ) f ( A f ( A ) + f ( B ) f ( A f(A)+f(B) <= f(A nnf(A)+f(B) \leq f(A \cap B ) + f ( A B ) B ) + f ( A B ) B)+f(A uu B)B)+f(A \cup B).
Definition 12.7. Let G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) and f : 2 V Z f : 2 V Z f:2^(V)rarrZf: 2^{V} \rightarrow \mathbb{Z}. For each X E X E X sube EX \subseteq E, the residual requirement function f X : 2 V Z f X : 2 V Z f_(X):2^(V)rarrZf_{\mathrm{X}}: 2^{V} \rightarrow \mathbb{Z} is defined as:
f X ( A ) = f ( A ) | δ X ( A ) | . f X ( A ) = f ( A ) δ X ( A ) . f_(X)(A)=f(A)-|delta_(X)(A)|.f_{X}(A)=f(A)-\left|\delta_{X}(A)\right| .
Exercise 12.5. Let g : 2 V R g : 2 V R g:2^(V)rarrRg: 2^{V} \rightarrow \mathbb{R} be a symmetric submodular function. Prove that g g gg satisfies posi-modularity:
g ( A ) + g ( B ) g ( A B ) + g ( B A ) A , B V . g ( A ) + g ( B ) g ( A B ) + g ( B A ) A , B V . g(A)+g(B) >= g(A-B)+g(B-A)quad AA A,B sube V.g(A)+g(B) \geq g(A-B)+g(B-A) \quad \forall A, B \subseteq V .
Lemma 12.2. If f f ff is skew-supermodular then f X f X f_(X)f_{\mathrm{X}} is also skew-supermodular for any X E X E X sube EX \subseteq E.
Proof. The function | δ X ( . ) | δ X ( . ) |delta_(X)(.)|\left|\delta_{X}(.)\right| is submodular. Hence
| δ X ( A ) | + | δ X ( B ) | | δ X ( A B ) | + | δ X ( B A ) | A , B V . δ X ( A ) + δ X ( B ) δ X ( A B ) + δ X ( B A ) A , B V . |delta_(X)(A)|+|delta_(X)(B)| >= |delta_(X)(A nn B)|+|delta_(X)(B uu A)|quad AA A,B sube V.\left|\delta_{X}(A)\right|+\left|\delta_{X}(B)\right| \geq\left|\delta_{X}(A \cap B)\right|+\left|\delta_{X}(B \cup A)\right| \quad \forall A, B \subseteq V .
The function is also symmetric and hence also satisfies posi-modularity. Therefore,
| δ X ( A ) | + | δ X ( B ) | | δ X ( A B ) | + | δ X ( B A ) | A , B V . δ X ( A ) + δ X ( B ) δ X ( A B ) + δ X ( B A ) A , B V . |delta_(X)(A)|+|delta_(X)(B)| >= |delta_(X)(A-B)|+|delta_(X)(B-A)|quad AA A,B sube V.\left|\delta_{X}(A)\right|+\left|\delta_{X}(B)\right| \geq\left|\delta_{X}(A-B)\right|+\left|\delta_{X}(B-A)\right| \quad \forall A, B \subseteq V .
Now consider the function f X f X f_(X)f_{X} and let A , B A , B A,BA, B be any two subsets of V V VV. Suppose f ( A ) + f ( B ) f ( A B ) + f ( A B ) f ( A ) + f ( B ) f ( A B ) + f ( A B ) f(A)+f(B) >= f(A uu B)+f(A nn B)f(A)+f(B) \geq f(A \cup B)+f(A \cap B). Then
f X ( A ) + f X ( A ) = f ( A ) | δ X ( A ) | + f ( B ) | δ X ( B ) | f ( A B ) + f ( A B ) ( | δ X ( A ) + | δ X ( B ) f ( A B ) + f ( A B ) ( | δ X ( A B ) | + | δ X ( B A ) | = f X ( A B ) + f X ( A B ) . f X ( A ) + f X ( A ) = f ( A ) δ X ( A ) + f ( B ) δ X ( B ) f ( A B ) + f ( A B ) δ X ( A ) + δ X ( B ) f ( A B ) + f ( A B ) δ X ( A B ) + δ X ( B A ) = f X ( A B ) + f X ( A B ) . {:[f_(X)(A)+f_(X)(A)=f(A)-|delta_(X)(A)|+f(B)-|delta_(X)(B)|],[ >= f(A uu B)+f(A nn B)-(|delta_(X)(A)+|delta_(X)(B)∣:}],[ >= f(A uu B)+f(A nn B)-(|delta_(X)(A nn B)|+|delta_(X)(B uu A)|:}],[=f_(X)(A uu B)+f_(X)(A nn B).]:}\begin{aligned} f_{X}(A)+f_{X}(A) &=f(A)-\left|\delta_{X}(A)\right|+f(B)-\left|\delta_{X}(B)\right| \\ & \geq f(A \cup B)+f(A \cap B)-\left(\left|\delta_{X}(A)+\right| \delta_{X}(B) \mid\right.\\ & \geq f(A \cup B)+f(A \cap B)-\left(\left|\delta_{X}(A \cap B)\right|+\left|\delta_{X}(B \cup A)\right|\right.\\ &=f_{X}(A \cup B)+f_{X}(A \cap B) . \end{aligned}
Similarly, if f ( A ) + f ( B ) f ( A B ) + f ( B A ) f ( A ) + f ( B ) f ( A B ) + f ( B A ) f(A)+f(B) >= f(A-B)+f(B-A)f(A)+f(B) \geq f(A-B)+f(B-A) we can use posi-modularity of | δ X ( ) | δ X ( ) |delta_(X)(*)|\left|\delta_{X}(\cdot)\right| to argue that f X ( A ) + f X ( B ) f X ( A B ) + f X ( B A ) f X ( A ) + f X ( B ) f X ( A B ) + f X ( B A ) f_(X)(A)+f_(X)(B) >= f_(X)(A-B)+f_(X)(B-A)f_{X}(A)+f_{X}(B) \geq f_{X}(A-B)+f_{X}(B-A). We note that | δ X | δ X |delta_(X)|\left|\delta_{X}\right| is both submodular and posi-modular which allows us to use the right inequality.
Remark 12.2. Allowing allow negative requirements in the definitoin of skewsupermodularity allows a clean proof when subtracting | δ X ( ) | δ X ( ) |delta_(X)(*)|\left|\delta_{X}(\cdot)\right|.
In the case of { 0 , 1 } { 0 , 1 } {0,1}\{0,1\} functions we make the following claim and leave the proof as an exercise which is similar to the the one above.
Lemma 12.3. Let f : 2 V { 0 , 1 } f : 2 V { 0 , 1 } f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\} be an uncrossable function and let X E X E X sube EX \subseteq E. Let h : 2 V { 0 , 1 } h : 2 V { 0 , 1 } h:2^(V)rarr{0,1}h: 2^{V} \rightarrow\{0,1\} be the residular function where h ( S ) = 1 h ( S ) = 1 h(S)=1h(S)=1 iff | δ X ( S ) | = 0 δ X ( S ) = 0 |delta_(X)(S)|=0\left|\delta_{X}(S)\right|=0. Then h h hh is uncrossable.
Definition 12.8. Let f f ff be a { 0 , 1 } a { 0 , 1 } a{0,1}a\{0,1\} requirement function over V V VV and let X E X E X sube EX \subseteq E. A set S S SS is violated with respect to X X XX if f X ( S ) = 1 f X ( S ) = 1 f_(X)(S)=1f_{X}(S)=1 (in other words S S SS is not yet covered by the edge set X X XX). A set S S SS is a minimal violated set if there is no S S S S S^(')⊊SS^{\prime} \subsetneq S such that S S S^(')S^{\prime} is violated.
Lemma 12.4. Let f f ff be an uncrossable function and X E X E X sube EX \subseteq E, then the minimial violated sets of f f ff with respect to X X XX are disjoint. That is, if A , B A , B A,BA, B are minimal violated sets then A = B A = B A=BA=B or A B = A B = A nn B=O/A \cap B=\emptyset.
Proof. Since f X f X f_(X)f_{\mathrm{X}} is also uncrossable it sufficies to consider minimal violated sets A , B A , B A,BA, B with respect to f f ff (hence the empty set of edges). Suppose the property does not hold. Then we can assume that A , B A , B A,BA, B propertly cross, that is, A B , A B , B A A B , A B , B A A-B,A nn B,B-AA-B, A \cap B, B-A are all non-empty. We have f ( A ) = f ( B ) = 1 f ( A ) = f ( B ) = 1 f(A)=f(B)=1f(A)=f(B)=1 since both are violated. Since f f ff is uncrossable, we have f ( A B ) = f ( B A ) = 1 f ( A B ) = f ( B A ) = 1 f(A-B)=f(B-A)=1f(A-B)=f(B-A)=1 or f ( A B ) = f ( A B ) = 1 f ( A B ) = f ( A B ) = 1 f(A nn B)=f(A uu B)=1f(A \cap B)=f(A \cup B)=1. In both cases we see that we violate minimality of A , B A , B A,BA, B.

12.2 A Primal-Dual Algorithm for Covering Uncrossable Functions

In this section we consider the following problem. Given a graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) with non-negative edge weights c : E R + c : E R + c:E rarrR_(+)c: E \rightarrow \mathbb{R}_{+}and a uncrossable function f : 2 V { 0 , 1 } f : 2 V { 0 , 1 } f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\} find a min-cost set of edges F E F E F sube EF \subseteq E such that | δ F ( S ) | f ( S ) δ F ( S ) f ( S ) |delta_(F)(S)| >= f(S)\left|\delta_{F}(S)\right| \geq f(S) for all S S SS. An important computational issue is how f f ff is specified. A natural model is to consider the value oracle one where we have access to f ( S ) f ( S ) f(S)f(S) via an oracle. Given S V S V S sube VS \subseteq V, the oracle returns f ( S ) f ( S ) f(S)f(S). However this is not sufficient in the general context of uncrossable functions as we see from the following example. Fix some set A A AA. Define the function f A f A f_(A)f_{A} where f A ( S ) = 1 f A ( S ) = 1 f_(A)(S)=1f_{A}(S)=1 iff S = A S = A S=AS=A. It is easy to see that there is a feasible solution iff δ E ( A ) δ E ( A ) delta_(E)(A)!=O/\delta_{E}(A) \neq \emptyset. How do we even verify that there is a feasible solution via a value oracle? In general it may take an exponential number of queries to find A A AA. Hence we need more. We will assume that there is an oracle that given G G GG and X E X E X sube EX \subseteq E outputs the set of all minimal violated sets of f X f X f_(X)f_{X}. This will typically be easy to ensure for specific functions of interest. We note that for some special class of functions such as proper functions, a value oracle suffices to find the minimal violated sets.
We write the primal and dual LPs for covering f f ff via edges of a given graph G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E).
min e E c e x e such that e δ ( S ) x e f ( S ) S V x e 0 e E min e E c e x e such that e δ ( S ) x e f ( S ) S V x e 0 e E {:["min"sum_(e in E)c_(e)x_(e)],["such that"sum_(e in delta(S))x_(e) >= f(S)quad AA S sube V],[x_(e)in0quad AA e in E],[]:}\begin{aligned} \text {min} &&& \sum_{e \in E} c_{e} x_{e} \\ \text {such that} &&& \sum_{e \in \delta(S)} x_{e} \geq f(S) \quad \forall S \subseteq V \\ &&& x_{e} \in 0 \quad \forall e \in E \\ \\ \end{aligned}
min S S f ( S ) y S such that S : e δ ( S ) y S c e e E y S 0 S V min S S f ( S ) y S such that S : e δ ( S ) y S c e e E y S 0 S V {:["min"sum_(S inS)f(S)y_(S)],["such that"sum_(S:e in delta(S))y_(S) <= c_(e)quad AA e in E],[y_(S) >= 0quad AA S sube V]:}\begin{aligned} \text {min} &&& \sum_{S \in \mathcal{S}}f(S) y_{S} \\ \text {such that} &&& \sum_{S: e \in \delta(S)} y_{S} \leq c_{e} \quad \forall e \in E \\ &&& y_{S} \geq 0 \quad \forall S \subseteq V \end{aligned}
The primal-dual algorithm is similar to the one for Steiner Forest with a growth phase and reverse-delete phase.
CoverUncrossableFunc ( G = ( V , E ) , f ) CoverUncrossableFunc ( G = ( V , E ) , f ) "CoverUncrossableFunc"(G=(V,E),f)\text{CoverUncrossableFunc}(G=(V, E), f):
F F quad F larr O/\quad F \leftarrow \emptyset
quad\quad while F F FF is not feasible
qquad\qquad Let C 1 , C 2 , , C C 1 , C 2 , , C C_(1),C_(2),dots,C_(ℓ)C_{1}, C_{2}, \ldots, C_{\ell} be minimally violated sets of f f ff with respect to F F FF
qquad\qquad Raise y C i y C i y_(C_(i))y_{C_{i}} for 1 i 1 i 1 <= i <= ℓ1 \leq i \leq \ell uniformly until some edge e e ee becomes tight
F F + e F F + e qquad F larr F+e\qquad F \leftarrow F+e
x e = 1 x e = 1 qquadx_(e)=1\qquad x_{e}=1
quad\quad Let F = { e 1 , e 2 , , e t } F = e 1 , e 2 , , e t F^(')={e_(1),e_(2),dots,e_(t)}F^{\prime}=\left\{e_{1}, e_{2}, \ldots, e_{t}\right\} where e i e i e_(i)e_{i} is edge added to F F FF in iteration i i ii
F = F F = F quadF^(')=F\quad F^{\prime}=F
quad\quad for i = t i = t i=ti=t down to 1 1 11 do
qquad\qquad if ( F e i ) F e i (F^(')-e_(i))\left(F^{\prime}-e_{i}\right) is feasible then F = F e i F = F e i F^(')=F^(')-e_(i)F^{\prime}=F^{\prime}-e_{i}
quad\quad Output F F F^(')F^{\prime}
Analysis: We can prove the following by induction on the iterations and omit the routine details.
Lemma 12.5. The output of the algorithm, F F F^(')F^{\prime}, is a feasible solution that covers f f ff. Assuming oracle access to finding the minimal violated sets in each iteration, the algorithm can be implemented in polynomial time.
The preceding lemma shows that the algorithm correctly outputs a feasible solution. The main part is to analyze the cost of the solution.
Theorem 12.9. Let F F F^(')F^{\prime} be the output of the algorithm. Then c ( F ) 2 S f ( S ) y S c F 2 S f ( S ) y S c(F^(')) <= 2sum_(S)f(S)y_(S)c\left(F^{\prime}\right) \leq 2 \sum_{S} f(S) y_{S} and hence c ( F ) 2 OPT c F 2 OPT c(F^(')) <= 2"OPT"c\left(F^{\prime}\right) \leq 2\text{OPT}.
The cost analysis is based on the following key structural lemma.
Lemma 12.6. Let G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) be a graph and let f : 2 V { 0 , 1 } f : 2 V { 0 , 1 } f:2^(V)rarr{0,1}f: 2^{V} \rightarrow\{0,1\} be an uncrossable function and let C C C\mathcal{C} be the set of minimal violated sets of f f ff with respect with respect to O/\emptyset. Let F E F E F sube EF \subseteq E be any minimal feasible solution that covers f f ff. Then C C deg F ( C ) 2 | C | C C deg F ( C ) 2 | C | sum_(C inC)deg_(F)(C) <= 2|C|\sum_{C \in \mathcal{C}} \operatorname{deg}_{F}(C) \leq 2|\mathcal{C}| where deg F ( C ) = | δ ( C ) F | deg F ( C ) = | δ ( C ) F | deg_(F)(C)=|delta(C)nn F|\operatorname{deg}_{F}(C)=|\delta(C) \cap F| is the number of edges of F F FF crossing C C CC.
We defer the proof of the preceding lemma to the following subsection and finish the analysis of the 2-approximation. This is similar to the one for Steiner Forest. Let t t tt be the number of iterations of the algorithm. Let C i C i C_(i)\mathcal{C}_{i} be the minimal violated sets in iteration i i ii of the algorithm and let Δ i Δ i Delta_(i)\Delta_{i} be the amount by which the duals grow in iteration i i ii. We call any C C i C C i C inC_(i)C \in \mathcal{C}_{i} active in iteration i i ii. We have e F c e = e F S : e δ ( S ) y S e F c e = e F S : e δ ( S ) y S sum_(e inF^('))c_(e)=sum_(e inF^('))sum_(S:e in delta(S))y_(S)\sum_{e \in F^{\prime}} c_{e}=\sum_{e \in F^{\prime}} \sum_{S: e \in \delta(S)} y_{S} since we add edges to F F FF only when the dual constraint is tight and F F F F F^(')sube FF^{\prime} \subseteq F. We also observe that the duals are grown only for sets S V S V S sube VS \subseteq V where f ( S ) = 1 f ( S ) = 1 f(S)=1f(S)=1 and hence S f ( S ) y S = S y S S f ( S ) y S = S y S sum_(S)f(S)y_(S)=sum_(S)y_(S)\sum_{S} f(S) y_{S}=\sum_{S} y_{S} for the dual solution created by the algorithm.
c ( F ) = e F S : e δ ( S ) y S = S f ( S ) y S deg F ( S ) = S deg F ( S ) S C i Δ i = i = 1 t Δ i S C i deg F ( S ) . c F = e F S : e δ ( S ) y S = S f ( S ) y S deg F ( S ) = S deg F ( S ) S C i Δ i = i = 1 t Δ i S C i deg F ( S ) . c(F^('))=sum_(e inF^('))sum_(S:e in delta(S))y_(S)=sum_(S)f(S)y_(S)deg_(F^('))(S)=sum_(S)deg_(F^('))(S)sum_(S inC_(i))Delta_(i)=sum_(i=1)^(t)Delta_(i)sum_(S inC_(i))deg_(F^('))(S).c\left(F^{\prime}\right)=\sum_{e \in F^{\prime}} \sum_{S: e \in \delta(S)} y_{S}=\sum_{S} f(S) y_{S} \operatorname{deg}_{F^{\prime}}(S)=\sum_{S} \operatorname{deg}_{F^{\prime}}(S) \sum_{S \in \mathcal{C}_{i}} \Delta_{i}=\sum_{i=1}^{t} \Delta_{i} \sum_{S \in \mathcal{C}_{i}} \operatorname{deg}_{F^{\prime}}(S) .
To complete the analysis we need the following lemma which can be seen as a corollary of Lemma 12.6.
Lemma 12.7. Consider any iteration i i ii of the algorithm. Then C C i deg F ( C ) 2 | C i | C C i deg F ( C ) 2 C i sum_(C inC_(i))deg_(F^('))(C) <= 2|C_(i)|\sum_{C \in \mathcal{C}_{i}} \operatorname{deg}_{F^{\prime}}(C) \leq 2\left|\mathcal{C}_{i}\right|.
Proof. Consider iteration i i ii. Let X = { e 1 , e 2 , , e i 1 } X = e 1 , e 2 , , e i 1 X={e_(1),e_(2),dots,e_(i-1)}X=\left\{e_{1}, e_{2}, \ldots, e_{i-1}\right\} which are the set of edges added by algorithm in the growth phase prior to iteration i i ii. Thus C i C i C_(i)\mathcal{C}_{i} is the minimal violated sets with respect to X X XX. Consider the graph G = ( V , E X ) G = ( V , E X ) G^(')=(V,E\\X)G^{\prime}=(V, E \backslash X) and the function f X f X f_(X)f_{X}. We observe that F = F X F = F X F^('')=F^(')\\XF^{\prime \prime}=F^{\prime} \backslash X is a minimal feasible solution to covering f X f X f_(X)f_{X} in G G G^(')-G^{\prime}- this is because of the reverse delete process. Moreover we claim that deg F ( C ) = deg F ( C ) deg F ( C ) = deg F ( C ) deg_(F^('))(C)=deg_(F^(''))(C)\operatorname{deg}_{F^{\prime}}(C)=\operatorname{deg}_{F^{\prime \prime}}(C) for any C C i C C i C inC_(i)C \in \mathcal{C}_{i} (why?). We can now apply Lemma 12.6 12.6 12.612.6 to the function f X f X f_(X)f_{X} (which is uncrossable) and G G G^(')G^{\prime} and F F F^('')F^{\prime \prime} so obtain:
C C i deg F ( C ) = C C i deg F ( C ) 2 | C i | . C C i deg F ( C ) = C C i deg F ( C ) 2 C i . sum_(C inC_(i))deg_(F^('))(C)=sum_(C inC_(i))deg_(F^(''))(C) <= 2|C_(i)|.\sum_{C \in \mathcal{C}_{i}} \operatorname{deg}_{F^{\prime}}(C)=\sum_{C \in \mathcal{C}_{i}} \operatorname{deg}_{F^{\prime \prime}}(C) \leq 2\left|\mathcal{C}_{i}\right| .
With the preceding lemma in place we have,
c ( F ) = i = 1 t Δ i S C i deg F ( S ) i = 1 t Δ i 2 | C i | = 2 S f ( S ) y S . c F = i = 1 t Δ i S C i deg F ( S ) i = 1 t Δ i 2 C i = 2 S f ( S ) y S . c(F^('))=sum_(i=1)^(t)Delta_(i)sum_(S inC_(i))deg_(F^('))(S) <= sum_(i=1)^(t)Delta_(i)*2|C_(i)|=2sum_(S)f(S)y_(S).c\left(F^{\prime}\right)=\sum_{i=1}^{t} \Delta_{i} \sum_{S \in \mathcal{C}_{i}} \operatorname{deg}_{F^{\prime}}(S) \leq \sum_{i=1}^{t} \Delta_{i} \cdot 2\left|\mathcal{C}_{i}\right|=2 \sum_{S} f(S) y_{S} .

12.2.1 Proof of Lemma 12.6

Since F F FF is a minimal feasible solution to cover f f ff, for every e F e F e in Fe \in F there must be a set S e S e S_(e)S_{e} such that f ( S e ) = 1 f S e = 1 f(S_(e))=1f\left(S_{e}\right)=1 and δ F ( S e ) = { e } δ F S e = { e } delta_(F)(S_(e))={e}\delta_{F}\left(S_{e}\right)=\{e\}; this is the reason we cannot remove e e ee from F F FF and maintain feasibility. We call such a set S e S e S_(e)S_{e} a witness set for e e ee. Clearly a witness set S e S e S_(e)S_{e} is a violated set.
Claim 12.2.1. Let S e S e S_(e)S_{e} be a witness set for e F e F e in Fe \in F. Then for any minimal violated set C C CC we have C S e C S e C subeS_(e)C \subseteq S_{e} or C S e = C S e = C nnS_(e)=O/C \cap S_{e}=\emptyset.
Proof. If C C CC crosses S e S e S_(e)S_{e} then either C S e C S e C-S_(e)C-S_{e} or C S e C S e C nnS_(e)C \cap S_{e} would also be violated (since f f ff is uncrossable) contradicting minimality of C C CC.
Note that there can be many witness sets for the same edge, however, the same set cannot be a witness set for two different edges.
Definition 12.10. Given a minimal feasible solution F F FF we call a family of sets S S S\mathcal{S} a witness family for F F FF if there is a bijection h : F S h : F S h:F rarrSh: F \rightarrow \mathcal{S} such that h ( e ) h ( e ) h(e)h(e) is a witness set for e e ee.
Given F F FF we can construct a witness family by considering each edge e F e F e in Fe \in F and picking an arbitrary witness set for e e ee and additing it to the collection.
Definition 12.11. A family S S S\mathcal{S} of finite sets is laminar if no two sets A , B S A , B S A,B inSA, B \in \mathcal{S} cross.
We have seen that there is a witness family for F F FF since it is minimal. We can obtain a special witness family starting with an arbitrary witness family.
Lemma 12.8. There is a witness family for F F FF which is laminar.
Proof. The process is based on uncrossing. Suppose we start with an arbitrary witness family S S S\mathcal{S} and it is not laminar. Let S e 1 , S e 1 S e 1 , S e 1 S_(e_(1)),S_(e_(1))S_{e_{1}}, S_{e_{1}} be the witness sets for e 1 , e 2 F e 1 , e 2 F e_(1),e_(2)in Fe_{1}, e_{2} \in F such that S e 1 , S e 2 S e 1 , S e 2 S_(e_(1)),S_(e_(2))S_{e_{1}}, S_{e_{2}} cross.
Claim 12.2.2. One of the following holds: (i) ( S { S e 1 , S e 2 } ) { S e 1 S e 2 , S e 2 S e 1 } S S e 1 , S e 2 S e 1 S e 2 , S e 2 S e 1 (S\\{S_(e_(1)),S_(e_(2))})uu{S_(e_(1))-S_(e_(2)),S_(e_(2))-S_(e_(1))}\left(\mathcal{S} \backslash\left\{S_{e_{1}}, S_{e_{2}}\right\}\right) \cup\left\{S_{e_{1}}-S_{e_{2}}, S_{e_{2}}-S_{e_{1}}\right\} is a witness family for F F FF (ii) ( S { S e 1 , S e 2 } ) { S e 1 S e 2 , S e 2 S e 2 } S S e 1 , S e 2 S e 1 S e 2 , S e 2 S e 2 (S\\{S_(e_(1)),S_(e_(2))})uu{S_(e_(1))nnS_(e_(2)),S_(e_(2))uuS_(e_(2))}\left(\mathcal{S} \backslash\left\{S_{e_{1}}, S_{e_{2}}\right\}\right) \cup\left\{S_{e_{1}} \cap S_{e_{2}}, S_{e_{2}} \cup S_{e_{2}}\right\} is a witness family for F F FF.
The new sets don't cross each other but what about other sets in the family? One can argue that the number of crossing can only decrease. More formally, suppose we have three sets A , B , D A , B , D A,B,DA, B, D and say D D DD crosses p p pp sets from A , B A , B A,BA, B( p p pp is one of { 0 , 1 , 2 } { 0 , 1 , 2 } {0,1,2}\{0,1,2\}). If we uncross A , B A , B A,BA, B (that is replace A , B A , B A,BA, B by A B , B A A B , B A A-B,B-AA-B, B-A or A B , A B A B , A B A nn B,A uu BA \cap B, A \cup B) then the number of sets that D D DD crosses after uncrossing cannot increase. We leave this claim as an exercise. This means that repeated uncrossing of two crossing sets will eventually lead to a laminar family.
Now we prove the claim. S e 1 . S e 1 S e 1 . S e 1 S_(e_(1)).S_(e_(1))S_{e_{1}} . S_{e_{1}} and S e 2 S e 2 S_(e_(2))S_{e_{2}} are violated sets which means that f ( S e 1 ) = 1 f S e 1 = 1 f(S_(e_(1)))=1f\left(S_{e_{1}}\right)=1 and f ( S e 2 ) = 1 f S e 2 = 1 f(S_(e_(2)))=1f\left(S_{e_{2}}\right)=1. Since f f ff is uncrossable, say f ( S e 1 S e 2 ) = 1 f S e 1 S e 2 = 1 f(S_(e_(1))-S_(e_(2)))=1f\left(S_{e_{1}}-S_{e_{2}}\right)=1 and f ( S e 2 S e 1 ) = 1 f S e 2 S e 1 = 1 f(S_(e_(2))-S_(e_(1)))=1f\left(S_{e_{2}}-S_{e_{1}}\right)=1. The only edges from F F FF that can cross S e 1 S e 2 S e 1 S e 2 S_(e_(1))-S_(e_(2))S_{e_{1}}-S_{e_{2}} and S e 2 S e 1 S e 2 S e 1 S_(e_(2))-S_(e_(1))S_{e_{2}}-S_{e_{1}} are e 1 e 1 e_(1)e_{1} and e 2 e 2 e_(2)e_{2} - if there is another edge e e ee that crosses one of them then it would also cross one of S e 1 S e 1 S_(e_(1))S_{e_{1}} and S e 2 S e 2 S_(e_(2))S_{e_{2}} and hence they would not be witness sets. Since F F F^(')F^{\prime} is a feasible solution, S e 1 S e 2 S e 1 S e 2 S_(e_(1))-S_(e_(2))S_{e_{1}}-S_{e_{2}} and S e 2 S e 1 S e 2 S e 1 S_(e_(2))-S_(e_(1))S_{e_{2}}-S_{e_{1}} are both crossed by some edge from Y = { e 1 , e 2 } Y = e 1 , e 2 Y={e_(1),e_(2)}Y=\left\{e_{1}, e_{2}\right\}. We claim that each of them is crossed by exactly one of them. If this is the case then they are valid witness sets for the two edges e 1 , e 2 e 1 , e 2 e_(1),e_(2)e_{1}, e_{2}. To see why exaclty one of them crosses each set we use submodularity/posi-modularity:
2 | δ Y ( S e 1 S e 2 ) | + | δ Y ( S e 2 S e 1 ) | | δ Y ( S e 1 ) | + | δ Y ( S e 2 ) | = 2 . 2 δ Y S e 1 S e 2 + δ Y S e 2 S e 1 δ Y S e 1 + δ Y S e 2 = 2 . 2 >= |delta_(Y)(S_(e_(1))-S_(e_(2)))|+|delta_(Y)(S_(e_(2))-S_(e_(1)))| <= |delta_(Y)(S_(e_(1)))|+|delta_(Y)(S_(e_(2)))|=2.2 \geq\left|\delta_{Y}\left(S_{e_{1}}-S_{e_{2}}\right)\right|+\left|\delta_{Y}\left(S_{e_{2}}-S_{e_{1}}\right)\right| \leq\left|\delta_{Y}\left(S_{e_{1}}\right)\right|+\left|\delta_{Y}\left(S_{e_{2}}\right)\right|=2 .
The first inequality is since each is covered and the second inequality is because of posi-modularity of | δ Y ( ) | δ Y ( ) |delta_(Y)(*)|\left|\delta_{Y}(\cdot)\right|.
The other case when f ( S e 1 S e 2 ) = 1 f S e 1 S e 2 = 1 f(S_(e_(1))nnS_(e_(2)))=1f\left(S_{e_{1}} \cap S_{e_{2}}\right)=1 and f ( S e 1 S e 2 ) = 1 f S e 1 S e 2 = 1 f(S_(e_(1))uuS_(e_(2)))=1f\left(S_{e_{1}} \cup S_{e_{2}}\right)=1 can also be handled with a similar argument.
Let S S S\mathcal{S} be a laminar witness family for F F FF. We create a rooted tree P P PP from S S S\mathcal{S} as follows. To do this we first add V V VV to the family. For each set S S S S S inSS \in \mathcal{S} we add a vertex v S v S v_(S)v_{S}. For any S , T S , T S,TS, T such that T T TT is the smallest set in S S S\mathcal{S} containing S S SS we add the edge ( v S , v T ) v S , v T (v_(S),v_(T))\left(v_{S}, v_{T}\right) which makes v T v T v_(T)v_{T} the parent of v S v S v_(S)v_{S}. Since we added V V VV to the family we obtain a tree since every maximal set in the original family becomes a child of v V v V v_(V)v_{V}. Note that P P PP has | F | | F | |F||F| edges and | F | + 1 | F | + 1 |F|+1|F|+1 nodes and each e F e F e in Fe \in F corresponds to the edge ( v S e , v T ) v S e , v T (v_(S_(e)),v_(T))\left(v_{S_{e}}, v_{T}\right) of P P PP where v T v T v_(T)v_{T} is the parent of v S e v S e v_(S_(e))v_{S_{e}} in P P PP. We keep this bijection between F F FF and edges of P P PP in mind for later.
See figure.
Consider any minimal violated set C C C C C in CC \in C. We observe that C C CC cannot cross any set in S S S\mathcal{S} since it is a witness family. For each C C CC we associate the minimal set S S S S S inSS \in \mathcal{S} such that C S C S C sube SC \subseteq S. We call v S v S v_(S)v_{S} an active node of T T TT if there is a C S C S C inSC \in \mathcal{S} associated with it. Note that (i) not all nodes of P P PP may be active (ii) every C C CC is associated with exactly one active node of P P PP (iii) multiple sets from C C CC can be associated with the same active node of P P PP.
Lemma 12.9. Let P a P a P_(a)P_{a} be the active nodes of P P PP. Then | P a | | C | P a | C | |P_(a)| <= |C|\left|P_{a}\right| \leq|C| and every leaf of P P PP other than potentially the root is an active node.
Proof. Since each C C CC is associated with an active node we obtain | P a | | C | P a | C | |P_(a)| <= |C|\left|P_{a}\right| \leq|C|. A leaf of P P PP corresponds to a minimal set from S S S\mathcal{S} or the root. If S e S e S_(e)S_{e} is a minimal set from S S S\mathcal{S} then S e S e S_(e)S_{e} is a violated set and hence must contain a minimal violated set C. But then S e S e S_(e)S_{e} is active because of C C CC. Consider v V v V v_(V)v_{V}. If it is a leaf then it has only one child which is the unique maximal witness set S S SS. The root can be inactive since the function f f ff is not necessarily symmetric. (However, if f f ff is symmetric then V S V S V-SV-S would also be a violated set and hence contain a minimal violated set from C C CC.)
Figure 12.1: Laminar witness family for a minimal solution F F FF shown as red edges. Sets in green are the minimal violated sets and the sets in black are the witness sets. The root set V V VV is not drawn.
Lemma 12.10. Let v T v T v_(T)v_{T} be an active node in P P PP. Let C C C C C^(')subeC\mathcal{C}^{\prime} \subseteq \mathcal{C} be set of all minimal violated sets associated with v T v T v_(T)v_{T}. Then C C deg F ( C ) deg P ( v T ) C C deg F ( C ) deg P v T sum_(C inC^('))deg_(F)(C) <= deg_(P)(v_(T))\sum_{C \in \mathcal{C}^{\prime}} \operatorname{deg}_{F}(C) \leq \operatorname{deg}_{P}\left(v_{T}\right).
Proof. Let Y = C C δ F ( C ) Y = C C δ F ( C ) Y=uu_(C inC^('))delta_(F)(C)Y=\cup_{C \in \mathcal{C}^{\prime}} \delta_{F}(C) be the set of edges incident to the sets in C C C^(')\mathcal{C}^{\prime}. Consider any C C . C T C C . C T C inC^(').C sub TC \in \mathcal{C}^{\prime} . C \subset T and C C CC is also disjoint from the children of T T TT. Consider an edge e δ F ( C ) e δ F ( C ) e indelta_(F)(C)e \in \delta_{F}(C). If e e ee crosses T T TT then T T TT is the witness set for e e ee (since only one edge from F F FF can cross T T TT for which it is the witness) and we charge e e ee to the parent edge of T T TT. If e e ee does not cross T T TT then the witness set S e S e S_(e)S_{e} must be a child of T T TT. Since only one edge can cross each child of T T TT we can charge e e ee to one child of T T TT. Note that no edge e Y e Y e in Ye \in Y can be incident to two set C 1 , C 2 C C 1 , C 2 C C_(1),C_(2)inC^(')C_{1}, C_{2} \in \mathcal{C}^{\prime} since both one end point of e e ee must be contained in a child of T T TT (assuming e e ee does not cross T T TT) and both C 1 , C 2 C 1 , C 2 C_(1),C_(2)C_{1}, C_{2} are contained in T T TT and disjoint from the children of T T TT. See figure. Therefore, we can charge C C deg F ( C ) C C deg F ( C ) sum_(C inC^('))deg_(F^('))(C)\sum_{C \in \mathcal{C}^{\prime}} \operatorname{deg}_{F^{\prime}}(C) to the number of children of T T TT plus the parent edge of T T TT, which is deg P ( v T ) deg P v T deg_(P)(v_(T))\operatorname{deg}_{P}\left(v_{T}\right).
Now we are ready to finish the proof. From Lemma 12.10 and the fact that each C C C C C inCC \in \mathcal{C} is associated to some active node, we have
C C deg F ( C ) v P a deg P ( v ) . C C deg F ( C ) v P a deg P ( v ) . sum_(C inC)deg_(F)(C) <= sum_(v inP_(a))deg_(P)(v).\sum_{C \in \mathcal{C}} \operatorname{deg}_{F}(C) \leq \sum_{v \in P_{a}} \operatorname{deg}_{P}(v) .
To bound v P a deg p ( v ) v P a deg p ( v ) sum_(v inP_(a))deg_(p)(v)\sum_{v \in P_{a}} \operatorname{deg}_{p}(v) we had observed that in the tree P P PP every leaf except perhaps the root node is an active node. Suppose root is an active node or it is not a leaf. Then from Lemma 11.2, v P a deg P ( v ) 2 | P a | 2 v P a deg P ( v ) 2 P a 2 sum_(v inP_(a))deg_(P)(v) <= 2|P_(a)|-2\sum_{v \in P_{a}} \operatorname{deg}_{P}(v) \leq 2\left|P_{a}\right|-2. Suppose root is a leaf and inactive. Again from Lemma 11.2 11.2 11.211.2 where we consider Z = P a { v V } Z = P a v V Z=P_(a)uu{v_(V)}Z=P_{a} \cup\left\{v_{V}\right\}, we have v P a deg P ( v ) + 1 2 | P a + 1 | 2 = 2 | P a | v P a deg P ( v ) + 1 2 P a + 1 2 = 2 P a sum_(v inP_(a))deg_(P)(v)+1 <= 2|P_(a)+1|-2=2|P_(a)|\sum_{v \in P_{a}} \operatorname{deg}_{P}(v)+1 \leq 2\left|P_{a}+1\right|-2=2\left|P_{a}\right|. Hence v P a deg P ( v ) 2 | P a | 1 v P a deg P ( v ) 2 P a 1 sum_(v inP_(a))deg_(P)(v) <= 2|P_(a)|-1\sum_{v \in P_{a}} \operatorname{deg}_{P}(v) \leq 2\left|P_{a}\right|-1. Thus, in both cases we see that v P a deg P ( v ) 2 | P a | v P a deg P ( v ) 2 P a sum_(v inP_(a))deg_(P)(v) <= 2|P_(a)|\sum_{v \in P_{a}} \operatorname{deg}_{P}(v) \leq 2\left|P_{a}\right|. Finally we note that | P a | | C | P a | C | |P_(a)| <= |C|\left|P_{a}\right| \leq|\mathcal{C}| and hence putting together we have
C C deg F ( C ) 2 | P a | 2 | C | C C deg F ( C ) 2 P a 2 | C | sum_(C inC)deg_(F)(C) <= 2|P_(a)| <= 2|C|\sum_{C \in \mathcal{C}} \operatorname{deg}_{F}(C) \leq 2\left|P_{a}\right| \leq 2|C|
as desired.
Bibliographic Notes: The primal-dual algorithm for uncrossable function is from the paper of Williamson, Goemans, Mihail and Vazirani [1]. The proof in the paper assumes that h h hh is symmetric without explicitly stating it; for symmetric functions one obtains a slight advantage over 2 2 22. See Williamson's thesis [2] where he gives the proof for both symmetric and general uncrossable functions. The survey by Goemans and Williamson [3] describes the many applications of the primal-dual method in network design.

  1. David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. “A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems”. In: 15 (1995), pp. 435–454. doi: http://dx.doi.org/10.1007/BF01299747. ↩︎
  2. David P. Williamson. “On the design of approximation algorithms for a class of graphs problems”. PhD thesis. Cambridge, MA: MIT, 1993. ↩︎
  3. Michel X Goemans and David P Williamson. “The primal-dual method for approximation algorithms and its application to network design problems”. In: Approximation algorithms for NP-hard problems (1997), pp. 144–191. ↩︎

Recommended for you

Kaichao You
A New Paradigm for Exploiting Pre-trained Model Hubs
A New Paradigm for Exploiting Pre-trained Model Hubs
It is often overlooked that the number of models in pre-trained model hubs is scaling up very fast. As a result, pre-trained model hubs are popular but under-exploited. Here a new paradigm is advocated to sufficiently exploit pre-trained model hubs.
8 points
0 issues