$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M$
is disjoint from
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K,$
therefore it is already present in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-S.$
This contradicts that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$
completing the proof.
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\blacklozenge$

######  Claim .

Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z$
be a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-V(K)$
and let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell$
be the maximum integer666If
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v$
are not connected in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-(K\cup
Z),$ we let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell=0.$
such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-(K\cup
Z)$ contains a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{\ell}$-model
with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v$
in different sets. Then
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z^{\prime}=Z\cup
T_{\ell}$ is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$

  * Proof of Claim. Suppose not, and let $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M=(X,Y)$ be a minimal $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model in $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-Z^{\prime}$ and note that $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(X\cup Y)\cap V(K)\neq\emptyset$ since otherwise $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M$ is also a $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model in $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-(V(K)\cup Z),$ a contradiction. Due to Claim 5 and the minimality of $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M,$ we know that $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X\cup Y$ must contain both $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$ and $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v.$ Without loss of generality, let $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u\in X.$ There are two possible cases.

Case A.
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u,v\in
X$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Y\subseteq
K:$ Note that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X\setminus
V(K)]$ is connected since otherwise we have the
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M$
entirely contained in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)},$
a contradiction. This also implies that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell\geq
1.$ Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}P$
be a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(u,v)$-path
in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X\setminus
V(K)].$ Because
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{1}-T_{\ell}$
is a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X\cup
Y\cup(V(K)\setminus T_{\ell})]$ obtained by replacing
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}P$
by an edge connecting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v,$
the graph obtained from
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M=(X,Y)$
by replacing
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}P$
by an edge connecting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model
in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{1}-T_{\ell}.$
However,
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{1}-T_{\ell}$
is a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{\ell}-T_{\ell},$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{\ell}-T_{\ell}$
is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-minor-
free by the construction of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{\ell},$
a contradiction.

Case B.
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u\in
X$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
Y$: Observe that both
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(X\cap
V(K^{(u,v)}),Y\cap V(K^{(u,v)}))$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(X\setminus
V(K),Y\setminus V(K)$ are a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{i}$-model
and a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{j}$-model
for some
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i,j\geq
1$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i+j\geq
c$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}j\leq\ell<c$
by the choice of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell.$
This means that there exists a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model
in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{j}-T_{\ell}$
because
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{j}-T_{\ell}$
is a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X\cup
Y\cup(V(K)\setminus T_{\ell})]$ obtained by contracting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X\setminus
V(K)$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Y\setminus
V(K),$ and contracting these sets in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M$
preserves the property of being a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model.
However,
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{j}-T_{\ell}$
is a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{\ell}-T_{\ell}$
due to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}j\leq\ell,$
which contradict the construction of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{\ell}.$

So, in both cases we reach a desired contradiction. That is,
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z^{\prime}$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$
This proves the claim.
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\blacklozenge$

We begin with proving the second part of the statement. Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}$
be the graph where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}$
is replaced by
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{\prime(u,v)}.$
It suffices to prove the second statement for an arbitrary minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}\subseteq
V(G^{\prime})$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}.$

First, assume that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}$
contains
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
or
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v,$
say
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u.$
Claim 5 is applied to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}$
verbatim with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G\leftarrow
G^{\prime},$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K\leftarrow
K^{\prime},$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}\leftarrow
K^{\prime(u,v)},$ and we deduce that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}\cap
V(K^{\prime})=\emptyset.$ Now we take
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S\leftarrow
S^{\prime},$ and let us argue that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$
Again Claim 5 implies that if
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-S$
contains a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-model,
then one can find one disjoint from
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}V(K).$
This is not possible because
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S=S^{\prime}$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-K=G^{\prime}-K^{\prime}.$

Secondly, let us assume that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}\cap\\{u,v\\}=\emptyset.$
Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell$
be the maximum integer such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}-(K^{\prime}\cup
S^{\prime})$ contains a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{\ell}$-model
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M=(X,Y)$
with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v$
in different sets, say
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u\in
X$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
Y.$ Clearly
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell$
is strictly smaller than
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$
because
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}-K^{\prime}.$
Note that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{\prime(u,v)}_{\ell}$
is obtained from
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}[X\cup
Y\cup V(K^{\prime})]$ by contracting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Y.$
Because
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}\cap
V(K^{\prime})$ is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}[X\cup
Y\cup V(K^{\prime})],$ it is also a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{\prime(u,v)}_{\ell}.$
Therefore we have
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w_{\ell}\leq
w(S^{\prime}\cap V(K^{\prime})).$

Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S=(S^{\prime}\setminus
V(K^{\prime}))\cup T_{\ell}$ be a vertex set of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
and note that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w(S)\leq
w(S^{\prime}).$ Now applying Claim 5 to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z\leftarrow
S^{\prime}\setminus V(K^{\prime})$ (as a vertex set of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$),
we conclude that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$
This proves the second part of the statement, which also establishes
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathsf{opt}(G)\leq\mathsf{opt}({G^{\prime}})$
in the first part of the statement.

