Tight Analysis of the Primal-Dual Method for Edge-Covering Pliable Set Families

Let ${ℱ}_0={ℱ}^{J_0}$ be the residual family of $ℱ$ w.r.t. $J_0$, and note that ${ℱ}^{\prime }$ is the residual family of ${ℱ}_0$ w.r.t. $I^{\prime }\setminus I$.

We prove (i). Since the edges were deleted in reverse order, the edges in $I^{\prime }$ were considered for deletion when all edges in $J_0$ were still present. Thus $I^{\prime }$ is an inclusion-minimal cover of ${ℱ}_0$. This implies that $I$ is an inclusion-minimal cover of the residual family of ${ℱ}_0$ w.r.t. $I^{\prime }\setminus I$ (this is so for any $I\subseteq I^{\prime }$), which is ${ℱ}^{\prime }$.

We prove (ii). By the definition, $𝒞$ is the family of ${ℱ}_0$-cores. No $C\in 𝒞$ is covered by $I^{\prime }\setminus I$, hence $𝒞\subseteq 𝒞({ℱ}^{\prime })$. This also implies that ${ℱ}^{\prime }$ has no other core $C^{\prime }\notin 𝒞({ℱ}^{\prime })\setminus 𝒞$, as otherwise $C^{\prime }\in {ℱ}_0$ and thus properly contains some $C\in 𝒞$, which is a contradiction. $◀$

Observing that $d_J(C)=d_I(C)$ for all $C\in 𝒞$ (since no $C\in 𝒞$ is covered by $J_0\cup (I^{\prime }\setminus I)$), we have the following.

One can see that if an edge $e$ covers one of the sets $A\cap B,A\cup B,A\setminus B,B\setminus A$ then it also covers one of $A,B$. This implies the following.

Due to Lemmas 6 and 7, to prove that the WGMV algorithm achieves approximation ratio $7$ for a $\gamma$-pliable family $ℱ$, it is sufficient to prove the following purely combinatorial statement.

A set family $ℒ$ is laminar if any two sets in $ℒ$ are disjoint or one of them contains the other. Let $I$ be an inclusion minimal edge cover of a set family $ℱ$. We say that a set $S_e\in ℱ$ is a witness set for an edge $e\in I$ if $e$ is the unique edge in $I$ that covers $S_e$, namely, if ${\delta }_I(S_e)=\{e\}$. We say that $ℒ\subseteq ℱ$ is a witness family for $I$ if $|ℒ|=|I|$ and for every $e\in I$ there is a witness set $S_e\in ℒ$. By the minimality of $I$, there exists a witness family $ℒ\subseteq ℱ$. The following was proved in BCGI [4].

Augment $ℒ$ by the set $V$. A set $S\in ℒ$ owns a set $C$ if $S$ is the inclusion-minimal set in $ℒ$ that contains $C$. We assign colors to sets in $ℒ$ as follows: a set is black if it owns some core and is white otherwise.

The laminar family $ℒ$ can be represented by a rooted tree $𝒯$ with node set $ℒ$ and root $V$, where the parent of $S$ in $𝒯$ is the smallest set in $ℒ$ that properly contains $S$. The (unique) edge in $I$ that covers $S$ corresponds to the edge in $𝒯$ from $S$ to its parent. We use for nodes of $𝒯$ the same terminology as for sets in $ℒ$; specifically, nodes of $𝒯$ are colored white and black accordingly, and a white chain in $𝒯$ is a path from a node to its ancestor such that all its nodes are white and have degree $2$.

Short-cutting a maximal white chain $\mathrm{SS}$ as in Definition 10 means removing from $ℒ$ the sets $S_1,\mathrm{\dots },S_{\mathrm{\ell }}$ and replacing in $I$ the $\mathrm{\ell }+1$ edges in $I_{\mathrm{SS}}$ by the single edge $e=a_0{b}_{\mathrm{\ell }+1}$ of weight $w(e)=w(\mathrm{SS})$ that now has $S_0$ as the witness set; see Fig. 1. In the tree representation $𝒯$ of $ℒ$ this means that we replace the white chain – the edges in $I_{\mathrm{SS}}$ and the nodes $S_1,\mathrm{\dots },S_{\mathrm{\ell }}$ by a new “shortcut edge” $e$ of weight $w(e)=w(\mathrm{SS})$ between the set that own $a_0$ and the set that owns $b_{\mathrm{\ell }}$.

