Enumeration Kernels for Vertex Cover and Feedback Vertex Set

Our first result is a PDE kernel for Enum Vertex Cover with $2k$ vertices, and directly improves upon the $𝒪\left(k^2\right)$ kernel of Creignou et al. [17]; the problem is formally defined as follows.

Enum Vertex Cover
Instance: A graph $G$ and an integer $k$. Enumerate: All vertex covers of $G$ of size at most $k$.

Our proof is a direct generalization of the kernel with $2k$ vertices for Vertex Cover; this, in turn, is based on the celebrated crown decomposition technique. Specifically, we obtain the following theorem.

Intuitively, our kernel works by applying the classic crown reduction that deletes the head $H$ and crown $C$ of the decomposition, reduces $k$ by $|H|$, and returns only the body $B$. The $2k$ bound is consequence of the Nemhauser-Trotter decomposition theorem [38] and the fact that it either yields a crown decomposition or gives a bound on the size of the input graph. The complicated part is showing how to design a lifting algorithm; we do so by proving that Enum Vertex Cover restricted to crowned graphs, i.e., graphs that can be partitioned into $H\cup C$ where $C$ is an independent set and there is an $H$-saturating matching between $H$ and $C$, admits a polynomial-delay algorithm. Given a solution $S$ of the reduced instance, our lifting algorithm has three phases: (i) brute force how the slack $k-(|S|+|N(B\setminus S)\cap H|)$ is distributed in $C$, (ii) compute sets of vertices forced to be added to and forbidden in the solution given the output of (i), and (iii) solve the instance $(G^{\prime },|V(G^{\prime })|/2)$ induced by the remaining vertices. The key observations are that: (a) every configuration tested in (i) leads to a solution of the input, and (b) $G^{\prime }$ is a crowned graph with a perfect matching.

We then proceed to show a cubic PDE kernel for the Enum Feedback Vertex Set problem, formally defined as below.

Enum Feedback Vertex Set
Instance: A multigraph $G$ and an integer $k$. Enumerate: Every feedback vertex set of $G$ of size at most $k$.

We follow a similar direction to Thomassé’s quadratic kernel [39]: we first design reduction rules to lower bound the minimum degree of the instance; then, we show that upper bounding the maximum degree is enough to lead to a kernel; and finally, we present reduction rules that yield said upper bound. The core ingredient of Thomassé’s proof – the computation of a $2$-expansion in an auxiliary graph – seems to fail in the enumeration setting, and we are unable to generalize it. Nevertheless, we obtain Theorem 2. Our set of reduction rules is mostly different, which leads to a quadratic instead of a linear bound on the maximum degree. As our lower bound on the minimum degree is also different, we must prove a slight generalization on the bound used in Thomassé’s proof.

In Section 2 we present some basic preliminaries about graphs, parameterized complexity, and enumeration problems. In Section 3, we present our linear PDE kernel for Enum Vertex Cover. In Section 4, we present our cubic PDE kernel for Enum Feedback Vertex Set and discuss some challenges in using rules based on $q$-expansions. We present concluding remarks and possible research directions in Section 5. Due to space limitations, the proofs of the statements marked with “$(\star )$” have been omitted and can be found in the full version available online (https://arxiv.org/abs/2509.08475).

Let $G^{\prime }=G\setminus \{v\}$. The forward direction is immediate; $S\in \mathrm{𝖲𝗈𝗅}(G,k)$ if and only if $S\setminus \{v\}\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k)$. For the converse direction, it is also immediate that $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k)$ if and only if $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G,k)$; however, observe that $(S^{\prime }\cup \{v\})\in \mathrm{𝖲𝗈𝗅}(G,k)$ if and only if as $v$ is isolated, and we must also output $(S^{\prime }\cup \{v\})$ if possible. $◀$

As pointed out by Chlebík and Chlebíkova [15], the Nemhauser-Trotter [38] decomposition based on the half-integral relaxation of Vertex Cover is a crown decomposition.