It remains to show
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathsf{opt}(G)\geq\mathsf{opt}({G^{\prime}}).$
Consider an optimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$
and let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}p$
be the maximum integer such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-(K\cup
S)$ contains a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{p}$-model
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M=(X,Y)$
with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}u$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v$
in different sets. Again we apply Claim 5 with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G\leftarrow
G^{\prime},$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z\leftarrow
S\setminus V(K)$ (as a vertex set of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}$),
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K\leftarrow
K^{\prime}$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{\ell}\leftarrow\\{x_{p}\\},$
and derive that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(S\setminus
V(K))\cup\\{x_{p}\\}$ is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}.$
Lastly, observe that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}_{p}$
is a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X\cup
Y\cup V(K)],$ and because
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S\cap
V(K)$ is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of the latter, it is also a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of the former. Therefore, we have
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w(S\cap
V(K))\geq w_{p},$ from which we have
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathsf{opt}(G)=w(S)\geq
w(S\setminus V(K))+w_{p}=w((S\setminus
V(K))\cup\\{x_{p}\\})\geq\mathsf{opt}(G^{\prime}).$ This finishes the proof. ∎

##  6 The primal-dual approach

We begin the section by formalizing the notions of replacer and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer. A
_$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$
-outgrowth replacer_ (hereinafter _replacer_) is a polynomial-time algorithm
which, given a weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G=(V,E,w)$
and a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-outgrowth
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\bf
K}=(K,u,v)$ of size at least
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c,$
outputs a weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}=(V^{\prime},E^{\prime},w^{\prime})$
with the following property.

  1. 1.

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\bf
K}$ is replaced by another
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-outgrowth
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\bf
K^{\prime}}=(K^{\prime},u,v)$ of size at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c-1.$

  2. 2.

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathsf{opt}(G)=\mathsf{opt}({G^{\prime}}).$

  3. 3.

Given a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S^{\prime}\subseteq
V(G^{\prime}),$ one can construct in polynomial time a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S\subseteq
V(G)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w(S)\leq
w(S^{\prime}).$

An
_$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$
-thin layer_ of a weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G=(V,E,w)$
is a weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H=(V,E,w^{o})$
such that the following holds.

  * •

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w^{o}(v)\leq
w(v)$ for every
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V,$

  * •

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w^{o}(v)=w(v)$
for some
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V,$ and

  * •

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w^{o}(S)\geq(1/\alpha)\cdot
w^{o}(V)$ for any
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S\subseteq
V$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H.$

We are now ready to prove our main approximation result.

######  Theorem 1.

There is a uniformly polynomial-time algorithm which, given a positive integer
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$
and a weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G=(V,E,w),$
computes a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover of weight at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha\cdot\mathsf{opt}(G)$
for some
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha=\alpha(c).$

###### Proof.

The algorithm initially sets
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{1}=G,$
and iteratively constructs a sequence of weighted graphs
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}=(V_{i},E_{i},w_{i})$
for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i=0,1,\ldots.$
At
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i$-th
iteration, we run the algorithm
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{A}$
of Theorem 1 for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t=8c.$
Recall that one of the following is the output:

  1. 1.

a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-outgrowth
of size at least
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$
or

  2. 2.

a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-model
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M$
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
of size at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\hyperref@@ii[label_quotedthepartinmy]{f_{\ref*{label_quotedthepartinmy}}}(c,8c)$
or

  3. 3.

a cluster collection
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
C}$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
of capacity at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\hyperref@@ii[label_quotedthepartinmy]{f_{\ref*{label_quotedthepartinmy}}}(c,8c)$
where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}δ(G/{\cal
C})\geq 8c,$ or

  4. 4.

a report that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\theta_{c}$-minor-
free.

If
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{A}$
detects a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-outgrowth
of size at least
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c,$
then we call the algorithm of Lemma 5, which is clearly a replacer. We run the
replacer on
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$
and set
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1}$
to be the output of the replacer. If
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-model
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M$
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$
of size at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\hyperref@@ii[label_quotedthepartinmy]{f_{\ref*{label_quotedthepartinmy}}}(c,t)$
is detected by
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{A},$
then let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\epsilon:=\min\\{w_{i}(v):v\in
M\\}$ and consider the weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}=(V_{i},E_{i},w_{i}^{o})$
with the weight function
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w$
as follows:

$w_{i}^{o}(v)=\begin{cases}\epsilon&\text{if }v\in M\\\
0&\text{otherwise.}\end{cases}$

It is obvious that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}$
is an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha=\hyperref@@ii[label_quotedthepartinmy]{f_{\ref*{label_quotedthepartinmy}}}(c,t).$

In the third case, note that the cluster collection
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
C}$ forms a cluster partition of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}[\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}].$ Consider the weight function
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w:\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}\rightarrow\mathbb{R}_{\geq 0}$ as in Equation 1 of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}[\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}].$ Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\epsilon:=\min\\{w_{i}(v)/w(v):v\in\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}\\}$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}=(V_{i},E_{i},w_{i}^{o})$
be the weighted graph, where