Now let us consider the rooted weighted shortcut tree $T=(B\cup W,I),w,r$ (where $B$ is the set of black nodes and $W$ is the set of white nodes) obtained from $𝒯$ by short-cutting every maximal white chain. Let $L$ be the set of leaves of $T$. In what follows, note the following properties of $T$.

1. 1.

   $w(I)={\sum }_{C\in 𝒞}{d}_I(C)$, namely, $w(I)$ equals the left-hand side of (1).

2. 2.

   $|B|\le |𝒞|$; every core is owned by exactly one set in $ℒ$, since $V\in ℒ$ and since $ℒ$ is laminar.

3. 3.

   In $T$, every leaf and every non-root node with exactly one child is black; we will call any tree that has this property a black-white tree. In particular, $T$ has no white chain (a path of white nodes that have exactly one child each) and thus $|I|\le 2|𝒞|$.

4. 4.

   $|I|=|W|+|B|-1\le 2|B|-1$ and $|W|\le |L|\le |B|$, and if $r$ is black or has at least $2$ children then $|W|\le |B|-1$.

If the original tree has no white chain of length $>\mathrm{\ell }$ then $w(e)\le \mathrm{\ell }$ for all $e\in I$, and thus ${\sum }_{C\in 𝒞}{d}_I(C)=w(I)\le 2(\mathrm{\ell }+1)\cdot 2|𝒞|$. BCGI [4] showed that the maximum possible length of a white chain is $\mathrm{\ell }=3$, which gives the bound $w(I)\le 16|𝒞|$. To improve this bound the following was proved in [11].

This immediately implies $w(I)\le 10$ (this is the bound that was explicitly stated in [11]), but in fact it also easily implies that $w(I)\le 9|B|$. To see this, let $t$ be the number of edges of weight $5$. Then $t\le |B|$, since by Lemma 11 the tail of every edge of weight $5$ is black. Thus since $|W|\le |B|$ we get

In the next section we will describe how to improve the analysis of the approximation ratio fro $9$ to $7$.

Let $t$ be the number of heavy edges. There are exactly $|I|-t=|W|+|B|-1-t$ non-heavy edges, hence since $|W|\le |B|$ we have

Since all leaves are black and since there is no bad pair, we can assign to every heavy edge the closest descendant black node, and no black node will be assigned twice. Consequently, $t\le |B|$. Thus we get $w(I)\le 3t+2(2|B|-1)\le 7|B|-2$, concluding the proof. $◀$

We will prove the following.

Note that Lemma 13 does not imply that the bad pairs are pairwise disjoint; if $(e,e^{\prime })$ is a bad pair then $(e,e^{\prime })$ is the unique bad pair that contains $e$, but there can be many bad pairs $(e_1,e^{\prime }),\mathrm{\dots },(e_q,e^{\prime })$ that contain $e^{\prime }$. Still, Theorem 2 easily follows from Lemmas 13 and 12 by a simple manipulation of weights. For every edge $e^{\prime }$ that appears as an upper edge in some bad pair, choose one such bad pair $(e,e^{\prime })$ and change the weights of $e^{\prime }$ to be $2$ and the weight of $e$ to be $w(e)+w(e^{\prime })-2\le 5$. This operation does not change the maximum weight nor the total weight, and after it there are no bad pairs, so there is a black node between any two ancestor-descendant heavy edges. Theorem 2 now follows from Lemma 12. Furthermore, the proof shows that if the bound $w(I)\le 7|B|$ is asymptotically tight, then there exists a tight example without bad pairs.

