Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion

We define a graph modification problem, called $ℒ$-Replacement to $\mathscr{H}$ ($ℒ$-R-$\mathscr{H}$ for short), which, depending on the choice of the function $ℒ$, called a replacement action, can simulate vertex deletion, edge deletion, edge completion, edge edition, edge contraction, vertex identification, independent set deletion, matching deletion, matching contraction, star deletion, and subgraph complementation, to name a few (see section 3 for an exposition of some problems encompassed by our result). When $\mathscr{H}$ is minor-closed, we solve $ℒ$-R-$\mathscr{H}$ in time $2^{\mathrm{𝗉𝗈𝗅𝗒}(k)}\cdot n^2$ (Theorem 2), where the degree of the polynomial $\mathrm{𝗉𝗈𝗅𝗒}$ depends on the maximum size $s_{\mathscr{H}}$ of the minor-obstructions of $\mathscr{H}$. This is the same running time as the one achieved by the currently best algorithm for vertex deletion [38] (the degree of $k$ in poly is the same as in [38] up to an extra additive constant of one that is absolutely negligible compared to the total degree that depends (wildly) on $s_{\mathscr{H}}$). For the other graph modification problems encompassed within $ℒ$-R-$\mathscr{H}$, to the authors’ knowledge, the only minor-closed classes for which a good parametric dependence was previously known, if any, were the class of forests and the class of union of paths [9, 48, 22, 39, 33].

As it is usually the case concerning meta-theorems, the degree $d$ of the polynomial $\mathrm{𝗉𝗈𝗅𝗒}$ in Theorem 2 is unfortunately huge. While we did not compute its exact value, we know that $d\ge 2^{2^{s_{\mathscr{H}}^{24}}}$. Nevertheless, $d$ can improved for some specific target classes $\mathscr{H}$. The Euler genus of a surface $\mathrm{\Sigma }$ that is obtained from the sphere by adding $h$ handles and $c$ crosscaps is defined to be $c+2h$. In particular, when $\mathscr{H}$ is the class of graphs embeddable in a surface of Euler genus at most $g$, we provide another algorithm solving $ℒ$-R-$\mathscr{H}$ in time $2^{𝒪(k^9)}\cdot n^2$ (Theorem 3), where the $𝒪(\cdot )$ notation depends on $g$. Note that, as opposed to Theorem 2, in Theorem 3 the contribution of the genus (that is, of the target graph class $\mathscr{H}$) does not affect the degree of the parameter $k$ in the exponent.

In section 2 we give basic definitions and conventions, and we formally define the problem and state our results. In section 3 we provide a non-exhaustive list of problems generated by different instantiations of the replacement action $ℒ$, and hence encompassed by our results. In section 4 we present an overview of our techniques. Due to space limitations, all proofs have been deferred to the full version of this article. In section 5 we present some directions for further research.

A graph class $\mathscr{H}$ is minor-closed if, for each graph $G$ and each minor $H$ of $G$, the fact that $G\in \mathscr{H}$ implies that $H\in \mathscr{H}$. Given a collection of graphs $ℱ$, we denote by $\mathrm{𝖾𝗑𝖼}(ℱ)$ the class of graphs that do not contain a graph in $ℱ$ as a minor. Obviously, $\mathrm{𝖾𝗑𝖼}(ℱ)$ is minor-closed. A (minor-)obstruction of a graph class $\mathscr{H}$ is a graph $F$ that is not in $\mathscr{H}$, but whose minors are all in $\mathscr{H}$. The set of all the obstructions of $\mathscr{H}$ is denoted by $\mathrm{𝗈𝖻𝗌}(\mathscr{H})$. By the seminal work of Robertson and Seymour [43], if $\mathscr{H}$ is a minor-closed graph class, then $\mathrm{𝗈𝖻𝗌}(\mathscr{H})$ is finite. Note that, if $ℱ=\mathrm{𝗈𝖻𝗌}(\mathscr{H})$, then $\mathrm{𝖾𝗑𝖼}(ℱ)=\mathscr{H}$. The detail of a graph $G$ is $\max \{|V(G)|,|E(G)|\}$.

For the definitions of the next two paragraphs to be correct, we actually need to consider ordered graphs instead of graphs (see the “Graph modifications” paragraph). An ordered graph is a graph $G$ equipped with a strict total order on $V(G)$, denoted by . In other words, there exists an indexation $v_1,\mathrm{\dots },v_n$ of the vertices of $V(G)$ such that . A subgraph $H$ of an ordered graph $G$ naturally comes equipped with the strict order such that, for each distinct $u,v\in V(H)$, if and only if .