$w_{i}^{o}(v)=\begin{cases}\epsilon\cdot w(v)&\text{if
}v\in\boldsymbol{\boldsymbol{\bigcup}}{\cal C}\\\
0&\text{otherwise.}\end{cases}$

Let us verify that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}$
is an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$
for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha=4r,$
where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}r=\hyperref@@ii[label_quotedthepartinmy]{f_{\ref*{label_quotedthepartinmy}}}(c,t).$
It is straightforward to see that the first two requirement of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer are met due to the choice of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\epsilon.$
To check the last requirement, consider an arbitrary
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S\subseteq
V_{i}$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}.$
By Lemma 4, it holds that

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\frac{\epsilon}{2r}\cdot|E(G_{i}[\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}]/\mathcal{C})|\leq\sum_{v\in S}w_{i}^{o}(v)\leq\sum_{v\in
V_{i}}w_{i}^{o}(v)\leq
2\epsilon\cdot|E(G_{i}[\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}]/\mathcal{C})|,$

and therefore,

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\sum_{v\in
S}w_{i}^{o}(v)\geq\frac{\epsilon}{2r}\cdot|E(G_{i}[\boldsymbol{\boldsymbol{\bigcup}}{\cal
C}]/\mathcal{C})|\geq\frac{1}{4r}\cdot\sum_{v\in V_{i}}w_{i}^{o}(v).$

Now we set
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1}$
to be the weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(V_{i},E_{i},w_{i}-w_{i}^{o})$
after removing all vertices of weight zero.

Finally, if
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{A}$
reports that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$
is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-minor
free, then we terminate the iteration. Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G=G_{1},G_{2},\ldots,G_{\ell}$
be the constructed sequence of weighted graph at the end, with
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{\ell}$
being a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-minor-
free graph. Observe that our algorithm strictly decrease the number of
vertices before the
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell$-th
iteration, and thus
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ell\leq
n.$

To establish the main statement, it suffices show that there is a polynomial-
time algorithm which produces an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4r$-approximate
solution for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$
given an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4r$-approximate
solution
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{i+1}$
for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1},$
where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}r=\hyperref@@ii[label_quotedthepartinmy]{f_{\ref*{label_quotedthepartinmy}}}(c,t)$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t=8c.$
This trivially holds if the execution of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{A}$
at
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i$-th
iteration calls the replacer.

Suppose that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i$-th
iteration produces an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}=(V_{i},E_{i},w_{i}^{o}),$
and recall that every
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer produced in our algorithm satisfies
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha\leq
4r.$ As
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{i+1}$
is an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4r$-approximate
solution for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1},$
we have

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\mathsf{opt}({G_{i+1}})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle(1/4r)\cdot
w_{i+1}(T_{i+1}),$ (2)

######  Claim .

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{i}:=T_{i+1}\cup(V_{i}\setminus
V_{i+1})$ is an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4r$-approximate
solution for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}.$

  * Proof of Claim. Let $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}D_{i}=V_{i}\setminus V_{i+1},$ namely the vertices deleted from $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$ to obtain $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1}.$ It is obvious that $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{i+1}\cup D_{i}$ is a feasible solution for $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i},$ that is, a $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond cover of $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}$ because $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1}-T_{i+1}=G_{i}-(T_{i+1}\cup D_{i})$ and $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}T_{i+1}$ is a $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond cover of $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1}.$ Let $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Q\subseteq V_{i}$ be an optimal solution for $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i}.$ Then $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Q$ is a feasible solution for $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H_{i}$ and $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Q\cap V_{i+1}$ is a feasible solution for $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i+1},$ therefore

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle
w_{i}^{o}(Q)$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle(1/4r)\cdot
w_{i}^{o}(V_{i})\mbox{\leavevmode\nobreak\ and}$ (3)
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle
w_{i+1}(Q\cap V_{i+1})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\mathsf{opt}({G_{i+1}}),$
(4)

where the inequality 3 is due to the third requirement of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\alpha$-thin
layer. Furthermore, it holds that

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle
w_{i}(v)=w_{i}^{o}(v)+w_{i+1}(v)$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\mbox{\leavevmode\nobreak\
for each\leavevmode\nobreak\ }v\in V_{i+1}\mbox{\leavevmode\nobreak\ and }$
(5)
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle
w_{i}(v)=w_{i}^{o}(v)\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\mbox{\leavevmode\nobreak\
for each\leavevmode\nobreak\ }v\in D_{i}.$ (6)

Therefore,

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle
w_{i}(Q)$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=w_{i}^{o}(Q)+w_{i+1}(Q\cap
V_{i+1})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\because\eqref{label_confederation},\eqref{label_unconsciousness}$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq(1/4r)\cdot
w_{i}^{o}(V_{i})+\mathsf{opt}({G_{i+1}})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\because\eqref{label_prerequisites},\eqref{label_geometrically}$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq(1/4r)\cdot
w_{i}^{o}(T_{i+1}\cup D_{i})+(1/4r)\cdot w_{i+1}(T_{i+1})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\because\eqref{label_konstantinos}$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=(1/4r)\cdot(w_{i}^{o}(T_{i+1})+w_{i+1}(T_{i+1}))+(1/4r)\cdot
w_{i}^{o}(D_{i})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=(1/4r)\cdot
w_{i}(T_{i+1}\cup D_{i})$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\because\eqref{label_confederation},\eqref{label_unconsciousness}$