In the rest of this section we prove Lemma 13. For that, we will need to analyze the white chains of a bad pair $(e,e^{\prime })$ as in the lemma. Note that in terms of white chains Lemma 13 says that if $(\mathrm{SS},{\mathrm{SS}}^{\prime })$ is a bad pair of white chains then:

1. 1.

   $w(\mathrm{SS})+w({\mathrm{SS}}^{\prime })\le 7$.

2. 2.

   There is no heavy maximal white chain between $\mathrm{SS}$ and ${\mathrm{SS}}^{\prime }$.

In the rest of this section we will prove this “white chains version” of Lemma 13.

Suppose that $C$ is not a subset of $S$. Then $C\setminus S\ne \mathrm{\varnothing }$. Also $S\setminus C\ne \mathrm{\varnothing }$, since $S$ cannot be a subset of $C$. By the minimality of $C$ we must have $C\cap S,C\setminus S\notin ℱ$, thus since $ℱ$ is pliable $S\setminus C,S\cup C\in ℱ$. In particular, $S,C$ cross. $◀$

In the proof of Lemma 13 we will use the following property of white sets.

Since $S_i$ is white (and thus doesn’t own $C$), $C\setminus S_i\ne \mathrm{\varnothing }$. Thus $C$ crosses both $S_{i-1},S_i$, by Lemma 14. Now suppose that $S_{i-1}$ is the unique child of $S_i$. Let $D=S_i\setminus (C\cup S_{i-1})$. By property $(\gamma )$ either $D=\mathrm{\varnothing }$ or $D\in ℱ$. If $D=\mathrm{\varnothing }$ then we are done. Else, $D\in ℱ$ and thus $D$ contains a core $C^{\prime }\in 𝒞$, that is owned by a descendant of $S_i$ disjoint to $S_{i-1}$. This contradicts that $S_i$ has a unique child. $◀$

Let $\mathrm{SS}$ be a maximal white chain as in Definition 10 and let $C\in 𝒞$. The following is proved in [11]; we provide a proof for completeness of exposition.

If $S_0\cap C\ne \mathrm{\varnothing }$ and $C$ is not owned by $S_0$ or by a descendant of $S_0$, then by Lemma 15, $\{a_1,b_1\}\subseteq S_1\setminus S_0\subset C$. Now assume that $a_0\in C$ and suppose to the contrary that $S_0$ does not own $C$. Then $C\setminus S_0\ne \mathrm{\varnothing }$. By Lemma 15, $S_1\setminus S_0\subset C$, hence $b_1\in C$. Thus the edge $a_0{b}_1$ has both ends in $C$, contradicting the assumption the every edge in $I$ covers some $C\in 𝒞$.

We prove (i). If $S_{i+1}$ exists then by Lemma 15 $b_{i+1}\in C$, contradicting the assumption that every edge in $I$ covers some $C\in 𝒞$.

We prove (ii). If $S_{i+1}$ exists then by Lemma 15 $a_{i+1},b_{i+1}\in C$, and $\mathrm{\ell }=i+1$ follows from part (i). $◀$

Let $U={\bigcup }_{C\in 𝒞}C$ be the set of those nodes that belong to some core. Using Lemma 16, we obtain the following partial characterization of heavy maximal white chains.

The case $\mathrm{\ell }=1$ is obvious. If $\mathrm{\ell }=2$ then $a_1\notin U$, by Lemma 16. If $b_1\in C$ for some $C\in 𝒞$ then by Lemma 16 $a_2,b_2\in C$ and we arrive at case (2a). Else, $b_1\notin U$ and since $a_1\notin U$ we must have $a_0,b_2\in U$ (since every edge has at least one end in $U$), and we arrive at case (2b).

If $a_1,b_1,a_2\notin U$, then $b_2\in U$ (since the edge $a_1{b}_2$ has an end in $U$), which by Lemma 16 implies $\mathrm{\ell }=3$ and $b_2,b_3,a_3\in C$ for some $C\in 𝒞$. $◀$