The any-replacement action is the function $ℳ$ that maps each ordered graph $H_1$ to the collection $ℳ(H_1)$ of all the pairs $(H_2,\varphi )$, where $H_2$ is an ordered graph and $\varphi :V(H_1)\to V(H_2)\cup \{\mathrm{\varnothing }\}$ is a function such that:

• $\mathrm{■}$

  $|V(H_2)|\le |V(H_1)|$,

• $\mathrm{■}$

  for each $v\in V(H_2)$, ${\varphi }^{-1}(v)\ne \mathrm{\varnothing }$, and

• $\mathrm{■}$

  is the strict total order such that, for each distinct $v_1,v_2\in V(H_2)$, we have if and only if where, for $i\in [2]$, $u_i$ is the smallest vertex (according to ) in ${\varphi }^{-1}(v_i)$.

A replacement action (abbreviated as R-action) is any function $ℒ$ that maps an ordered graph (called a pattern) $H_1$ to a non-empty collection $ℒ(H_1)\subseteq ℳ(H_1)$ of its possible pattern transformations. See Figure 1 for an illustration. The vertices of $H_1$ mapped by $\varphi$ to the empty set are said to be deleted, and two vertices of $H_1$ mapped by $\varphi$ to the same vertex of $H_2$ are said to be identified. Given $S\subseteq V(H_1)$, we set ${\varphi }^{+}(S)=\varphi (S)\setminus \{\mathrm{\varnothing }\}$. Note that, if $\varphi (S)=\{\mathrm{\varnothing }\}$, then ${\varphi }^{+}(S)=\{\mathrm{\varnothing }\}\setminus \{\mathrm{\varnothing }\}=\mathrm{\varnothing }$.

Let $ℒ$ be an R-action, let $G$ be an ordered graph, and $S\subseteq V(G)$. Let $(H_2,\varphi )\in ℒ(G[S])$. We denote by $G_{(H_2,\varphi )}^S$ the graph obtained from the disjoint union of $G-S$ and $H_2$ by adding an edge $u\varphi (v)$ for each $u\in V(G)\setminus S$ and each $v\in {\varphi }^{-1}(V(H_2))$ such that $uv\in E(G)$. We equip $G^{\prime }:=G_{(H_2,\varphi )}^S$ with the strict total order such that if and only if where, for $i\in [2]$, $u_i:=v_i$ if $v_i\in V(G)\setminus S$, and $u_i$ is the smallest vertex in ${\varphi }^{-1}(v_i)$ if $v_i\in V(H_2)$. We also set ${ℒ}_S(G)=\{G_{(H_2,\varphi )}^S\mid (H_2,\varphi )\in ℒ(G[S])\}$. See Figure 1 for an illustration.

Note that we consider ordered graphs merely so that the correspondence between the vertices in $S$ and the vertices in $V(H_2)$ is well-defined. We actually omit the order from the statements, but it will be implicitly assumed that vertices have a label that allows us to keep track of them during the modification procedure.

Let $ℒ$ be an R-action and $\mathscr{H}$ be a graph class. We define the following problem.

Such a set $S$ is called solution of $ℒ$-R-$\mathscr{H}$ for the instance $(G,k)$.

We will use the following observation, which implies that a no-instance for Vertex Deletion to $\mathscr{H}$ is also a no-instance for $ℒ$-R-$\mathscr{H}$.

Indeed, suppose that there is $(H_2,\varphi )\in ℒ(G[S])$ such that $G_{(H_2,\varphi )}^S\in \mathscr{H}$. Then, because $\mathscr{H}$ is hereditary, $G_{(H_2,\varphi )}^S-{\varphi }^{+}(S)=G-S\in \mathscr{H}$. $◀$

An R-action is said to be hereditary if, for each ordered graph $H_1$, for each non-empty $X\subseteq V(H_1)$, and for each $(H_2,\varphi )\in ℒ(H_1)$, we have $(H_2[{\varphi }^{+}(X)],{\varphi |}_X)\in ℒ(H_1[X])$. We say that $(H_2[{\varphi }^{+}(X)],{\varphi |}_X)$ is the restriction of $(H_2,\varphi )$ to $X$. See Figure 2 for an illustration. Informally, an R-action is hereditary if, when a modification is allowed, then modifying “less” is allowed as well. For instance, if $ℒ$ allows us to delete exactly $k$ vertices, then $ℒ$ also allows us to delete at most $k$ vertices.