Let us show how to construct the lifting algorithm ${ℛ}_b$ using $𝒜$. Given a solution $S^{\prime }$ of the reduced instance $(G^{\prime },k^{\prime })$, let $x=k^{\prime }-|S^{\prime }|$ (where $x\ge 0$) be the slack of the solution $S^{\prime }$, and $F=N(B\setminus S^{\prime })\cap H$ be the set of forced vertices in $H$, i.e. vertices that are adjacent to some vertex of $B$ not picked in $S^{\prime }$. Let $H^{\prime }=H\setminus F$. For any $\mathrm{\ell }\in [0,\min (|C|,x)]$, define $x_{\mathrm{\ell }}=|H^{\prime }|+\mathrm{\ell }$, and observe that $(G[H^{\prime }\cup C],x_{\mathrm{\ell }})$ is a valid instance of Enum Crown as $x_{\mathrm{\ell }}\le |C|$. For any $\mathrm{\ell }\in [0,\min (|C|,x)]$, ${ℛ}_b$ outputs all solutions of the form $S^{\prime }\cup F\cup S_{\mathrm{\ell }}$, where $S_{\mathrm{\ell }}\in \mathrm{𝖲𝗈𝗅}(G[H^{\prime }\cup C],x_{\mathrm{\ell }})$ are enumerated by $𝒜$. This completes the description of ${ℛ}_b$, so let us now prove that it adheres to the requirements of Definition 4. The first item is satisfied as it is well known that the crown reduction is safe for the decision version of the problem, in the sense that $(G,k)$ is a $\mathrm{𝗒𝖾𝗌}$-instance if and only if $(G^{\prime },k^{\prime })$ is. Let us now check the second item, more precisely:

• $\mathrm{■}$

  For every $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k^{\prime })$, the set ${ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })$ is non-empty, and can be enumerated with polynomial-delay; and

• $\mathrm{■}$

  $\{{ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })\mid S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k^{\prime })\}$ is a partition of $\mathrm{𝖲𝗈𝗅}(G,k)$.

Let us start with the first property. Notice that there exists at least one $\mathrm{\ell }\in [0,\min (|C|,x)]$, and as for any such $\mathrm{\ell }$, tuple $((H^{\prime },C),x_{\mathrm{\ell }})$ is an instance of Enum Crown (which always has a solution by Remark 6), we get that ${ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })\ne \mathrm{\varnothing }$. Moreover, ${ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })$ runs with polynomial-delay, as for each $\mathrm{\ell }$, $𝒜$ enumerates $\mathrm{𝖲𝗈𝗅}(G[H^{\prime }\cup C],x_{\mathrm{\ell }})$ with polynomial-delay, and there is no additional verification required in ${ℛ}_b$ to avoid duplicate solutions of the form $S^{\prime }\cup F\cup S_{\mathrm{\ell }}$ generated by different values of $\mathrm{\ell }$, as for any $\mathrm{\ell }$ these solutions have size exactly $|S^{\prime }|+|F|+x_{\mathrm{\ell }}$.