Consider the lower chain $\mathrm{SS}$. By Lemma 17, one of the nodes $a_1,b_1,\mathrm{\dots },a_{\mathrm{\ell }},b_{\mathrm{\ell }}$ is in $C$ for some $C\in 𝒞$. The core $C$ is not owned by sets in $\mathrm{SS}\cup {\mathrm{SS}}^{\prime }$ nor by sets between $\mathrm{SS}$ and ${\mathrm{SS}}^{\prime }$, since all these sets are white. Thus $C$ crosses all sets in the upper chain ${\mathrm{SS}}^{\prime }$, and in particular the set $S_1^{\prime }$. By Lemma 15 $S_1^{\prime }\setminus S_0^{\prime }\subseteq C$, and in particular $a_1^{\prime }\in C$. This implies $\mathrm{\ell }=1$, by Lemma 16. Moreover, $a_0^{\prime }\notin U$, as otherwise by Lemma 16 $S_0^{\prime }$ is black, contradicting the assumption that there is no black set between $\mathrm{SS}$ and ${\mathrm{SS}}^{\prime }$. This proves part 1.

For part 2, we claim that one of $a_{\mathrm{\ell }},b_{\mathrm{\ell }+1}$ is not in $U$. Suppose to the contrary that $a_{\mathrm{\ell }}\in C$ and $b_{\mathrm{\ell }+1}\in C^{\prime }$ for some distinct $C,C^{\prime }\in 𝒞$. Then each of $C,C^{\prime }$ crosses all the sets in ${\mathrm{SS}}^{\prime }$, and in particular the first set $S_1^{\prime }$. Thus by Lemma 15 $S_1^{\prime }\setminus S_0^{\prime }\subseteq C\cap C^{\prime }$, and in particular $a_1^{\prime },b_1^{\prime }\in C\cap C^{\prime }$. This contradicts that the cores are disjoint. Consequently, one of $a_{\mathrm{\ell }},b_{\mathrm{\ell }+1}$ is not in $U$, which implies $w(\mathrm{SS})\le 4$, by Lemma 17; note that $w(\mathrm{SS})=5$ is possible only in case (3) of Lemma 17 when $a_3,b_4\in U$. If $\mathrm{\ell }=1$, then $a_0\in U$ as otherwise $\mathrm{SS}$ is not heavy. $◀$

Lemma 18 already implies the first part 1 of Lemma 13, that $w(\mathrm{SS})+w({\mathrm{SS}}^{\prime })\le 7$. We will show that it also implies part 2. Suppose to the contrary that there is another maximal white chain ${\mathrm{SS}}^{\prime \prime }$ between $\mathrm{SS}$ and ${\mathrm{SS}}^{\prime }$. To obtain a contradiction we apply Lemma 18 twice, as follows.

• $\mathrm{■}$

  Since $\mathrm{SS}\prec {\mathrm{SS}}^{\prime \prime }$, Lemma 18 implies ${\mathrm{\ell }}^{\prime \prime }=1$ and $a_0^{\prime \prime }\notin U$.

• $\mathrm{■}$

  Since ${\mathrm{SS}}^{\prime \prime }\prec {\mathrm{SS}}^{\prime }$, Lemma 18 implies that if ${\mathrm{\ell }}^{\prime \prime }=1$ then $a_0^{\prime \prime }\in U$.

In the first application $a_0^{\prime \prime }\notin U$ while in the second $a_0^{\prime \prime }\in U$, arriving at a contradiction.

This concludes the proof of Lemma 13, and thus also of Lemma 8 and Theorem 2.

The following example shows that the bound in (2) is asymptotically tight. The shortcut-tree is a binary tree with black nodes $B=L\cup \{r\}$ and weights $5$ for leaf edges while all the other edges have weight $2$; see Fig. 4 for an illustration for the case $|L|=8$. To materialize this tree in terms of the laminar family $ℒ$ and a set $|𝒞$ of cores, do the following.

• $\mathrm{■}$

  Replace every leaf edge by the gadget as in case (2a) in Lemma 17 where $a_0,b_3\in U$ belong to distinct cores.