By convention, when there is no confusion, we set $n:=|V(G)|$ and $m:=|E(G)|$. In the rest of the paper, instead of considering a minor-closed graph class $\mathscr{H}$, we consider its obstruction set $ℱ$, and thus the minor-closed graph class $\mathrm{𝖾𝗑𝖼}(ℱ)$. We define three constants depending on $ℱ$ that will be used throughout the paper whenever we consider such a collection $ℱ$. We define $a_{ℱ}$ as the minimum apex number of a graph in $ℱ$, we set $s_{ℱ}:=\max \{|V(F)|\mid F\in ℱ\}$, and we define ${\mathrm{\ell }}_{ℱ}$ to be the maximum detail of a graph in $ℱ$. Given a tuple $𝐭=(x_1,\mathrm{\dots },x_{\mathrm{\ell }})\in {\mathbb{N}}^{\mathrm{\ell }}$ and two functions $\chi ,\psi :\mathbb{N}\to \mathbb{N}$, we write $\chi (n)={𝒪}_{𝐭}(\psi (n))$ in order to denote that there exists a computable function $\varphi :{\mathbb{N}}^{\mathrm{\ell }}\to \mathbb{N}$ such that $\chi (n)=𝒪(\varphi (𝐭)\cdot \psi (n))$. Notice that $s_{ℱ}\le {\mathrm{\ell }}_{ℱ}\le s_{ℱ}(s_{ℱ}-1)/2$, and thus ${𝒪}_{{\mathrm{\ell }}_{ℱ}}(\cdot )={𝒪}_{s_{ℱ}}(\cdot )$.

Our main result is the following.

As mentioned in the introduction, the main result in [47] already implies that $ℒ$-R-$\mathscr{H}$ is solvable in time $f(k)\cdot n^2$ when $\mathscr{H}$ is minor-closed for some huge function $f$ that is not even estimated. Our main contribution is an explicit and single-exponential dependence on $k$.

The degree of ${\mathrm{𝗉𝗈𝗅𝗒}}_{ℱ}(k)$ is quite big, but we can reduce it in some specific cases.

More generally, we study the annotated version of $ℒ$-R-$\mathscr{H}$. Let $ℒ$ be a hereditary R-action and $\mathscr{H}$ be a graph class. We define the following problem.

Obviously, we must have $S^{\prime }\subseteq S$. Such a triple $(S,H_2,\varphi )$ is called a solution of $ℒ$-AR-$\mathscr{H}$ for the instance $(G,S^{\prime },H_2^{\prime },{\varphi }^{\prime },k)$. An instance of $ℒ$-AR-$\mathscr{H}$ where $S^{\prime }=\mathrm{\varnothing }$ is an instance of $ℒ$-R-$\mathscr{H}$, so $ℒ$-AR-$\mathscr{H}$ generalizes $ℒ$-R-$\mathscr{H}$. Two instances ${ℐ}_1$ and ${ℐ}_2$ are equivalent instances of $ℒ$-AR-$\mathscr{H}$ if ${ℐ}_1$ is a yes-instance of $ℒ$-AR-$\mathscr{H}$ if and only if ${ℐ}_2$ is a yes-instance of $ℒ$-AR-$\mathscr{H}$.

In fact, we prove stronger statements of Theorem 2 and Theorem 3 that apply to their respective annotated versions.

The techniques that we employ for our first algorithm (that is, when $\mathscr{H}$ is any minor-closed graph class) are strongly inspired by those used by Morelle, Sau, Stamoulis, Thilikos [38] for the particular case of vertex deletion (see also [44]), namely Vertex Deletion to $\mathscr{H}$, achieving the same running time. Nevertheless, in order to deal with our “meta-modification” operations, we need several new technical insights compared to the approach of [44], which we proceed to sketch. In a nutshell, the algorithm of [38] employs a win/win strategy that proceeds as follows:

• $\mathrm{■}$

  If the treewidth of the input graph is small (as a function of the parameter $k$), then solve the problem via a dynamic programming approach.

