Protrusion Decompositions Revisited:
Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors

In order to overcome known barriers against polynomial kernels [3, 8], researchers started to study a lossy variant of kernelization [23]. Intuitively, an $\alpha$-approximate kernel reduces the task of finding an approximate solution to an instance of size $\mathrm{𝗉𝗈𝗅𝗒}(k)$ where $k$ bounds the optimum. Here, the approximation factor $\alpha$ measures how much is “lost in translation” between the two instances: a $c$-approximate solution is translated to an $(\alpha \cdot c)$-approximate solution. Such lossy kernels have been studied for Vertex Planarization [18] and for $ℱ$-Deletion with a connectivity constraint on solution [7, 24]. To capture the difficulty of an approximation task by parameter $k$, solutions larger than $k$ are treated as equally bad and we define their cost as $k+1$ [23].

Analogously to exact kernelization, one can allow the algorithm to repeatedly call an oracle that (approximately) solves an instance of bounded size. Assuming that the oracle processes instances of size $\mathrm{𝗉𝗈𝗅𝗒}(k)$, such an algorithm is called an (approximate) polynomial Turing kernelization [16, 21]. A restricted model in which the number of oracle calls is bounded by $\mathrm{𝗉𝗈𝗅𝗒}(k)$ (so, in particular, it does not depend on the input size) has been dubbed a lossy kernelization protocol [9]. In fact, allowing just two oracle calls unlocks technical tools unavailable for currently known one-shot lossy kernels [9]. Whereas there are problems that admit an exact polynomial Turing kernel and are unlikely to admit a regular polynomial kernel [17], the current lower bound techniques do not distinguish whether the oracle is called $\mathrm{𝗉𝗈𝗅𝗒}(k)$ times or just once [8, §21]. It is therefore an intriguing question if and how (lossy) kernelization protocols can outperform one-shot (lossy) kernels.

In this paper we address the two raised issues that trouble the existing kernelization algorithms for $ℱ$-Deletion. First, we show that a uniform polynomial kernelization for Treewidth-$\eta$-Deletion is possible if we settle for 2-approximation. This should be compared to polynomial-time $𝒪(\log \eta )$-approximation algorithm for Treewidth-$\eta$-Deletion [15] whereas $c$-approximation with an absolute constant $c$ remains elusive. Our result extends to $ℱ$-Deletion  for any family $ℱ$ containing a planar graph, modulo the fact that we still need an oracle solving Treewidth-$\eta$-Deletion. As the oracle problem differs from the original one, we obtain a slightly weaker result, namely a lossy polynomial compression.

We can improve the approximation factor from 2 to $(1+ϵ)$ for any $ϵ>0$ by calling the oracle in several rounds. The number of rounds, as well as the degree in the kernel size, depend only on $ϵ$. Hence we obtain a uniform lossy compression protocol with approximation factor arbitrary close to 1 and with constant number of rounds.

The proofs of Theorems 1 and 2 rely on “protrusion techniques” [8, §16]. An $r$-protrusion is a vertex subset $X\subseteq V(G)$ such that (i) treewidth of $G[X]$ is at most $r$ and (ii) $X$ contains at most $r$ vertices with a neighbor outside $X$. A graph $G$ admits an $(\alpha ,\beta )$-protrusion decomposition if there is a vertex subset $P_0\subseteq V(G)$ of size $\le \alpha$ so that $G-P_0$ can be covered by $\alpha$ many $\beta$-protrusions (see Section 2 for formal definitions). In the proofs we transform so-called near-protrusion decompositions [11] into true protrusion decompositions with bounded parameters $\alpha ,\beta$ by sacrificing small accuracy loss. The known techniques can compress such structures in a uniform fashion as long as all graphs in the family $ℱ$ are connected. To tackle the remaining cases, we prove the following lemma. Here, ${\mathrm{𝗈𝗉𝗍}}_{ℱ}(G)$ denotes the minimum size of a solution to $ℱ$-Deletion in $G$, i.e., an $ℱ$-deletion set.