• $\mathrm{■}$

  Every other edge will connect two distinct cores, when the same cores are used for distinct edges.

Every node colored by a shade of red is a core (we used distinct shades of red to indicate that these cores are distinct), and is a leaf in the laminar family $ℒ$. There are two additional cores – one contains all black nodes and the other all blue nodes; these two cores are owned by the root $V$. The number of cores is $|𝒞|=|L|+2$, while the total weight of the edges in the shortcut tree is $5|L|+2(|L|-1)=7|L|-2$.

Note that this example shows only the edge set $I$, the laminar witness family $ℒ$, and the set $𝒞$ of cores, but does not specify the entire $\gamma$-pliable set family $ℱ$. Such a family $ℱ$ should have the following properties.

1. (i)

   $ℱ$ contains the laminar family $ℒ$ and the set $𝒞$ of cores as in the example.

2. (ii)

   $I$ is an inclusion minimal cover of $ℱ$.

3. (iii)

   $ℱ$ is $\gamma$-pliable.

Such a family $ℱ$ can probably be obtained by an iterative process that starts with $ℱ=ℒ\cup 𝒞$ and repeatedly adds to $ℱ$ at least two sets among $A\cap B,A\setminus B,B\setminus A,A\cup B$ for any pair $A,B\in ℱ$. We will not describe the full construction here.

Let $\mathrm{SS}$ be a white chain. By Lemma 17, if $w(\mathrm{SS})=5$ then $a_0,a_{\mathrm{\ell }},b_{\mathrm{\ell }+1}\in U$; see cases (2a) and (3) in Figure 2 and Lemma 17. Thus by Lemma 16 $S_0$ is black (since $a_0\in U$). Note that $a_{\mathrm{\ell }},b_{\mathrm{\ell }+1}$ belong to distinct cores, say $a_{\mathrm{\ell }}\in C$ and $b_{\mathrm{\ell }+1}\in C^{\prime }$. Let $S$ be the parent of $S_{\mathrm{\ell }}$. Since $ℱ$ is sparse, at least one of $C,C^{\prime }$ cannot cross $S$, and thus is owned by $S$. Hence $S$ is also black. If $w(\mathrm{SS})=4$ then $a_0\in U$ and then $S_0$ is black, or $a_{\mathrm{\ell }},b_{\mathrm{\ell }+1}\in U$ and then the parent $S$ of $S_{\mathrm{\ell }}$ is black. $◀$

Let $T=(W\cup B,I),r,w$ be the shortcut tree; recall that $T$ is a black-white tree, namely, every non-root node with exactly one child is black. We already know that $w(e)\le 5$ and if $w(e)=5$ then $e$ has its lower end in $B$ (by Lemma 11); Lemma 20 adds the property that if $w(e)=5$ then $e$ has both ends in $B$. Furthermore, Lemma 18 implies the following.

For a heavy edge $e$ let $B_e$ be the set of black nodes $b\in B$ such that $b$ is a descendant of $e$ and there is no heavy edge between $e$ and $b$. Note the following.

• $\mathrm{■}$

  $B_e=\mathrm{\varnothing }$ if and only if $e$ is an upper edge of a bad pair.

• $\mathrm{■}$

  $B_e\cap B_f=\mathrm{\varnothing }$ for distinct $e,f$.

Let $H^{\ast }$ be the set of heavy edges $e$ such that $e$ is not the upper edge of a bad pair, so $B_e\ne \mathrm{\varnothing }$ for all $e\in H^{\ast }$. For every $e\in H^{\ast }$ choose one node $b_e\in B_e$ and let $B^{\ast }=\{b_e:e\in H^{\ast }\}$ be the set of chosen black nodes. Now we will prove the following lemma, that implies Lemma 19.

Assign tokens to nodes in $B$ as follows:

• $\mathrm{■}$

  $4$ tokens to every node in $L$.

• $\mathrm{■}$

  $3$ tokens to every node in $B\setminus L$.

• $\mathrm{■}$

  $2$ additional tokens to every node in $B^{\ast }$.