• $\mathrm{■}$

  If the treewidth of the input graph is big, then either

  • –

    (irrelevant vertex) find a vertex $v$ such that $(G,k)$ and $(G-v,k)$ are equivalent instances, or

  • –

    (branching case) find a set $A\subseteq V(G)$ of small size such that there exists $v\in A$ such that $(G,k)$ and $(G-v,k-1)$ are equivalent instances,

  and recurse.

Hence, we require three ingredients: one to solve the problem parameterized by treewidth, one to find an irrelevant vertex, and one to find an “obligatory set” $A$, all with a “reasonable” parametric dependence on $k$. Then, we need to construct an algorithm so that one of these three cases always applies and such that the overall running time is still within the desired bound, which is one of the most convoluted parts of the proof. In what follows we provide further insights about these steps, by first saying a few words about flat walls.

Let $S^{\prime }$ be the set of vertices recursively guessed to be modified in the branching step. An advantage when the modification consists in vertex deletion is that we can simply recurse on $(G-S^{\prime },k-|S^{\prime }|)$. For the more general case of $ℒ$-R-$\mathscr{H}$, we cannot simply delete $S^{\prime }$, as the considered modification may be different from vertex deletion. We need 1) to guess how $G[S^{\prime }]$ is modified, that is, to guess $(H_2^{\prime },{\varphi }^{\prime })\in ℒ(G[S^{\prime }])$ and 2) to remember $S^{\prime }$ and $(H_2^{\prime },{\varphi }^{\prime })$ in order to check that we eventually find a set $S\supseteq S^{\prime }$ and an allowed modification $(H_2,\varphi )\in ℒ(G[S])$ whose restriction to $S^{\prime }$ is $(H_2^{\prime },{\varphi }^{\prime })$ such that the modified graph is in $\mathscr{H}$. This is why we need to solve the annotated version of the problem, denoted by $ℒ$-AR-$\mathscr{H}$, where we add to the input a subset $S^{\prime }$ of vertices of $G$ that are required to be part of $H_1$, as well as the modification $(H_2^{\prime },{\varphi }^{\prime })$ made on $S^{\prime }$.

Note that we cannot just use Courcelle’s theorem [8], since we require a nice parametric dependence on $k$. Hence, we need to design our own dynamic programming algorithm to solve $ℒ$-AR-$\mathscr{H}$ parameterized by the treewidth and $k$. Essentially, the idea is to guess, in each bag $\beta (t)$ of the decomposition, the set $S_t$ of vertices that are modified as well as how they are modified, and to reduce the size of the graph $G_t$ induced by the bag $t$ and its children using the representative-based technique of [5]. This technique is essentially based on the property that, given a graph $G$ in a minor-closed graph class $\mathscr{H}$ with a boundary $B$, there is a graph $R$ of bounded size with same boundary $B$, called the representative of $G$, such that, for any graph $H$ glued on $B$ to get $G\oplus H$ and $R\oplus H$, $G\oplus H\in \mathscr{H}$ if and only if $R\oplus H\in \mathscr{H}$. $G_t$ does not belong to $\mathscr{H}$, so we cannot find a representative of $G_t$, but we find instead a representative of the graph $G_t^{\prime }\in \mathscr{H}$ modified from $G_t$ according to the guessed modification on $S_t$ and the previously guessed modification on the children of $t$. Given that we may need to identify together vertices that are far apart in the tree decomposition, we need to remember throughout the algorithm the vertices that are guessed to be part of the solution. The fact that we keep information about these at most $k$ vertices explains the dependence on $k$ of the dynamic programming algorithm. More precisely, we prove the following result.

The above result parameterized by treewidth and $k$ may be of independent interest, given that it implies an algorithm with a good parametric dependence on the treewidth and $k$ for a number of graph modification problems. Note that the question of whether $ℒ$-R-$\mathscr{H}$ is FPT parameterized by only treewidth is open. Even Courcelle’s theorem only implies a running time of $f(\mathrm{𝗍𝗐},k)\cdot n$, given that the size of the CMSO formula expressing yes-instances of $ℒ$-R-$\mathscr{H}$ depends on $k$. Note that, in [38], the bounded treewidth part consists just in a black-box application of the algorithm of Baste, Sau, and Thilikos [5].