We remark that the factor hidden in the $𝒪(\cdot )$-notation is a computable function of $(ℱ,\beta )$. See Lemma 14 for a full statement tailored for lossy kernelization. As a corollary of Lemma 3 we obtain linear kernels on graph classes where one can compute an $(𝒪(k),𝒪(1))$-protrusion decomposition. The most general cases where such a construction is known are classes with excluded topological minor [19]. Whereas the known linear kernels for $ℱ$-Deletion require all the graphs in $ℱ$ to be connected [4, 12, 13, 19], we are able to drop this assumption.

We begin with an informal exposition of our main technical ideas in Section 3. The most of the remaining space is devoted to Lemma 3 (Section 4) which is too technical to be covered in the overview. We prove Theorems 1 and 2 in Sections 5 and 6. Since Theorem 4 follows from Lemma 3 and previous results, it is given in the full version of the article. The full version also contains the proofs of lemmas marked with $(\mathrm{★})$ as well as background on tree decompositions and lossy kernelization.

For any $\beta \in \mathbb{N}$, a $\beta$-protrusion in a graph $G$ is a vertex set $X\subseteq V(G)$ such that the treewidth of $G[X]$ is at most $\beta$ and $|{\partial }_G(X)|\le \beta$, where ${\partial }_G(X)=N_G(V(G)\setminus X)$. When $G$ is clear from the context, we drop the subscript.

Fix $i\in [1,\mathrm{\ell }]$. By definition, we have that $|\partial (N[P_i])|=|N(V(G)\setminus N[P_i])|\le \beta$. Suppose that $v\in N(P_i)\setminus \partial (N[P_i])$. Then $N(v)\subseteq N[P_i]$ and moving $v$ from $P_0$ to $P_i$ does not alter the set $N[P_i]$, hence $N[P_i]\cup \{v\}$ remains a $\beta$-protrusion. After performing such an operation exhaustively for each $i\in [1,\mathrm{\ell }]$ and $v\in N(P_i)\setminus \partial (N[P_i])$, we obtain a nice $(\alpha ,\beta )$-protrusion decomposition. $◀$

A $t$-boundaried graph is a triple $𝐇=(H,B,\lambda )$ where $H$ is a graph, $B\subseteq V(H)$ is of size $t$ and $\lambda :[t]\to B$ is a bijection representing a labeling function. We refer to the set $B$ as $\partial 𝐇$ and call it the boundary of $𝐇$. By $V(𝐇)$ we refer to $V(H)$. Given two $t$-boundaried graphs ${𝐇}_{\mathrm{𝟏}}=(H_1,B_1,{\lambda }_1)$ and ${𝐇}_{\mathrm{𝟐}}=(H_2,B_2,{\lambda }_2)$, ${𝐇}_{\mathrm{𝟏}}\oplus {𝐇}_{\mathrm{𝟐}}$ denotes the graph $H$ obtained by first taking the disjoint union of $H_1$ and $H_2$ and then identifying each vertex $u_1$ in $B_1$ with $u_2\in B_2$ such that ${\lambda }_1^{-1}(u_1)={\lambda }_2^{-1}(u_2)$. For $h\in \mathbb{N}$ and a graph $G$, $h$-folio$(G)$ is the set of all graphs on at most $h$ vertices which appear in $G$ as a minor.

The proof of Lemma 9 appears in the full version for completeness and follows the proof of [13, Theorem $1.1$]. Note that the key highlight of Lemma 9 is that the function $\gamma$ is computable and the family $ℱ$ is arbitrary (and not necessarily of connected graphs).

We would like to transform the current decomposition into a $({𝒪}_{\eta }(k^c),{𝒪}_{\eta }(1))$-protrusion decomposition, where $c$ does not depend on $\eta$. We call a component $C$ of $G-(X\cup Z)$ simplicial if $N(C)$ forms a clique. Because we can insert edges between highly connected vertices in $X\cup Z$, each non-edge may appear only in a bounded number of sets $N(C)$. We use this argument to bound the number of non-simplicial components by ${𝒪}_{\eta }(k^5)$. Let us neglect the simplicial components for a moment and let $G^{\prime }$ denote the graph without them. Then $G^{\prime }$ admits a protrusion decomposition of desired form and we can compress $G^{\prime }$ to $G^{\prime \prime }$ on ${𝒪}_{\eta }(k^5)$ vertices. This is the output of the kernelization algorithm.