Let us now consider the second property. Observe first that for any $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k^{\prime })$, any $S\in {ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })$ is indeed a solution of $(G,k)$ as $V(G)$ can be partitioned into $V_1=V(G^{\prime })\cup F$ and $V_2=H^{\prime }\cup C$, and $S=S^{\prime }\cup F\cup S_{\mathrm{\ell }}$ where $S^{\prime }\cup F$ is a vertex cover of $G[V_1]$, $S_{\mathrm{\ell }}$ is a vertex cover of $G[V_2]$, and there is no edge between $V_1\setminus S$ and $V_2$. Let us now prove that $\mathrm{𝖲𝗈𝗅}(G,k)\subseteq {\bigcup }_{S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k^{\prime })}{ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })$. Let $S\in \mathrm{𝖲𝗈𝗅}(G,k)$ and $S^{\prime }=S\setminus (H\cup C)$. As there is a matching of size $|H|$ between the head and the crown, $|S\cap (H\cup C)|\ge |H|$ and thus $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime },k^{\prime })$. Now, let us prove that $S\in {ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })$. Observe first that as $S$ necessarily contains $F$, $S$ is partitioned into $S=S^{\prime }\cup F\cup (S\cap (H^{\prime }\cup C))$, where $S\cap (H^{\prime }\cup C)$ is a vertex cover of $G[H^{\prime }\cup C]$. Let ${\mathrm{\ell }}_0$ be such that $|S\cap (H^{\prime }\cup C)|=|H^{\prime }|+{\mathrm{\ell }}_0$. It remains to prove that ${\mathrm{\ell }}_0\in [0,\min (|C|,x)]$, as this implies that $(S\cap (H^{\prime }\cup C))\in \mathrm{𝖲𝗈𝗅}(G[H^{\prime }\cup C],x_{{\mathrm{\ell }}_0})$, and thus that $S\in {ℛ}_b(G,G^{\prime },k,k^{\prime },S^{\prime })$. First, we have ${\mathrm{\ell }}_0\ge 0$ as $(C,H^{\prime },\mathrm{\varnothing })$ remains a crown decomposition, and thus there is a matching saturating $H^{\prime }$ in $G[H^{\prime }\cup C]$. Let $x=k^{\prime }-|S^{\prime }|$ where $x\ge 0$. Moreover, $|S|=|S^{\prime }|+|F|+|(S\cap (H^{\prime }\cup C))|=k^{\prime }-x+|F|+|H^{\prime }|+{\mathrm{\ell }}_0=k-x+{\mathrm{\ell }}_0\le k$, implying that ${\mathrm{\ell }}_0\le x$. As ${\mathrm{\ell }}_0\le |C|$ by definition, we get the claimed inequality. Finally, observe that $S\cap V(G^{\prime })=S^{\prime }$, so it follows that ${ℛ}_b$ is an extension-only lifting algorithm, which implies that, for any two different solutions $S_1^{\prime },S_2^{\prime }$ of $\mathrm{𝖲𝗈𝗅}(G^{\prime },k^{\prime })$, the sets ${ℛ}_b(G,G^{\prime },k,k^{\prime },S_1^{\prime })$, and ${ℛ}_b(G,G^{\prime },k,k^{\prime },S_2^{\prime })$ are disjoint. $◀$

With this conditional result, we are now able to state a conditional kernelization lemma.

The remainder of this section is dedicated to proving that Enum Crown admits a polynomial-delay enumeration algorithm. In what follows, given a matching $M$, and a subset $T\subseteq V(M)$ such that for any $e\in M$, $|V(e)\cap T|\le 1$, we define $M_V(T)≔\{v^{\prime }\mid v{v}^{\prime }\in M\text{ and }v\in T\}$ and call it the image of $T$ by $M$. We need the following procedure and its associated technical lemma to obtain our lifting algorithm. Intuitively, in a small crowned graph $G$, exactly one endpoint of each edge of an $H$-saturating matching $M$ can be in a vertex cover; ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖽𝗂𝗋}}(G,M,X_0)$ decides which vertices must be included and which must be excluded from a solution if we fix $X_0$ to be part of the it.

Let $\overrightarrow{G}=(A\cup B,\overrightarrow{E})$ be the oriented bipartite graph defined in Definition 10.