An essential tool of our approach is the notion of flat wall, originating in the work of Robertson and Seymour [42]. Informally speaking, a flat wall is a structure made up of (non-necessarily planar) pieces, called flaps, that are glued together in a bidimensional grid-like way defining the so-called bricks of the wall. While such a structure may not be planar, it enjoys topological properties similar to those of planar graphs, in the sense that two paths that are not routed entirely inside a flap cannot “cross”, except at a constant-sized vertex set $A$ whose vertices are called apices. Hence, flat walls are only “locally non-planar”, and after removing apices we can apply useful locality arguments, in the sense that two vertices that are in “distant” flaps should also be “distant” in the whole graph without the apices. In this article we apply some variants of one of the most celebrated results in the theory of Graph Minors by Robertson and Seymour [42, 43], known as the Flat Wall theorem (see also [27, 46] for recently proved variants), which informally states that graphs of large treewidth contain either a large clique minor or a large flat wall.

In order for our formal statements to be mathematically correct, we would need to introduce a number of notions originating in [46]. Unfortunately, in the attached full version several pages are required to provide all these technical notions. Due to space limitations, in this extended abstract we only provide intuitive descriptions of the main notions required to read the statement of the results, but we skip a number of technical terms (such as renditions, tilts, influence, regular flatness pairs, etc.) that are not the main focus of this sketch. All details can be found in the attached full version, and we refer the reader to [46] for a more detailed exposition of these definitions and the reasons for which they were introduced.

An $r$-wall is any graph $W$ obtained from a so-called elementary $r$-wall $\overline{W}$ after subdividing edges: see Figure 3 for self-explanatory illustration of a $5$-wall.

A flat wall is illustrated in Figure 4, where the flaps mentioned above correspond to the orange cells. The perimeter of a flat wall in a graph $G$ separates $V(G)$ into two sets $X$ and $Y$ with $Y$ containing the wall. The compass of a flat wall is $G[Y]$. For example, in Figure 4, $X$ is the set of vertices in the green part, and $Y$ the set of vertices in the orange part.

In order to find an irrelevant vertex, we need to deal with homogeneous flat walls. Intuitively, homogeneous flat walls are flat walls that allow the routing of the same set of (topological) minors in the augmented flaps (i.e., the flaps together with the apex set) “cropped” by each one of their bricks. Such a homogeneous wall can be detected in a big enough flat wall and this “homogeneity” property implies that some central part of a big enough homogeneous wall can be declared irrelevant.

Another very useful notion is that of a canonical partition of a graph $G$ with respect to some wall $W$ of $G$. Informally, this refers to a partition of the vertex set of $G$ into bags that follow the grid-like structure of $W$; see Figure 5. Essentially, the goal is to be able to contract each of these bags to obtain a grid that is a minor of $W$, and thus of $G$. In particular, we prove (see Lemma 5 below) that if $G$ contains as a minor a grid $\mathrm{\Gamma }$ along with a set $A$ whose vertices have sufficiently many neighbors in the grid, then some vertex in $A$ is obligatory. We use canonical partitions here to easily find such a structure given a wall of $G$.

The branching case is not much different from what is done in [38] (originally from [45]): essentially, if there is a big enough wall $W$ (cf. Figure 3) and a set $A$ of vertices having many disjoint paths to $W$ (cf. Figure 6), then some modification $(H_A,{\varphi }_A)$ must happen in $A$ and we can branch. Here, we however need to additionally prove that we must have . We stress that it is important here to guess some modification in $A$ that strictly decreases the size of $A$, so that, after applying this partial modification to $G$ at the next step in the recursion, we will not find the exact same obligatory set $A$. Hence, in the algorithm with input $(G,S^{\prime },H_2^{\prime },{\varphi }^{\prime },k)$, at each step, either we find an irrelevant vertex and strictly decrease the size of $G$, or we branch and strictly increase the size of $S^{\prime }$.

More precisely, the next result is the main technical ingredient in this part of the proof, essentially stating that a part of the solution $S$ can be found in a set $A$ of size $a_{ℱ}$ in which every vertex is adjacent to many vertices of a big enough wall. This is our “obligatory vertex” method. See Figure 6 for an illustration and Section 6 of the full version for the details.