and the claim follows.
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\blacklozenge$

We inductively obtain a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4r$-approximate
solution for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{i},$
and finally for the graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G_{1}=G.$
This finishes the proof. ∎

##  7 Discussion

In this paper we construct a polynomial constant-factor approximation
algorithm for the Weighted
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$-Vertex
Deletion problem in the case
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
F}$ is the class of graphs not containing a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-bond
or, alternatively, the
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-minor
free graphs. The constant-factor of our approximation algorithm is a
(constructible) function of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$
and the running time is uniformly polynomial, that is it runs in time
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}O_{c}(n^{{\cal
O}(1)}).$ Our results, in case
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c=2,$
yield a constant-factor approximation for the Vertex Weighted Feedback Set.
Also, a constant-factor approximation for Diamond Hitting Set can easily be
derived for the case where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c=3.$
For this we apply our results on simple graphs and observe that each time a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{3}$-minor-
model appears, this model, under the absence of multiple edges, should contain
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4$
vertices and therefore is a minor-model of the diamond
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K_{4}^{-}$
(that is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K_{4}$
without an edge).

Certainly the general open question is whether Weighted
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$-Vertex
Deletion admits a constant-factor approximation for more general
instantiations of the minor-closed class
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
F}.$ In this direction, the challenge is to use our approach when the graphs
in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$
have bounded treewidth (or, equivalently, if the minor obstruction of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
F}$ contains some planar graph). For this, one needs to extend the structural
result of Section 1 and, based on this to build a replacer as in Section 5.

Given an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}r\in\mathbb{N},$
an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}r$-protrustion
of a graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is a set
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X\subseteq
V(G)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X]$
has treewidth at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}|\partial_{G}(X)|\leq
t,$ were
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\partial_{G}(X)$
is the set of vertices of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X$
that are incident to edges not in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X].$
We conjecture that a possible extension of Section 1 might be the following.

######  Conjecture .

There are functions
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}f_{3}:\mathbb{N}^{2}\to\mathbb{N}$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}f_{4}:\mathbb{N}^{3}\to\mathbb{N}$
such that, for every
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}h$-vertex
planar graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
and every two positive integers
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t,p,$
there is a uniformly polynomial time algorithm that, given as input a graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$
outputs one of the following:

  1. 1.

an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\hyperref@@ii[label_cristianesmo]{f_{\ref*{label_cristianesmo}}}(h,t)$-protrusion
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X$
of size at least
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}p,$
or

  2. 2.

a minor-model of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
of of size at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\hyperref@@ii[label_inconsistent]{f_{\ref*{label_inconsistent}}}(h,t,p),$
or

  3. 3.

a cluster collection
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
C}$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
of capacity at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\hyperref@@ii[label_inconsistent]{f_{\ref*{label_inconsistent}}}(h,t,p)$
such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}δ(G/{\cal
C})\geq t,$ or

  4. 4.

a report that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor
free.

Given a proof of some suitable version of Section 7 at hand, cases 1,2, and 3
above can be treated using the method proposed in this paper. In the first
case, we need to find a weighted prorusion replacer that can replace, in the
weighed graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G=(V,E,w),$
the subgraph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[X]$
by another one (glued on the same boundary) and create a new weighted graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}=(V^{\prime},E^{\prime},w^{\prime})$
so that an optimal solution has the same weight in both instances. In our
case, the role of a protrusion is played by the
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-outgrowth,
where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X$
is the vertex set of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}K^{(u,v)}$
that has treewidth at most
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}2c$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}|\partial_{G}(X)|\leq
2,$ i.e.,
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}V(K^{(u,v)})$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}2c$-protrusion
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$
In the case of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c},$
the the replacer is given in Section 5. The existence of such a replacer in
the general case is wide open, first because the boundary
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\partial_{G}(X)$
has bigger size (depending on
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}h$
but perhaps also on
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$)
and second, and most important, because we now must deal with weights which
does not permit us to use any protrusion replacement machinery such as the one
used in [23, 22] unweighted version of the problem (based on the, so called,
FII-property [15] for more details).

We believe that a possible way to prove Section 7 is to use as departure the
proof of the main combinatorial result in [48]. However, in our opinion, the
most challenging step is to design a weighted protrusion replacer (or, on the
negative side, to provide instantiations of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
where such a replacer does not exist). As such a replacer needs to work on the
presence of weights, we suggest that its design might use techniques related
to mimicking networks technology (see [27, 36]).