Let $S\in \mathrm{𝖲𝗈𝗅}(G)$ such that $X_0\subseteq S$. For any $i\ge 0$, let $D_i$ be the vertices of $(A,B)$ at distance $i$ from $X_0$ in $\overrightarrow{G}$ (e.g. $D_0=X_0$, $D_1=M_V(X_0)$, see Figure 1). Let us show by induction that for any $i$, if $i$ is even, then $D_i\subseteq A\cap S$, and if $i$ is odd then $D_i\subseteq B\setminus S$, and $D_i=M_V(D_{i-1})$. Observe that the statement holds for $i=0$. Let us now assume that it holds for $i-1$ and consider $i$. If $i$ is odd, observe first that $D_i=M_V(D_{i-1})$ by the definition of $\overrightarrow{G}$, and, by Remark 6, for any edge $v,v^{\prime }\in M$ with $v\in D_{i-1}$ and $v^{\prime }\in D_i$, $v^{\prime }\notin S$. If $i$ is even, as $D_{i-1}\cap S=\mathrm{\varnothing }$ and $S$ is a vertex cover of $G$, then $D_i\subseteq S$, and, as $\overrightarrow{G}$ is bipartite, we also get that $D_i\subseteq A$. Now, as $F={\bigcup }_{i\equiv 0mod2}{D}_i$ and $\overline{F}={\bigcup }_{i\equiv 1mod2}{D}_i$, we get $\overline{F}=M_V(F)$, and Item 1 follows.

Observe first that $G^{\prime }$ is indeed a crowned graph as $\overline{F}=M_V(F)$. Now, as $S\in \mathrm{𝖲𝗈𝗅}(G)$ we get $|S|=|H|$; by Remark 6 we get $|S\cap (F\cup \overline{F})|=|F|$, leading to $|S\cap (C^{\prime }\cup H^{\prime })|=|H^{\prime }|$.

Let $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$, and let us consider $S=F\cup S^{\prime }$. Observe that $H\cup C$ is partitioned into $F\cup \overline{F}$ and $H^{\prime }\cup C^{\prime }$, that $F$ is a vertex cover of $G[F\cup \overline{F}]$ (as $\overline{F}=M_V(F)$), and $S^{\prime }$ is a vertex cover of $G[H^{\prime }\cup C^{\prime }]$. By definition of $F$ and $\overline{F}$, there is no edge between $\overline{F}$ and $H^{\prime }\cup C^{\prime }$, implying that $S$ is a vertex cover of $G[H\cup C]$. Since $|S|=|H|$, we get that $S$ is a solution of $G$ (that contains $X_0$ by definition of $F$). $◀$

Let us define a polynomial-delay enumeration algorithm $𝒜$ for Enum Crown. Let $(G,x)$ be an instance of Enum Crown with $V(G)=H\cup C$, and let $M$ be a matching from $H$ to $C$ that saturates $H$. Given $T\subseteq V(G)$, we define $M(T)=\{e\in M\mid V(e)\subseteq T\}$, i.e., the set of edges of $M$ entirely in $T$. For any $S\in \mathrm{𝖲𝗈𝗅}(G,x)$, the signature of $S$ is composed of two sets, $C_1(S)=V(M(S))\cap C$ and $C_2(S)=(C\setminus V(M))\cap S)$. Observe that

• $\mathrm{■}$

  $|C_1(S)|=|M(S)|$, where $|C_1(S)|\le x$ (as $|C_1(S)|+|H|\le |S|=|H|+x$);

• $\mathrm{■}$

  $x-(|C|-|M|)\le |C_1(S)|$ (as if $x-(|C|-|M|)>|C_1(S)|$ then as $C_2(S)\subseteq (C\setminus V(M))$, we would have ), and $|C_2(S)|=x-|C_1(S)|$;

• $\mathrm{■}$

  By defining $\overline{X_1}(S)=(C\setminus V(M))\setminus C_2(S)$, we have $S\cap \overline{X_1}(S)=\mathrm{\varnothing }$.

Our next step is guessing which edges of the $H$-saturating matching $M$ will have both endpoints in the solution $S$; in the next propagation procedure, this is represented by set $C_1$, i.e. which vertices of $C\cap V(M)$ must be accompanied by their image in $S$. We also guess which vertices of $C$ that are not matched to $H$ will be included in a solution; this is represented by $C_2$. Finally, the choice of $C_1$ and $C_2$ implies that the vertices $\overline{X}\subseteq C\setminus (V(M)\cup C_2)$ are incident to yet uncovered edges. Formally, for any $d\in [\max (0,x-(|C|-|V(M))|),x]$, any set $C_1\subseteq V(M)\cap C$ of size $d$, and any set $C_2\subseteq C\setminus V(M)$ of size $x-d$, we define (see Figure 2) ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝗅𝖺𝗋𝗀𝖾}}(C_1,C_2)$ that computes $(F,\overline{F},\overline{X_1})$ where $\overline{X_1}=(C\setminus V(M))\setminus C_2$, and $(F,\overline{F})={\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖽𝗂𝗋}}(\tilde{G},X_0)$ with $X_0=N(\overline{X_1})$, and $\tilde{G}=G[\tilde{H}\cup \tilde{C}]$, where $\tilde{H}=H\setminus M_V(C_1)$, and $\tilde{C}=M_V(\tilde{H})$.