As expected, we use the irrelevant vertex technique of Robertson and Seymour [42]. More specifically, we generalize the irrelevant vertex technique used in [38] (actually proved in [45]). This technique is based on the (intuitive but surprisingly hard to prove) fact that the central vertex of a homogeneous flat wall is always irrelevant. While our irrelevant vertex technique for $ℒ$-AR-$\mathscr{H}$ takes inspiration from [45], it is far more involved due to the annotation and the fact that we allow a wide variety of modifications. In particular, we need to redefine what it means to be homogeneous for a flat wall, to adapt it to our new setting. The previous definition was made to handle the case when we had to remove a small vertex set, called apex set, to find a flat wall, and more specifically to handle the fact that some vertices are possibly deleted from the apex set. Now, we also need to handle any other way the apex set may be modified, hence the new definition. The fact that we ask the replacement action $ℒ$ to be hereditary comes from the irrelevant vertex technique. Indeed, in order to prove that the central vertex $v$ of a homogeneous flat wall $W$ is irrelevant, we essentially prove that, for any solution $(S,H_2,\varphi )$, we can delete a small part $X$ of $W$ containing $v$, and that the restriction of $(S,H_2,\varphi )$ to $G-X$ is still a solution.

The following is the main technical result that we prove in this part, stating that an irrelevant vertex can be found in a big enough flat wall whose compass has bounded treewidth.

We also prove the following result for the bounded genus case with a better dependence on $k$ and a better running time. In this case, we do not ask for our flat wall to have bounded treewidth, but to have a planar embedding instead. Note that here, instead of a single vertex $v$, we might sometimes find an entire planar block of vertices $V$ that is irrelevant.

Finally, we combine the three ingredients discussed above to find an algorithm for $ℒ$-AR-$\mathscr{H}$. We essentially proceed as follows. Let $(G,S^{\prime },H_2^{\prime },{\varphi }^{\prime },k)$ be the instance we want to solve, and $G^{\prime }$ be obtained by doing the modification $(H_2^{\prime },{\varphi }^{\prime })$ of $S^{\prime }$. In the first steps, we either find that $G$ has small treewidth, where we can use our dynamic programming algorithm to conclude, or that $G^{\prime }$ contains a wall $W$. Given $W$, we first try to find a flat wall $W^{\prime }$ inside, with all the necessary conditions to find an irrelevant vertex. If we manage to do so, we remove the irrelevant vertex and recurse. Otherwise, through a greedy procedure, we try to find an obligatory vertex set $A$ with many disjoint paths to $W$ in $G^{\prime }$. If we find such a set, we branch and recurse. If not, we manage to argue that we must have a no-instance, and conclude.

Our second algorithm (Theorem 3), when $\mathscr{H}$ is a class of graphs embeddable in a surface of bounded Euler genus, uses two additional ideas to get an improved running time. The first one is that here, the obligatory set $A$ is a singleton. Indeed, the size of $A$ is the size of the minimum number of vertices one can remove from an obstruction of $\mathscr{H}$ to make it planar. It is well known that, when $\mathscr{H}$ is such a class, there is some integer $t$ depending on the Euler genus such that $K_{3,t}\notin \mathscr{H}$, and thus, $|A|=1$. In particular, this implies that we do not need to branch on $A$, but that we instead immediately find an obligatory vertex. The second idea is about homogeneous flat walls. In the running time $2^{\mathrm{𝗉𝗈𝗅𝗒}(k)}\cdot n^2$ of the first algorithm, the degree of poly essentially corresponds to the size of the required flat wall to find a big enough homogeneous flat wall, and hence an irrelevant vertex, inside of it. In the case where $\mathscr{H}$ is the class of graphs embeddable in a surface of Euler genus at most $g$, we prove that we can find a homogeneous flat wall inside a flat wall of smaller size, hence the improved running time. To do so, we prove that, after some preliminary processing, a flat wall that is furthermore embeddable in a disk with the perimeter on its boundary is already homogeneous. Hence, our second algorithm proceeds similarly to the first one, but if we find a flat wall $W^{\prime }$ in $G^{\prime }$, we divide $W^{\prime }$ into $k+1$ disjoint smaller flat walls and check whether they belong to $\mathscr{H}$. By the pigeonhole principle, one of them, $W_i$, does not contain a modified vertex and must thus be in $\mathscr{H}$, otherwise we return a no-instance. Then, we argue, using a result from [11] to guarantee additional properties of the planar embedding that are needed for technical reasons, that we can find a smaller flat wall $W_i^{\prime }$ in $W_i$ with a planar embedding (even if the genus of the target graph class is strictly positive). Hence, we find an irrelevant vertex in $W_i^{\prime }$ and conclude.