Finally, since our algorithm is based on the primal-dual framework and
proceeds by constructing suitable weights for the second and third case where
every feasible solution is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
O}(1)$-approximate, one can ask whether it is possible to bypass the need for
a replacer and construct suitable weights for the first case. Indeed, the
previous approximation algorithms for Weighted Feedback Vertex Set [7, 13, 19]
designed suitable weights even for the case 1 where every minimal solution is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
O}(1)$-approximate. (And used the additional “reverse delete” step at the end
to ensure that the final solution remains minimal, for every weighted graph
constructed.) In Appendix B, we show that such weights cannot exist for a
simple planar graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H,$
which suggests that replacers are inherently needed for this class of
algorithms for Weighted
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$-Vertex
Deletion.

## References

  * [1] A. Agrawal, S. Kolay, D. Lokshtanov, and S. Saurabh.  A faster FPT algorithm and a smaller kernel for block graph vertex deletion.  In LATIN 2016: theoretical informatics, volume 9644 of Lecture Notes in Comput. Sci., pages 1–13. Springer, Berlin, 2016.
  * [2] A. Agrawal, D. Lokshtanov, P. Misra, S. Saurabh, and M. Zehavi.  Polylogarithmic approximation algorithms for weighted-$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$-deletion problems.  In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 116 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 1, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
  * [3] A. Agrawal, D. Lokshtanov, P. Misra, S. Saurabh, and M. Zehavi.  Feedback vertex set inspired kernel for chordal vertex deletion.  ACM Trans. Algorithms, 15(1):Art. 11, 28, 2019.
  * [4] A. Agrawal, P. Misra, S. Saurabh, and M. Zehavi.  Interval vertex deletion admits a polynomial kernel.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1711–1730. SIAM, Philadelphia, PA, 2019.
  * [5] J. Ahn, E. Eiben, O.-j. Kwon, and S.-i. Oum.  A polynomial kernel for $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}3$-leaf power deletion.  In 45th International Symposium on Mathematical Foundations of Computer Science, volume 170 of LIPIcs. Leibniz Int. Proc. Inform., pages 5:1–5:14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020.
  * [6] J. Ahn, E. J. Kim, and E. Lee.  Towards constant-factor approximation for chordal / distance-hereditary vertex deletion.  In Y. Cao, S. Cheng, and M. Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 62:1–62:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [7] V. Bafna, P. Berman, and T. Fujito.  A 2-approximation algorithm for the undirected feedback vertex set problem.  SIAM J. Discret. Math., 12(3):289–297, 1999.
  * [8] N. Bansal, D. Reichman, and S. W. Umboh.  LP-based robust algorithms for noisy minor-free and bounded treewidth graphs.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1964–1979. SIAM, Philadelphia, PA, 2017.
  * [9] R. Bar-Yehuda, K. Bendel, A. Freund, and D. Rawitz.  Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon even 1935-2004.  ACM Computing Surveys (CSUR), 36(4):422–463, 2004.
  * [10] R. Bar-Yehuda and S. Even.  A local-ratio theorem for approximating the weighted vertex cover problem.  In G. Ausiello and M. Lucertini, editors, Analysis and Design of Algorithms for Combinatorial Problems, volume 109 of North-Holland Mathematics Studies, pages 27–45. North-Holland, 1985.
  * [11] J. Baste, I. Sau, and D. M. Thilikos.  A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary.  In S. Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 951–970. SIAM, 2020.
  * [12] J. Baste, I. Sau, and D. M. Thilikos.  Hitting minors on bounded treewidth graphs. I. general upper bounds.  SIAM J. Discret. Math., 34(3):1623–1648, 2020.
  * [13] A. Becker and D. Geiger.  Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.  Artificial Intelligence, 83(1):167–188, 1996.
  * [14] H. L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.
  * [15] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos.  (meta) kernelization.  J. ACM, 63(5):44:1–44:69, 2016.
  * [16] H. L. Bodlaender, J. van Leeuwen, R. B. Tan, and D. M. Thilikos.  On interval routing schemes and treewidth.  Inf. Comput., 139(1):92–109, 1997.
  * [17] Y. Cao.  Linear recognition of almost interval graphs.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1096–1115. ACM, New York, 2016\.
  * [18] R. D. Carr, L. Fleischer, V. J. Leung, and C. A. Phillips.  Strengthening integrality gaps for capacitated network design and covering problems.  In D. B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA, pages 106–115. ACM/SIAM, 2000.
  * [19] F. A. Chudak, M. X. Goemans, D. S. Hochbaum, and D. P. Williamson.  A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs.  Oper. Res. Lett., 22(4-5):111–118, 1998.
  * [20] H. Eto, T. Hanaka, Y. Kobayashi, and Y. Kobayashi.  Parameterized algorithms for maximum cut with connectivity constraints.  In B. M. P. Jansen and J. A. Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 13:1–13:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [21] S. Fiorini, G. Joret, and U. Pietropaoli.  Hitting diamonds and growing cacti.  In Integer Programming and Combinatorial Optimization – IPCO 2010, volume 6080 of Lecture Notes in Comput. Sci., pages 191–204. Springer, Berlin, 2010.
  * [22] F. V. Fomin, D. Lokshtanov, N. Misra, G. Philip, and S. Saurabh.  Hitting forbidden minors: Approximation and kernelization.  SIAM J. Discret. Math., 30(1):383–410, 2016.
  * [23] F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh.  Planar $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal F}$-Deletion: approximation, kernelization and optimal FPT algorithms.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science – FOCS 2012, pages 470–479. IEEE Computer Soc., Los Alamitos, CA, 2012.
  * [24] F. V. Fomin, D. Lokshtanov, F. Panolan, S. Saurabh, and M. Zehavi.  Hitting topological minors is FPT.  In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1317–1326. ACM, 2020.
  * [25] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Approximation schemes via width/weight trade-offs on minor-free graphs.  In S. Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2299–2318. SIAM, 2020.
  * [26] A. Gupta, E. Lee, J. Li, P. Manurangsi, and M. Wł odarczyk.  Losing treewidth by separating subsets.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1731–1749. SIAM, Philadelphia, PA, 2019.
  * [27] T. Hagerup, J. Katajainen, N. Nishimura, and P. Ragde.  Characterizing multiterminal flow networks and computing flows in networks of small treewidth.  J. Comput. Syst. Sci., 57(3):366–375, 1998.
  * [28] D. J. Haglin and S. M. Venkatesan.  Approximation and intractability results for the maximum cut problem and its variants.  IEEE Trans. Computers, 40(1):110–113, 1991.
  * [29] K. ichi Kawarabayashi, Y. Kobayashi, and B. Reed.  The disjoint paths problem in quadratic time.  Journal of Combinatorial Theory, Series B, 102(2):424–435, 2012\.
  * [30] R. Impagliazzo, R. Paturi, and F. Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.
  * [31] B. M. P. Jansen and M. Pilipczuk.  Approximation and kernelization for chordal vertex deletion.  SIAM J. Discrete Math., 32(3):2258–2301, 2018.
  * [32] G. Joret, C. Paul, I. Sau, S. Saurabh, and S. Thomassé.  Hitting and harvesting pumpkins.  SIAM J. Discret. Math., 28(3):1363–1390, 2014.
  * [33] K. Kawarabayashi and A. Sidiropoulos.  Polylogarithmic approximation for minimum planarization (almost).  In C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 779–788. IEEE Computer Society, 2017.
  * [34] E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau, and S. Sikdar.  Linear kernels and single-exponential algorithms via protrusion decompositions.  ACM Trans. Algorithms, 12(2):21:1–21:41, 2016.
  * [35] S. Kratsch and M. Wahlström.  Compression via matroids: a randomized polynomial kernel for odd cycle transversal.  ACM Trans. Algorithms, 10(4):Art. 20, 15, 2014.
  * [36] R. Krauthgamer and I. Rika.  Mimicking networks and succinct representations of terminal cuts.  In S. Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1789–1799. SIAM, 2013.
  * [37] J. M. Lewis and M. Yannakakis.  The node-deletion problem for hereditary properties is NP-complete.  J. Comput. System Sci., 20(2):219–230, 1980.  ACM-SIGACT Symposium on the Theory of Computing (San Diego, Calif., 1978).
  * [38] S. Limnios, C. Paul, J. Perret, and D. M. Thilikos.  Edge degeneracy: Algorithmic and structural results.  Theor. Comput. Sci., 839:164–175, 2020.
  * [39] D. Lokshtanov, P. Misra, F. Panolan, G. Philip, and S. Saurabh.  A (2 + $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\epsilon$)-factor approximation algorithm for split vertex deletion.  In A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 80:1–80:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [40] A. Louis, P. Raghavendra, and S. Vempala.  The complexity of approximating vertex expansion.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 360–369. IEEE, 2013.
  * [41] C. Lund and M. Yannakakis.  The approximation of maximum subgraph problems.  In A. Lingas, R. G. Karlsson, and S. Carlsson, editors, Automata, Languages and Programming, 20nd International Colloquium, ICALP93, Lund, Sweden, July 5-9, 1993, Proceedings, volume 700 of Lecture Notes in Computer Science, pages 40–51. Springer, 1993.
  * [42] G. L. Nemhauser and L. E. T. Jr.  Properties of vertex packing and independence system polyhedra.  Math. Program., 6(1):48–61, 1974.
  * [43] B. Reed, K. Smith, and A. Vetta.  Finding odd cycle transversals.  Oper. Res. Lett., 32(4):299–301, 2004.
  * [44] N. Robertson and P. D. Seymour.  Graph minors. V. excluding a planar graph.  J. Comb. Theory, Ser. B, 41(1):92–114, 1986.
  * [45] N. Robertson and P. D. Seymour.  Graph minors. XX. Wagner’s conjecture.  J. Comb. Theory, Ser. B, 92(2):325–357, 2004.
  * [46] I. Sau, G. Stamoulis, and D. M. Thilikos.  An fpt-algorithm for recognizing k-apices of minor-closed graph classes.  In A. Czumaj, A. Dawar, and E. Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 95:1–95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [47] A. Thomason.  The extremal function for complete minors.  J. Comb. Theory Ser. B, 81(2):318–338, 2001.
  * [48] W. C. van Batenburg, T. Huynh, G. Joret, and J. Raymond.  A tight erdős-pósa function for planar minors.  In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1485–1500. SIAM, 2019.