Let $S\in \mathrm{𝖲𝗈𝗅}(G,x)$ have signature $(C_1,C_2)$. By definition of $C_2(S)$, we get that $S\cap \overline{X_1}=\mathrm{\varnothing }$, implying also that $X_0\subseteq S$. Moreover, by definition of $C_1(S)$, no edge $e\in M$ with $V(e)\subseteq \tilde{H}\cup \tilde{C}$ has both its endpoints in $S$. Thus, if we define $\tilde{S}=S\cap (\tilde{H}\cup \tilde{C})$, we get that $\tilde{S}\in \mathrm{𝖲𝗈𝗅}(\tilde{G})$ and that $X_0\subseteq \tilde{S}$. By Lemma 11, we obtain the two claimed properties. $\mathrm{⊲}$

We are now ready to define $𝒜$. To this end, let ${𝒜}_s$ be the polynomial-delay algorithm for Enum Small Crown. For any $d\in [\max (0,x-(|C|-|V(M)|)),x]$, any set $C_1\subseteq V(M)\cap C$ of size $d$, and any set $C_2\subseteq C\setminus V(M)$ of size $x-d$, $𝒜$ runs ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝗅𝖺𝗋𝗀𝖾}}(C_1,C_2)$ that computes $(F,\overline{F},\overline{X_1})$, and defines $G^{\prime }$, $H^{\prime }$, and $C^{\prime }$ as in Item 2 of Claim 13. Note that $G^{\prime }$ may be the empty graph. Then, $𝒜$ outputs all solutions of the form $C_1\cup M(C_1)\cup C_2\cup F\cup S^{\prime }$, where $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$ are enumerated by ${𝒜}_s$. Observe that we can indeed call ${𝒜}_s$ on $G^{\prime }$ as according to Item 2, $G^{\prime }$ is a small crowned graph.

Let us first prove that there is no repetition. Observe that for each $d$, $C_1$, $C_2$ considered by $𝒜$, all enumerated solutions of the form $C_1\cup M(C_1)\cup C_2\cup F\cup S^{\prime }$ (where $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$) have a signature $(C_1,C_2)$. Now, it is sufficient to observe that two solutions of $(G,x)$ with different signatures are necessarily different, which implies that there is no repetition.

Let us now prove that all enumerated elements are in $\mathrm{𝖲𝗈𝗅}(G,x)$. Let $S=C_1\cup M(C_1)\cup C_2\cup F\cup S^{\prime }$, where $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$ exists (as $S^{\prime }=S\cap V(G^{\prime })$ and $G^{\prime }$ is an induced subgraph of $G$) and is enumerated by $𝒜$. By Item 3 of Lemma 11, $(S^{\prime }\cup F)\in \mathrm{𝖲𝗈𝗅}(\tilde{G})$ and contains $X_0$. Now, observe that $H\cup C$ is partitioned into $V_1=C_1\cup M(C_1)\cup C_2\cup \overline{X_1}$, and $V_2=\tilde{H}\cup \tilde{C}$. Notice that $S\cap V_i$ is a vertex cover of $G[V_i]$ for $i\in \{1,2\}$. Moreover, as $V_1\setminus S=\overline{X_1}$, the only edges between $V_1$ and $V_2$ not covered by $S\cap V_1$ are edges between $\overline{X_1}$ and $N(\overline{X_1})=X_0$, but as $S\cap V_2\supseteq X_0$, $S$ is indeed a vertex cover of $G$. Finally, $|S|=2|C_1|+|C_2|+|F|+|H^{\prime }|=2|C_1|+|C_2|+|\tilde{H}|=|H|+|C_1|+|C_2|=|H|+x$, and so we have $S\in \mathrm{𝖲𝗈𝗅}(G,x)$.