It remains to provide a mechanism to lift a solution $S^{\prime \prime }$ from $G^{\prime \prime }$ to $G$. First, we note that a solution $S^{\prime \prime }$ can be lifted to a solution $S^{\prime }$ of $G^{\prime }$ using standard tools. The interesting step is lifting $S^{\prime }$ to a solution $S$ in $G$. This is the part where the lifting step of the algorithm does a nontrivial (yet, polynomial-time) computation exploiting a treewidth bound. Consider a tree decomposition $𝒯$ of $G^{\prime }-S^{\prime }$ of width $\eta$ and a simplicial component $C$ of $G-(X\cup Z)$. Since $N(C)\setminus S^{\prime }$ is a clique, it must be covered by some bag in $𝒯$. Therefore, we can plug $G[N[C]]$ into $𝒯$ by merging a tree decomposition of $G[N[C]]$ of width $2\eta +1$ and the tree decomposition $𝒯$ alongside $N(C)\setminus S^{\prime }$. This argument bounds the treewidth of $G-S^{\prime }$ by $2\eta +1$ and on such a graph we can solve Treewidth-$\eta$-Deletion exactly in polynomial time. We output the union of $S^{\prime }$ and the optimal solution in $G-S^{\prime }$, resulting in 2-approximation.

Improving the approximation factor below $2$ requires a different approach. We can still start with the sets $X\cup Z$ as described in the beginning of this section, and make each connected component $C$ of $G-(X\cup Z)$ a protrusion, this time by removing a clique in the neighbourhood of $C$ whose size is at least $(\eta +1)(1+ϵ)/ϵ$. The main challenge is to bound the number of simplicial protrusions. Let $Y_0=X\cup Z$. Since we now aim at a lossy kernelization protocol, we can send $G[Y_0]$ to the oracle which outputs $Y_1\subseteq Y_0$ for which $\text{tw}(G[Y_0\setminus Y_1])\le \eta$. Assume for simplicity that the oracle always returns an optimal solution. Then $|Y_1|=\mathrm{𝗈𝗉𝗍}(G[Y_0])\le \mathrm{𝗈𝗉𝗍}(G)$. And once again, we ask the oracle for a solution $Y_2$ in $G[Y_1]$.

Suppose first that $|Y_2|>(1-\epsilon )\cdot |Y_1|$. Observe that any optimal solution $S$ in $G$ satisfies $|S\cap Y_1|\ge \mathrm{𝗈𝗉𝗍}(G[Y_1])$ so $\mathrm{𝗈𝗉𝗍}(G-Y_1)\le \mathrm{𝗈𝗉𝗍}(G)-(1-\epsilon )\cdot |Y_1|$. A crucial observation is that removing $Y_1$ from $G$ allows us to construct an $({𝒪}_{\eta }(k^5),{𝒪}_{\eta }(1))$-protrusion decomposition. For each simplicial component $C$, the set $N(C)\setminus Y_1$ forms a clique in the graph $G[Y_0\setminus Y_1]$ of treewidth $\le \eta$. But the number of cliques in a bounded-treewidth graph is linear so we can group the simplicial components into ${𝒪}_{\eta }(|Y_0\setminus Y_1|)$ protrusions according to their neighborhoods in $Y_0\setminus Y_1$. Together with ${𝒪}_{\eta }(k^5)$ non-simplicial components, this allows us to compress the graph $G-Y_1$ into size ${𝒪}_{\eta }(k^5)$. Let $S_1$ be the solution in $G-Y_1$ computed with the help of the oracle. Assuming $|S_1|=\mathrm{𝗈𝗉𝗍}(G-Y_1)$ we get $|S_1|+|Y_1|\le \mathrm{𝗈𝗉𝗍}(G)-(1-\epsilon )\cdot |Y_1|+|Y_1|=\mathrm{𝗈𝗉𝗍}(G)+ϵ\cdot |Y_1|\le (1+ϵ)\cdot \mathrm{𝗈𝗉𝗍}(G)$.