##  Appendix A The case of big minimum edge-degree

It is known that if
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
F}$ is a non-trivial minor-closed graph class, then there is some
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}d_{\cal
F}$ such that for every (multi) graph in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
F}$ it holds that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}|E(G)|\leq
μ(G)\cdot d_{\cal F}\cdot|V(G)|$ (see e.g. [47]).

######  Lemma .

Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
be an instance of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$-Vertex
Deletion where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}μ(G)\leq
m$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\delta(G)\geq
3m\cdot d_{\cal F}.$ Then for every solution
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X$
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathcal{F}$-Vertex
Deletion on
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$
it holds that

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}|E(G)|\leq
2\sum_{v\in X}{\sf edeg}_{G}(v)\leq 4|E(G)|.$

###### Proof.

We prove the first inequality as the second one is obvious. Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}F:=G-X$
,
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}d:=d_{\cal
F},$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}b:=\delta(G)\geq
3md.$ Observe that

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle|E(X,F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=\sum_{v\in
F}{\sf edeg}_{G}(v)-\sum_{v\in F}{\sf edeg}_{F}(v)$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq
b\cdot|V(F)|-2|E(F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq
b\cdot|V(F)|-2md\cdot|V(F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\because|E(F)|\leq
md\cdot|V(F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq
md\cdot|V(F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\because
b\geq 3md$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq|E(F)|$

Therefore, we deduce

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\sum_{v\in
X}{\sf edeg}_{G}(v)$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=2|E(X)|+|E(X,F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=\frac{1}{2}|E(X)|+\frac{1}{2}|E(X,F)|+\frac{1}{2}|E(X,F)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle\geq\frac{1}{2}\big{(}|E(X)|+|E(X,F)|+|E(F)|\big{)}$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=\frac{1}{2}\cdot|E(G)|$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=\frac{1}{4}\cdot\sum_{v\in
V(G)}{\sf edeg}_{G}(v)$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\displaystyle=\frac{1}{2}|E(G)|$

as claimed. ∎

In the special case where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
F}$ is the class of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-free
graphs, we know, from Section 2.i, that every simple
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}θ_{c}$-minor
free graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
satisfies
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}E(G)\leq
2c\cdot|V(G)|.$ As for such graphs
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}μ(G)<c,$
we can apply the above lemma for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}d_{\cal
F}=2.$ Therefore, given an instance
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
of (unweighted)
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-Bond
Cover where
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\delta(G)\geq
6c,$ every feasible solution
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X$
is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}4$-approximation.
This implies that if we set
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w(v):={\sf
edeg}_{G}(v)$ for every
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V,$ every feasible solution to Weighted
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}c$-Bond
Cover is a 4-approximate solution.