Towards proving that all elements of $\mathrm{𝖲𝗈𝗅}(G,x)$ are enumerated, let $S\in \mathrm{𝖲𝗈𝗅}(G,x)$, and $(C_1(S),C_2(S))$ be its signature. By definition of $𝒜$, there exists $C_1$ and $C_2$ considered by $𝒜$ such that $C_i=C_i(S)$ for $i\in \{1,2\}$. Let $(F,\overline{F},\overline{X_1})={\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝗅𝖺𝗋𝗀𝖾}}(C_1,C_2)$. By Item 1, $S\supseteq F$, and $S\cap (\overline{F}\cup \overline{X_1})=\mathrm{\varnothing }$, which implies that $S=C_1\cup M(C_1)\cup C_2\cup F\cup S^{\prime }$. As $S\cap (C^{\prime }\cup H^{\prime })=S^{\prime }$, Item 2 implies that $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$, and so $S^{\prime }$ is enumerated by ${𝒜}_s$.

It remains to prove that there is only polynomial-time between two consecutive outputs of $𝒜$. Notice first that ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝗅𝖺𝗋𝗀𝖾}}$ runs in polynomial time. Then, for each fixed $C_1,C_2$ considered by $𝒜$, as ${𝒜}_s$ runs in polynomial-delay, there is at most polynomial-time between two consecutive solutions having the same signature $(C_1,C_2)$. Moreover, and as for any choice of $C_1,C_2$ considered by $𝒜$, we know that $\mathrm{𝖲𝗈𝗅}(G^{\prime })\ne \mathrm{\varnothing }$ (by Remark 6), there is also a polynomial-delay between two consecutive solutions with different signatures. $◀$

The proof of Lemma 16 requires a more involved variant of the propagation algorithm, where the goal is to avoid a prescribed vertex $v$.

Suppose that there is some $S\in \mathrm{𝖲𝗈𝗅}(G)$ where $v\notin S$. Let us prove by induction that for any $i\ge 1$, if there is a failure when computing $F_i$ or $\overline{F_i}$, then $S$ cannot exist, and otherwise $F_i\subseteq S$ and $S\cap \overline{F_i}=\mathrm{\varnothing }$.

Assume there was no failure, and consider the step where we try to compute $F_i$. By induction, $S\cap {\overline{F}}_{i-1}=\mathrm{\varnothing }$, so we have that $N({\overline{F}}_{i-1})\subseteq S$ and, by construction, $F_i=N({\overline{F}}_{i-1})$. By Remark 6, if there is an edge $e\in M$ where $V(e)\subseteq F_i$, then no such solution exists. Let us now consider the case where we try to compute $\overline{F_i}$. Again by induction, we have $F_{i-1}\subseteq S$, and by Remark 6 we know that no edge of $M$ can have both endpoints in $S$, implying that we must have $S\cap M_V(F_i)=\mathrm{\varnothing }$. Thus, if $G[M_V(F_i)]$ is not an independent set, then no such solution exists.

The correctness of Item 1 now directly follows from the induction. The proof of Item 2 is also immediate: if ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖺𝗅𝗅}}(G,v)$ returns $(F,\overline{F})$, then $\overline{F}=M_V(F)$ follows from the definition, and for $S\in \mathrm{𝖲𝗈𝗅}(G)$ such that $v\notin S$, $F\subseteq S$ and $S\cap \overline{F}=\mathrm{\varnothing }$ follows from the induction, and the fact that $(S\cap (C^{\prime }\cup H^{\prime }))\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$ is true by Remark 6.