The number of tokens is $4|L|+3|B\setminus L|+2|B^{\ast }|=3|B|+|L|+2|B^{\ast }|$. We will show that these tokens can be redistributed such that every $e\in I$ gets $w(e)$ tokens and some tokens remain.

For each $e\in H^{\ast }$ use $2$ tokens of $b_e$ to reduce the weight of $e$ by $2$. Then we have the following.

• $\mathrm{■}$

  Every leaf has $4$ tokens and every internal black node has $3$ tokens.

• $\mathrm{■}$

  The maximum weight is $3$ since initially the maximum weight was $5$ and since the upper edge of every bad pair has weight exactly $3$, by Corollary 21.

• $\mathrm{■}$

  Every edge of weight $3$ has its upper end in $B$, since every edge of weight $5$ and the upper edge of every bad pair has its upper end in $B$, by Lemma 20 and Corollary 21.

For $v\in V$ let $T_v$ be the rooted subtree of $T$ that consists of $v$ and its descendants. We claim that for any $v\ne r$, the tokens of $T_v$ can be redistributed such that every edge gets at least $w(e)$ tokens and the root $v$ gets $4$ tokens. The proof is by induction on he height of the tree. The induction base case, when $v$ is a leaf, is trivial. Suppose that $v$ is not a leaf and has $p\ge 1$ children. By the induction hypothesis each child of $v$ has $4$ tokens.

Suppose that $v$ is white. Then $p\ge 2$. Each child of $v$ is connected to $v$ by an edge of weight $\le 2$ (since the upper end of every edge of weight $3$ is black), and this child can pay for its parent edge and give $2$ tokens to $v$. Thus $v$ gets $2p\ge 4$ tokens.

Suppose that $v$ is black, so $v\in B\setminus L$. Then $v$ already has $3$ tokens. Each child of $v$ is connected to $v$ by an edge of weight $\le 3$. Thus in this case each child can pay for his parent edge and give $1$ token to $v$. Thus $v$ gets $3+p\ge 4$ tokens.

Now let us consider the root $r$ of $T$ that has $p\ge 1$ children. If $r$ is white then it gets $2p\ge 2$ tokens. If $r$ is black then it gets $3+p\ge 4$ tokens, and if $r$ has at least $2$ children then it gets $3+p\ge 4$ tokens. $◀$

Lemma 22 implies that $w(I)\le 6|B|-2\le 6|𝒞|-2$, thus concluding the proof of the first part of Theorem 3. The following example shows that the bound $w(I)\le 6|B|$ is asymptotically tight even when there are no bad pairs. The shortcut-tree is a binary tree with black nodes $B=L\cup \{r\}$ and weights $4$ for leaf edges while all the other edges have weight $2$; see Fig. 5 for an illustration for the case $|L|=8$. To materialize this tree in terms of the laminar family and cores, do the following.

• $\mathrm{■}$

  Replace every leaf edge by the Lemma 17(2a) gadget, where $a_0,\in U$ and $b_3\notin U$.

• $\mathrm{■}$

  Replace every other edge by the gadget as in case (1) in Lemma 17 where $a_1,b_1\in U$ and $a_0,b_3\notin U$; this is a “redundant” (non-heavy) white chain of weight $2$.

Every node colored by a shade of red is a core (we used distinct shades of red to indicate that these cores are distinct), and there is one additional core – the one that contains all black nodes; this core is owned by the root $V$. The number of cores is $|L|+1$, while the total weight is $4|L|+2(|L|-1)=6|L|-2$.

Note that in this example every member of the laminar family is crossed by at most one core, and that there are no bad pairs in this example.

The example again shows only the edge set $I$, the laminar witness family $ℒ$, and the set $𝒞$ of cores, but does not specify the entire $\gamma$-pliable sparse set family $ℱ$. Such a family $ℱ$ should have the following properties.

1. (i)

   $ℱ$ contains the laminar family $ℒ$ and the set $𝒞$ of cores as in the example.

2. (ii)

   $I$ is an inclusion minimal cover of $ℱ$.