##  Appendix B Necessity of a replacer

The previous approximation algorithms for Weighted Feedback Vertex Set, at
least the ones stated in [7, 13, 19], did not use the notion of a replacer
that we introduce here. Instead, these algorithms use the primal-dual
framework by always finding suitable weightings
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w:V(G)\to\mathbb{R}_{\geq
0}$ of the current graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
such that any minimial feedback vertex set (i.e., cycle cover) for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}2$-approximate
solution with respect to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w.$
(In this section, minimality is defined with respect to set inclusion.) The
existence of such a weighting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w$
relies on the fact that, for any induced path
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}P$
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$
any minimal feedback vertex set has at most one internal vertex from
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}P.$
We prove the following lemma revealing that such weights cannot exist for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor
cover for some planar graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H.$
(In fact, every graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
that satisfies the mild technical conditions (1) and (2) in the proof.)

######  Lemma .

There exists a fixed planar graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
such that the following holds. For infinitely many values of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}n,$
there exists an
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}n$-vertex
graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
such that for any weighting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w:V(G)\to\mathbb{R}_{\geq
0},$ there exists a minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor
cover
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S\subseteq
V(G)$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w(S)=\Omega(n)\cdot\mathsf{opt}(G).$

###### Proof.

Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
be any 2-connected planar graph with treewidth at least five (for this, one
may just take the
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(5\times
5)$-grid). Choose
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s,t\in
V(H)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\\{s,t\\}\in
E(H).$ Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}k$
be any parameter bigger than five. The graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is constructed as follows.

  * •

Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}R=\\{0,1,2,3\\}\times[k]$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}V(G)=V(H)\cup
R.$ So
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}n=4k+|V(H)|.$

  * •

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}E(G)$
consists of the following edges
($\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\oplus$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\ominus$
denotes the addition and subtraction modulo 4 respectively).

    * –

the edges in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}E(H)\setminus\\{\\{s,t\\}\\}.$

    * –

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$
is adjacent to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(i,1)$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$
is adjacent to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(i,k)$
for each
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i\in\\{0,1,2,3\\}.$

    * –

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[R]$
is the
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(4\times
k)$-grid. Formally, for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}1\leq
j\leq k$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}0\leq
i<3,$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}E(G)$
contains the edge
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\\{(i,j),(i\oplus
1,j)\\}$. Moreover, for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}1\leq
j<k$ and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}0\leq
i<3,$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}E(G)$
contains the edges
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\\{(i,j),(i,j+1)\\}$.