Suppose now that $|Y_2|\le (1-\epsilon )\cdot |Y_1|$. We continue asking the oracle for solution $Y_{i+1}$ in $G[Y_i]$. Let $j$ be the first iteration for which $|Y_{j+1}|>(1-\epsilon )\cdot |Y_j|$. We repeat the same trick but this time the set $Y_0\setminus Y_j$ is partitioned into $j$ subsets $(Y_0\setminus Y_1),(Y_1\setminus Y_2),\mathrm{\dots },(Y_{j-1}\setminus Y_j)$, each inducing a graph of treewidth $\le \eta$. The number of cliques in $G[Y_0\setminus Y_j]$ can be bounded by $f(\eta ,j)\cdot {|Y_0|}^j$, allowing us to construct an $({𝒪}_{\eta ,j}(k^{𝒪(j)+5}),{𝒪}_{\eta ,j}(1))$-protrusion decomposition.

This procedure yields a uniform kernelization protocol as long as $j$ can be bounded. But suppose we keep getting outcome $|Y_{j+1}|\le (1-\epsilon )\cdot |Y_j|$. Then for $r=1+\lceil {\log }_{1-ϵ}(ϵ)\rceil$ we obtain $|Y_r|\le {(1-\epsilon )}^{r-1}\cdot |Y_1|=\epsilon \cdot |Y_1|\le \epsilon \cdot \mathrm{𝗈𝗉𝗍}(G)$. In this case we can again use the oracle to compute a solution in $G-Y_r$, bounding the number of protrusions by ${|Y_0|}^r$, and merge it with $Y_r$, achieving $(1+\epsilon )$-approximation. See Figure 3 on page 3 for an illustration.

In order to handle $ℱ$-Deletion, we need to be more careful because inserting an edge between highly connected vertices may no longer be safe. To this end, we introduce an auxiliary graph which collects these inserted edges and exploit the fact that the optimum to $ℱ$-Deletion can be lower bounded by the optimum to Treewidth-$\eta$-Deletion, for some $\eta =\eta (ℱ)$. We need to ask the oracle for solutions to Treewidth-$\eta$-Deletion over the auxiliary graph as well, and this is the reason why in general we end up with compression protocol, rather than kernelization protocol. Whereas the standard protrusion replacement technique suffices to finish the construction when all the graphs in $ℱ$ are connected, dealing with the general case requires one more tool.

There are two known ways to compress protrusions in the presence of disconnected graphs in $ℱ$. First, one can consider an annotated version of $ℱ$-Deletion, where some vertices are marked as undeletable [4], but this requires the oracle to solve a significantly harder task. Secondly, one can take advantage of a certain well-quasi-order over boundaried graphs [11] but this involves a non-constructive argument and results in factors that a priori may be an uncomputable function of $ℱ$. Besides, both approaches are insufficient to construct a linear kernel in Theorem 4.

To visualize the issue, consider $F=K_4+C_5$ and an $(\alpha ,\beta )$-protrusion decomposition $(P_0,P_1,\mathrm{\dots },P_{\mathrm{\ell }})$ of a graph $G$. It may be the case that $G[P_i]$ is $K_4$-free for some $i\in [1,\mathrm{\ell }]$ but it contains a lot of minor models of $C_5$. Depending on whether a solution to $F$-Deletion hits all the copies of $K_4$ outside $P$, it may need to remove either none or a very large number of vertices in $P$. In fact, such a problem does not admit finite integer index [19], a property crucial for protrusion replacement [4, 13].