To prove Item 3, let $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G^{\prime })$, and let $S=F\cup S^{\prime }$. Notice that $H\cup C$ is partitioned into $F\cup \overline{F}$ and $H^{\prime }\cup C^{\prime }$, that $F$ is a vertex cover of $G[F\cup \overline{F}]$ (as $\overline{F}=M_V(F)$), and that $S^{\prime }$ is a vertex cover of $G[H^{\prime }\cup C^{\prime }]$. Now, let $i_0$ be the index where ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖺𝗅𝗅}}$ stops, meaning that $F_{i_0}=F_{i_0-1}$. This implies that $N({\overline{F}}_{i_0})\subseteq F_{i_0-1}$, and thus that there is no edge between ${\overline{F}}_{i_0}=\overline{F}$ and $H^{\prime }\cup C^{\prime }$, implying that $S$ is a vertex cover of $G[H\cup C]$. As $|S|=|H|$, we get that $S$ is a solution of $G$ that avoids $v$ by definition of $F$. $◀$

With the propagation algorithm in hand, Lemma 16 can be proved by constructing a branching algorithm where we either add a vertex $v$ of $H$ or do not add it to the solution. The key properties we use are that: (i) there is always one solution that uses $v$ (e.g. taking the entirety of $H$), and (ii) we can decide in polynomial time if it is possible to avoid $v$ in a solution. Consequently, we recursively call our branching algorithm only if we know that there is some solution to be found in this branch.

Let $G=(H\cup C,E)$ be a small crowned graph and let us define an algorithm ${𝒜}_s$ that enumerates all vertex covers of $G$ of size $|H|$. If $V(G)=\mathrm{\varnothing }$, then ${𝒜}_s$ returns $\mathrm{\varnothing }$, so now let $v\in H$ be an arbitrary vertex. Let $(F_v,\overline{F_v})={\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖽𝗂𝗋}}(G,\{v\})$, $H_v^{\prime }=H\setminus F_v$, $C_v^{\prime }=C\setminus \overline{F_v}$, and $G_v^{\prime }=G[H_v^{\prime }\cup C_v^{\prime }]$. Algorithm ${𝒜}_s$ outputs first all solutions of the form $F_v\cup S^{\prime }$, where $S^{\prime }$ are enumerated by a recursive call ${𝒜}_s(G_v^{\prime })$. Then, ${𝒜}_s$ calls ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖺𝗅𝗅}}(G,v)$. If it fails then ${𝒜}_s$ stops, otherwise let $(F_{\overline{v}},{\overline{F}}_{\overline{v}})$ be the output of ${\mathrm{𝗉𝗋𝗈𝗉𝖺𝗀𝖺𝗍𝖾}}_{\mathrm{𝖺𝗅𝗅}}(G,\overline{v})$, $H_{\overline{v}}^{\prime }=H\setminus F_{\overline{v}}$, $C_{\overline{v}}^{\prime }=C\setminus {\overline{F}}_{\overline{v}}$, and $G_{\overline{v}}^{\prime }=G[H_{\overline{v}}^{\prime }\cup C_{\overline{v}}^{\prime }]$. Algorithm ${𝒜}_s$ outputs then all solutions of the form $F_{\overline{v}}\cup S^{\prime }$, where $S^{\prime }$ are enumerated by a recursive call ${𝒜}_S(G_{\overline{v}}^{\prime })$. This concludes the definition of ${𝒜}_s$.

First, observe that the recursive calls are made on small crowned graphs, as they were obtained by removing sets $(F,\overline{F})$ from $V(G)$ where $\overline{F}=M_V(F)$. The fact that there is no repetition is immediate by induction, as in particular all solutions of $F_v\cup S^{\prime }$, where $S^{\prime }\in \mathrm{𝖲𝗈𝗅}(G_v^{\prime })$, contain $v$, and all solutions of the form $F_{\overline{v}}\cup S^{\prime \prime }$, where $S^{\prime \prime }\in \mathrm{𝖲𝗈𝗅}(G_{\overline{v}}^{\prime })$, do not contain $v$.