Let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z:=G[\\{s,t\\}\cup
R].$ We need the following two properties of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
(we remark that the lemma is true for any
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
that satisfies them):

  * (1)

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}2$-vertex
connected and

  * (2)

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
is not a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z.$

For the above, it is easy to verify that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z=G[\\{s,t\\}\cup
R]$ has treewidth at most four, therefore it cannot contain as a minor the
graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
that has treewidth at least five.

For
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}1\leq
j\leq k,$ let
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Y_{j}=\\{(0,j),(1,j),(2,j),(3,j)\\}$
and notice that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Y_{i}$
is a minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$-$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$
separator of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}R$
(that is
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$
are in different connected components of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}R-S$
and none of its subsets has this property). In the proof of the following
claim, by
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor-
model we mean a cluster collection
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal
M}=\\{M_{v}\mid v\in V(H)\\}$ of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G/{\cal
M}$ is equal to
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
with possibly some additional edges.

######  Claim .

If
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$
is a minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$-$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$
separator of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z$,
then
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$

  * Proof of Claim. Once $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}S$ is removed from $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$ there is no $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$-$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$ path in $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z.$ Let $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}A\subseteq R$ be the vertices connected to $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$ and $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}B\subseteq R$ be the vertices connected to $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$ (so $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(A,B,S)$ is a partition of $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}R$). Assume towards contradiction that there exists a $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor-model $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}{\cal M}=\\{M_{v}\mid v\in V(H)\\}$ of $\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G^{\prime}=G-S.$ We consider the following cases.

    * –

If there exists some
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V(H)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{v}\subseteq
A,$ the 2-vertex-connectivity of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
ensures that there is no
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w\in
V(H)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{w}\subseteq
V(G-S)\setminus(A\cup\\{s\\}),$ since
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$
is a singleton vertex cut separating
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}A$
and
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}V(G-S)\setminus(A\cup\\{s\\}).$
By letting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{v}\leftarrow
M_{v}\cap(A\cup\\{s\\})$ for each
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V(H),$ this implies that there exists a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-model
contained in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}A\cup\\{s\\},$
which contradicts the fact
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
is not a minor of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G[\\{s\\}\cup
R].$ Similarly, there is no
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V(H)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{v}\subseteq
B.$

    * –

Then there is no
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V(H)$ such that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{v}\subseteq
A$ or
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{v}\subseteq
B.$ In that case, letting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}M_{v}\leftarrow
M_{v}\setminus(A\cup B)$ for each
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}v\in
V(H)$ gives a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-model
of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-S$
entirely contained in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}V(G-S)\setminus(A\cup
B).$ But note that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G-(S\cup
A\cup B)=G-R$ is exactly
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$
minus one edge, so contradiction.

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\blacklozenge$

On the other hand, we define, for
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}0\leq
i<3,$ the sets

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X_{i}=(\\{i\ominus
1\\}\times\\{2,\dots,k-1\\})\cup(\\{i\oplus
1\\}\times\\{2,\dots,k-1\\})\cup\\{(i,k),(i\oplus 2,1)\\}.$

By construction, in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z,$
each
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X_{i}$
is a minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}s$-$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}t$
separator. Therefore,
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X_{i}$
is a minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor-
cover of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G.$

For any
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w:V(G)\to\mathbb{R}_{\geq
0},$ note that
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\sum_{j=1}^{k}w(Y_{j})\leq\frac{1}{2}\sum_{i=0}^{3}w(X_{i}).$
Indeed, for each
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(i,j)\in
R,$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}(i,j)$
appears at least twice in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\\{X_{0},X_{1},X_{2},X_{3}\\}$
and exactly once in
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\\{Y_{j}:1\leq
j\leq k\\}.$ Since each
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Y_{j}$
is a
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-minor
cover, it holds that

$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}k\cdot\mathsf{opt}^{(w)}(G)\leq\sum_{j=1}^{k}w(Y_{j})\leq\frac{1}{2}\sum_{i\in\\{0,1,2,3\\}}w(X_{i}).$

(Here we denote by
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\mathsf{opt}^{(w)}(G)$
the optimum value attained with respect to the weighting
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}w.$)
Therefore, for some
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}i,$
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}X_{i}$
is a minimal
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$-cover
whose weight is at least
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}\frac{k}{2}\cdot\mathsf{opt}^{(w)}(G).$
As
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}|V(G)|=25+4k,$
the lemma follows. ∎

We stress that in the above proof, the treewidth of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is always equal to five (that is the treewidth of
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}H$).
This means that one may not expect a better behaviour than the one testified
by Appendix B, even when restricted to graphs of fixed treewidth. Notice also
that the graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G$
is not planar (while the graph
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}Z$
is). Any construction of a planar
$\color[rgb]{0.1,0.1,0.28}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.28}G,$
as in Appendix B, seems to be an interesting challenge.