Observe however that if $G[P_i]$ contains a disjoint packing of $k+1$ minor models of $C_5$, then we already know that no solution of size $\le k$ can make the graph $C_5$-minor-free, so it should “focus” on hitting the $K_4$-minors. There is a caveat though: it might be the case that the only minor model of $K_4$ in $G$ intersects each model of $C_5$ and so $K_4+C_5$ already does not appear as a minor. In order to circumvent such error-prone corner cases, we refine an $(\alpha ,\beta )$-protrusion decomposition to one with dichotomy property. It states that for every connected graph $F$ on at most $h$ vertices (where $h$ is the maximum graph size in $ℱ$) either $F$ does not appear as a minor in $G-P_0$ or $F$ has a large “private” collection of protrusions in which it appears. This property implies that any optimal solution $S$ can use only ${𝒪}_{ℱ,\beta }(1)$ vertices from each protrusion, mimicking the missing separation property. Intuitively, the aforementioned collections justify that any solution $S$ of size $\le k$ must focus on hitting minors that do not appear in $G-P_0$, and so it does not make sense to remove too many vertices from a single protrusion. Consequently, the constructive protrusion replacement by Garnero et al. [13] can be adapted to compress protrusions in a decomposition with the dichotomy property.

To construct a decomposition with dichotomy property we generalize the packing/covering duality for connected minor models in bounded-treewidth graphs [25]. In our case however we do not pack models of a single graph $F$ but we consider a family of connected graphs ${ℱ}^{\prime }$ and in each step of a greedy procedure we need to choose one graph $F\in {ℱ}^{\prime }$ to be packed, without spoiling the invariants for the remaining graphs from ${ℱ}^{\prime }$. The details are technical and we omit them here.

Let ${\mathscr{H}}_G\subseteq {\mathscr{H}}_h^{\mathrm{𝖼𝗈𝗇𝗇}}$ be the family of those connected graphs on at most $h$ vertices that appear as minors in $G-P_0$. Due to $(k,h)$-dichotomy property, for each $H\in {\mathscr{H}}_G$ there is a collection $I(H)\subseteq [1,\mathrm{\ell }]$ of size $k+h$, such that for $i\in I(H)$ we have $H{\le }_{m}G[P_i]$ and the sets $I(H)$ are disjoint for distinct graphs $H$ from ${\mathscr{H}}_G$. Since $|S|\le k$, for some $h$ indices $i\in I(H)$ the set $P_i$ is disjoint from $S$. Let us denote this subset as $J_H\subseteq I(H)$. Consequently, for each $H\in {\mathscr{H}}_G$ we have $|J_H|=h$, the sets $J_H$ are pairwise disjoint, and for each $i\in J_H$ it holds that $H{\le }_{m}G[P_i]$ and $P_i\cap S=\mathrm{\varnothing }$, Note that ${\sum }_{H\in {\mathscr{H}}_G}|J_H|\le h\cdot |{\mathscr{H}}_h^{\mathrm{𝖼𝗈𝗇𝗇}}|$.

Suppose that there exists $j\in [1,\mathrm{\ell }]$ for which $|S\cap P_j|>\beta \cdot (h\cdot |{\mathscr{H}}_h^{\mathrm{𝖼𝗈𝗇𝗇}}|+1)$. W.l.o.g. we will assume that $j=1$. Let $\widehat{S}$ be obtained from $S$ by (1) removing $S\cap P_1$, (2) inserting $N(P_1)$, (3) inserting $N(P_i)$ for every $i\in J_H$, $H\in {\mathscr{H}}_G$ (see Figure 1). Note that because the given protrusion decomposition is nice.

We will now prove that $\widehat{S}$ is also an $ℱ$-deletion set. Suppose not, and let $F\in ℱ$ be a graph appearing in $G-\widehat{S}$ as a minor. Let $F_1,\mathrm{\dots },F_c$, $c\le h$, be the connected components of $F$. Note that some of them may be isomorphic. Consider a minor model $\mathrm{\Phi }$ of $F$ in $G-\widehat{S}$ for which the number of $F_j$ appearing in $P_1$ is minimized. More precisely, we minimize the number $c^{\prime }$ of indices $j\in [c]$ for which $\mathrm{\Phi }(V(F_j))\subseteq P_1$. Observe that $P_1$ is a union of connected components of $G-\widehat{S}$ so if $\mathrm{\Phi }(V(F_j))$ intersects $P_1$ then it must be fully contained in $P_1$. If $c^{\prime }=0$ then $F$ is a minor of $G-(P_1\cup \widehat{S})$. But this is an induced subgraph of $G-S$, which is $ℱ$-minor-free by assumption, so this is impossible.