3. (iii)

   $ℱ$ is $\gamma$-pliable and sparse.

Such a family $ℱ$ can be obtained by an iterative process that starts with $ℱ=ℒ\cup 𝒞$ and repeatedly adds to $ℱ$ at least two sets among $A\cap B,A\setminus B,B\setminus A,A\cup B$ for any pair $A,B\in ℱ$. We will not describe the full construction here.

Note that the above example is not for the Small Cuts Cover problem, but rather for an arbitrary sparse $\gamma$-pliable family. In fact, Corollary 4 states that Small Cuts Cover admits a better approximation ratio $6-\frac{1}{\beta +1}$, where $\beta =\lfloor \frac{k-1}{\lceil (\lambda +1)/2\rceil }\rfloor$ and $\lambda$ is the the edge-connectivity of the input graph $H$. This approximation ratio is is better than $6$ when $\lambda$ is not much smaller than $k$.

To prove the second part of Theorem 3 we prove the following.

We claim that

To see this consider the set of edges $I^{\ast }=\{e\in H^{\ast }:b_e\in L\cap B^{\ast }\}$; namely, $e\in I^{\ast }$ if $e\in H^{\ast }$ (so $e$ is heavy but is not the upper edge of a bad pair) and the black node $b_e$ assigned to $e$ is a leaf. Note the following.

• $\mathrm{■}$

  For any two edges in $I^{\ast }$, none of them is a descendant of the other, since if $e\in I^{\ast }$ has a descendant edge $f\in I^{\ast }$, then $b_e$ is between $e$ and $f$ contradicting that $b_e$ is a leaf.

• $\mathrm{■}$

  For every $e\in I^{\ast }$ there is a core $C_e\in 𝒞$ that crosses all the sets in the white chain of $e$.

For every $e\in I^{\ast }$ chose some set $S_e$ from the white chain of $e$. The sets $S_e$ are pairwise disjoint. Since $ℱ$ is $\beta$-crossing, in any set of $\beta +1$ edges from $I^{\ast }$ there are two edges $e,f$ with $C_e\ne C_f$. Consequently

There are also $|L|$ cores contained in leaves of $T$. Thus

By Lemma 22 $w(I)-3|B|-|B^{\ast }|\le |L|+|B^{\ast }|$. Thus since $L\cup B^{\ast }\subseteq B$ we get

Consequently, $w(I)\le 4|B|+|B^{\ast }|+|𝒞|/(1+1/\beta )\le 5|𝒞|+|𝒞|/(1+1/\beta )$, as required. $◀$

Note that we proved approximation ratio $\frac{6\beta +5}{\beta +1}$. We can provide an example without edges of weight $5$ and without bad pairs such that $w(I)\approx \frac{6\beta }{\beta +1}$. Consider the example in Fig. 5. Suppose that $|L|=2^i$ and $\beta =2^j$ for some . Fig. 6 illustrates the construction for $j=1$ and $i=3$, where two nodes are colored by the same color if they belong to the same core. Consider the minimal rooted subtrees of $T$ with exactly $\beta =2^j$ leaves. Each such subtree will be exactly as in the example in Fig. 5 – the leaves are colored by distinct colors, while the other nodes in $U$ all have the same color, which we call “the color of the subtree”. For each subtree, its root is not in $U$ (the union of all cores), while the parent of the root is in $U$ and has the color of the subtree. The grandparent of the root is again a node not in $U$ and joins two subtrees; the parent of the grandparent will is colored by the color of one of these subtrees. In a similar manner we propagate the colors upwards, where a node not in $U$ joins two subtrees and its parent is colored by the color of one of these two subtrees. Note that such “coloring” does not violate the $\beta$-crossing property. In the constructed example, $w(I)=6|L|-2$ (the weight is the same ias in the example in Fig. 5) and $|𝒞|=|L|+|L|/\beta$, hence when $|L|$ is large $w(I)/|𝒞|\approx \frac{6}{1+1/\beta }=\frac{6\beta }{\beta +1}$.