Consequently, the minor model $\mathrm{\Phi }$ places $c^{\prime }\ge 1$ connected components of $F$ inside $P_1$. Assume w.l.o.g. that this is the case for $F_1$. Aiming at contradiction, we want to modify $\mathrm{\Phi }$ to place $F_1$ outside $P_1$, without affecting the models of remaining $F_j$, $j>1$. Since $F_1{\le }_{m}G[P_1]$ it follows that $F_1\in {\mathscr{H}}_G$. Recall that for each $i\in J_{F_1}$ it holds that $\widehat{S}\cap P_i=\mathrm{\varnothing }$ (because $S\cap P_i=\mathrm{\varnothing }$) and $N(P_i)\subseteq \widehat{S}$. Since each $F_j$ is connected, $\mathrm{\Phi }(F_j)$ can intersect at most one $P_i$ for $i\in J_{F_1}$. Next, $|J_{F_1}|=h$ and $c\le h$, so there is some $i\in J_{F_1}$ for which $P_i$ is disjoint from all $\mathrm{\Phi }(F_j)$, $j>1$. Therefore, we can move the model of $F_1$ from $P_1$ to $P_i$, obtaining a model ${\mathrm{\Phi }}^{\prime }$ of $F$ in $G-\widehat{S}$ with $c^{\prime }-1$ components contained in $P_1$. This contradicts the choice of the model $\mathrm{\Phi }$ and, consequently, contradicts the assumption that $F{\le }_{m}G-\widehat{S}$. Hence $\widehat{S}$ is a valid $ℱ$-deletion set.

We can repeat this process to reduce the intersection of $\widehat{S}$ with each $P_i$ because the described modification to $S$ never adds new vertices from any $P_i$. A single refinement step can be implemented in polynomial time using any polynomial-time algorithm for minor testing, for example [27, 20], which also yields an algorithm to construct $\widehat{S}$. Observe that if $G$ has an $ℱ$-deletion set of size at most $k$, then every minimum $ℱ$-deletion set $S$ in $G$ must satisfy $|S\cap P_i|\le \beta \cdot (h\cdot |{\mathscr{H}}_h^{\mathrm{𝖼𝗈𝗇𝗇}}|+1)$ as otherwise we could find a smaller $ℱ$-deletion set. $◀$

We can now combine Lemma 13 with Lemma 9 to compress each $P_i$ in a protrusion decomposition to a constant size. It is crucial that Lemma 9 preserves the $h$-folio of $G[P_i]$ therefore the dichotomy property is maintained after the replacement. The last point of the lemma statement refers to the solution cost capped at $k+1$, which will be convenient in the design of a lossy kernelization protocol.

We apply Lemma 12 to construct a nice $(\widehat{\alpha },\widehat{\beta })$-protrusion decomposition $(P_0,P_1,\mathrm{\dots },P_{\mathrm{\ell }})$ with the $(k,h)$-dichotomy property, where $\widehat{\alpha }=\alpha +{𝒪}_{h,\beta }(k)$ and $\widehat{\beta }={𝒪}_{h,\beta }(1)$. Let $d:=\widehat{\beta }\cdot (h\cdot |{\mathscr{H}}_h^{\mathrm{𝖼𝗈𝗇𝗇}}|+1)$. We will iteratively replace each protrusion induced by $N_G[P_i]$ with one of constant size using Lemma 9. Below we describe this process for $P_1$.

We fix some labeling $\lambda$ of ${\partial }_G(N_G[P_1]))$ and replace the boundaried graph $𝐇=(G[N[P_1]],N(P_1),\lambda )$ with a boundaried graph $\widehat{𝐇}$ of size ${𝒪}_{h,\widehat{\beta },d}(1)\in {𝒪}_{h,\beta }(1)$. Denote the new graph $G^{\prime }$ and let $P_1^{\prime }$ be the set of vertices put in place of $P_1$.

By Lemma 13 there exists an optimal $ℱ$-deletion set $S$ in $G$ such that $|S\cap P_1|\le d$. Lemma 9 guarantees that such an $S$ can be translated to an $ℱ$-deletion set in $G^{\prime }$ of size at most $|S|$. $\mathrm{⊲}$

Lemma 9 ensures that $h$-folio$(𝐇-\partial 𝐇)=h$-folio$(\widehat{𝐇}-\partial \widehat{𝐇})$ which can be rewritten as $h$-folio$(G[P_1])=h$-folio$(G^{\prime }[P_1^{\prime }])$. If $P_1$ contributed a minor model to the minor packing corresponding to $(k,h)$-dichotomy property, it can be replaced by a minor model of the same graph in $G^{\prime }[P_1^{\prime }]$. $\mathrm{⊲}$

The previous claim allows us to apply Lemma 13 to graph $G^{\prime }$ and $S^{\prime }$. Given $S^{\prime }$ we can in polynomial time find an $ℱ$-deletion set $\widehat{S}$ in $G^{\prime }$ of size $\le |S^{\prime }|$ for which $|\widehat{S}\cap P_1^{\prime }|\le d$. By applying Lemma 9 we can lift $\widehat{S}$ to a solution in $G$ of size at most $|\widehat{S}|\le |S^{\prime }|$. By taking $S^{\prime }$ to be an optimal $ℱ$-deletion set in $G^{\prime }$, we infer that ${\mathrm{𝗈𝗉𝗍}}_{ℱ}(G)\le {\mathrm{𝗈𝗉𝗍}}_{ℱ}(G^{\prime })$. $\mathrm{⊲}$

Claims 15 and 17 imply that $\min ({\mathrm{𝗈𝗉𝗍}}_{ℱ}(G),k+1)=\min ({\mathrm{𝗈𝗉𝗍}}_{ℱ}(G^{\prime }),k+1)$ and provide a mechanism to lift a bounded-size solution from $G^{\prime }$ to $G$ while preserving its size. Claim 16 ensures that we preserve the $(k,h)$-dichotomy property in the new protrusion decomposition of $G^{\prime }$, so we can repeat this process to replace each $P_i$. Application of Lemma 9 takes time linear in the size of the protrusion being replaced, so the total running time is linear.

We now justify the final inequality for lifting solutions. Recall that when $S$ is a feasible $ℱ$-deletion set in $G$ then ${\text{val}}_{(G,k)}^{ℱ\text{-Del}}(S)=\min \{|S|,k+1\}$ and ${\mathrm{𝗈𝗉𝗍}}_{ℱ\text{-Del}}((G,k))$ is the minimum over ${\text{val}}_{(G,k)}^{ℱ\text{-Del}}(S)$. In these terms, we have ${\mathrm{𝗈𝗉𝗍}}_{ℱ\text{-Del}}((G,k))={\mathrm{𝗈𝗉𝗍}}_{ℱ\text{-Del}}((G^{\prime },k))$. Suppose first that $|S^{\prime }|>k$ so ${\text{val}}_{(G^{\prime },k)}^{ℱ\text{-Del}}(S^{\prime })=k+1$. Then we simply return $S=V(G)$ for which ${\text{val}}_{(G,k)}^{ℱ\text{-Del}}(S)=k+1$ and the inequality holds. Otherwise, $|S^{\prime }|\le k$. We use the lifting algorithm described in Claim 17 to compute a solution $S$ in $G$ so that $|S|\le |S^{\prime }|$ and we have $\frac{|S|}{{\mathrm{𝗈𝗉𝗍}}_{ℱ\text{-Del}}((G,k))}\le \frac{|S^{\prime }|}{{\mathrm{𝗈𝗉𝗍}}_{ℱ\text{-Del}}((G^{\prime },k))}$. $◀$