Robust Contraction Decomposition for Minor-Free Graphs and Its Applications

There are many natural problems where a set $Z_i$ cannot be removed even if it is irrelevant to the solution: most notably, problems involving connectivity typically have this property. To handle such problems, Klein [21] introduced a dual version of Baker’s layering technique, which is based on contractions of edges. This (Edge) Contraction Decomposition Theorem was later generalized to $H$-minor free graphs by Demaine, Hajiaghayi, and Kawarabayashi [7].

Contraction decomposition theorems of this form can be used as a building block in designing approximation schemes for, e.g., the Traveling Salesman Problem (TSP) and Subset TSP [4, 7, 8, 20, 21], and parameterized algorithms for Bisection, $k$-Way Cut, Odd Cycle Transversal, Subset Feedback Vertex Set and many other problems [3, 18, 24].

To illustrate this, let us briefly discuss how Theorem 1 can be used to obtain a subexponential-time parameterized algorithm for Edge Multiway Cut in $H$-minor-free graphs. In Edge Multiway Cut, we are given a graph $G$, a set $T\subseteq V(G)$ of terminals, and an integer $k$, and the task is to find a set $S\subseteq E(G)$ of at most $k$ edges such that every component of $G\setminus S$ contains at most one terminal.

1. (1)

   A result of Wahlström [31] gives a randomized quasipolynomial kernel for the problem, which allows us to assume that $|V(G)|=k^{\text{polylog}(k)}$.

2. (2)

   Given the decomposition $Z_1,\mathrm{\dots },Z_p$ of Theorem 1 where $p≔\lceil \sqrt{k}\rceil$, there is an $i\in [p]$ such that $|Z_i\cap S|\le \sqrt{k}$ for the hypothetical solution $S$ of size $k$.

3. (3)

   Guess this $i\in [p]$ (there are $\sqrt{k}$ possibilities) and the set $Z_i\cap S$ (there are ${|V(G)|}^{O(\sqrt{k})}=k^{\sqrt{k}\cdot \text{polylog}(k)}$ possibilities)

4. (4)

   Contracting $Z_i\setminus S$ does not change the problem at hand, since the solution $S$ if not affected.

5. (5)

   Since the graph $G/Z_i$ has treewidth $O(\sqrt{k})$, we get that the graph $G/(Z_i\setminus S)$ has treewidth $O(\sqrt{k}+|Z_i\cap S|)=O(\sqrt{k})$ (contracting an edge can decrease treewidth by at most one). Finally, we solve Edge Multiway Cut on $G/(Z_i\setminus S)$ in time $2^{O(\sqrt{k}\log k)}\cdot {|V(G)|}^{O(1)}$ using standard bounded-treewidth techniques.

Overall, we obtain a $2^{\sqrt{k}\cdot \text{polylog}(k)}\cdot n^{O(1)}$ time randomized algorithm for Edge Multiway Cut. The same approach also works for many other problems [2, 24].

Let us try to apply a similar technique for the problem Vertex Multiway Cut, where instead of deleting a set of edges, we need to delete now a set of vertices. There are two main difficulties if we try to apply Theorem 1. First, it would be convenient to have a partition $Z_1,\mathrm{\dots },Z_p$ of vertices such that for every $i\in [p]$ contracting $Z_i$ leaves a graph of treewidth $O(p)$. Here contracting a vertex set $Z_i$ amounts to contracting all edges that have both endpoints in the set $Z_i$. Second, in Step 5 above, we exploited that the decomposition of Theorem 1 is inherently robust: if $Z_i^{\prime }$ is obtained from $Z_i$ by omitting a set of $s$ edges, then the treewidth of $G/Z_i^{\prime }$ is at most $s$ higher than the treewidth of $G/Z_i$.

The following example shows that an analogous statements for contracting vertex sets is not true. Let $G$ be obtained from a $k\times k$ grid by adding two universal vertices $x$ and $y$. Let $A$ and $B$ be the two bipartition classes of the $k\times k$ grid, and define $Z_1≔A\cup \{x\}$ and $Z_2≔B\cup \{y\}$. Then $G/Z_i$ has treewidth 2 for both $i\in [2]$. On the other hand, $G/(Z_1\setminus \{x\})=G/A=G$ and $G/(Z_2\setminus \{y\})=G/B=G$ which means the jump in treewidth can be unbounded even after omitting just a single vertex. Note that $G$ is $K_7$-minor free, so we cannot hope that a vertex partition version of Theorem 1 is inherently robust even on $H$-minor-free graphs.

The above naturally leads to the question of a robust vertex contraction decomposition theorem, where omitting vertices from some $Z_i$ increases the treewidth only in a bounded way. Such decomposition theorems were recently introduced independently for planar graphs [24] and for bounded-genus graphs (and more generally, almost-embeddable graphs) [2] by subsets of the authors, who used them to obtain the first subexponential-time (parameterized) algorithms for a number of problems, such as Edge Bipartization, Odd Cycle Transversal, Edge/Vertex Multiway Cut, Edge/Vertex Multicut, and Group Feedback Edge/Vertex Set on the above graph classes. More precisely, [2, 24] design parameterized algorithms with running time $f(k)\cdot n^{O(\sqrt{k})}$ or even $2^{\tilde{O}(\sqrt{k})}\cdot n^{O(1)}$, where $k$ is the size of the solution (and $\tilde{O}(\cdot )$ hides $\log k$ factors).

The main result of this paper is a vertex contraction decomposition theorem on $H$-minor-free graphs that is robust in the sense described above.

Theorem 2 generalizes the robust vertex contraction theorem for planar graphs [24] and almost-embeddable graphs [2] to arbitrary $H$-minor-free graphs. It also generalizes the edge contraction decomposition (Theorem  1) for $H$-minor free graphs by Demaine et al. [7].

Combined with the results from [24], Theorem 2 directly yields parameterized algorithms of running time $2^{\tilde{O}(\sqrt{k})}\cdot n^{O(1)}$ or $n^{O(\sqrt{k})}$ for all vertex/edge deletion problems on $H$-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion, two broad classes of problems defined in [24]. Roughly speaking, a permutation CSP instance is a binary CSP instance satisfying certain nice properties, and thus corresponds to a graph in which the vertices are variables and the edges are constraints. The Permutation CSP Edge/Vertex Deletion problem basically asks whether one can delete at most $k$ vertices (resp., edges) from (the graph of) a permutation CSP instance such that every connected component in the resulting graph has a satisfying assignment. The 2-Conn Permutation CSP Edge/Vertex Deletion problem is defined similarly, but we only care about the satisfiability on every 2-connected component (instead of connected component). We refer to Section 3 for the precise definition of these problems. Combining the results from [24] and Theorem 2, we get the following result.

The above theorem directly gives us parameterized algorithms of running time exponential in $O(\sqrt{k})$ for many problems on $H$-minor-free graphs. Specifically, we obtain the first subexponential-time parameterized algorithms for the following fundamental problems on $H$-minor-free graphs.

• $\mathrm{■}$

  $n^{O(\sqrt{k})}$ time algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity, and the edge-deletion version of these problems.

• $\mathrm{■}$

  $2^{\tilde{O}(\sqrt{k})}\cdot n^{O(1)}$ time algorithms for Subset Feedback Vertex Set and Subset Feedback Edge Set.

Additionally, the main algorithmic results from [2] (such as subexponential-time parameterized algorithms for Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), that required a complicated two-layered dynamic programming algorithm over the structural decomposition theorem of Robertson and Seymour [28] for $H$-minor free graphs, now admit much cleaner and more direct algorithms by exploiting Theorem 2 (these problems belong to the Permutation CSP Deletion category in Theorem 3).

The study of subexponential-time parameterized algorithms on planar and $H$-minor free graphs has been one of the most active sub-areas of parameterized algorithms, which led to exciting results and powerful methods. Examples include Bidimensionality [5], applications of Baker’s layering technique [4, 10, 12, 15, 29], bounds on the treewidth of the solution [14, 22, 23, 25], and pattern coverage [15, 26]. The central theme of all these results is that planar graphs exhibit the “ square root phenomenon”: parameterized problems whose fastest parameterized algorithm run in time $f(k)\cdot n^{O(k)}$ or $2^{O(k)}\cdot n^{O(1)}$ on general graphs admit $f(k)\cdot n^{O(\sqrt{k})}$ or even $2^{O(\sqrt{k})}\cdot n^{O(1)}$ time algorithms when input is restricted to planar or $H$-minor free graphs. However, these techniques do not apply for designing subexponential time parameterized algorithms for cut and cycle hitting problems such as Multiway Cut, Multicut, or Odd Cycle Transversal. Robust vertex contraction decomposition theorems, first obtained in [2, 24], provide the necessary tools to design subexponential-time parameterized algorithms for some of the cut and cycle hitting problems on $H$-minor free graphs.

On the decomposition front, apart from edge contraction decomposition theorems, there are several other kind of decomposition theorems that have been used to design polynomial-time approximation schemes (PTASs) and FPT algorithms on planar graphs or more generally on $H$-minor free graphs. Most of these decomposition theorems prove strengthening of the classic Baker’s layering technique [1]. This generally yields, in what is known as (Vertex) Edge Decomposition Theorems [1, 6, 9, 11, 13] (see [27] for a detailed introduction).

Finally, let us also point to some recent developments on the structural theory of $H$-minor-free graphs [17, 30]. Our current proof of Theorem 2 mostly relies on the original Robertson-Seymour decomposition for $H$-minor-free graphs [28], and is independent of [17, 30]. Reformulating some of our arguments in the language of [17, 30] may allow us to obtain a more streamlined proof in the future.

Condition B is not tractable, because it is a global constraint on $Z_1,\mathrm{\dots },Z_p$. So we need to somehow reduce it to a local constraint on the RCD of each torso. Let us fix a node $t\in V(T)$ and an index $i\in [p]$. To have condition B, the first thing we need is that (almost) every edge of $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}]$ has its endpoints in the same connected component of $G[Z_i]$, which is the special case $Z^{\prime }=\mathrm{\varnothing }$. But only having this is not enough. We need in addition that loosing $k$ vertices in $Z_i$ only makes $O(k)$ fake edges become “unsafe”. To achieve this, our main idea is to require the two endpoints of every edge in $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}]$ to be connected in $G[Z_i]$ by only the vertices “strictly below $t$” in the tree decomposition $(T,\beta )$, that is, the vertices that only appear in the bags of descendants of $t$. Formally, for every child $s$ of $t$, denote by $\gamma (s)$ the union of all bags in $T_s$, the subtree of $T$ rooted at $s$. Then our requirement is that for every edge $uv$ of $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}]$, $u$ and $v$ lie in the same connected component of $G[((\gamma (s)\setminus \sigma (s))\cap Z_i)\cup \{u,v\}]$ for every child $s$ of $t$ such that $u,v\in \sigma (s)$. Note that every non-fake edge trivially satisfies the requirement.

We show that this requirement is sufficient to guarantee condition B above for all $Z^{\prime }\subseteq Z_i$. The definition of tree decompositions guarantees that the sets $\gamma (s)\setminus \sigma (s)$ are disjoint for different children $s$ of $t$. We say a child $s$ of $t$ is bad if $Z^{\prime }$ contains at least one vertex in $\gamma (s)\setminus \sigma (s)$. By the disjointness of the sets $\gamma (s)\setminus \sigma (s)$, the number of bad children of $t$ is at most $|Z^{\prime }|$. For convenience, we say a child $s$ of $t$ witnesses an edge $uv$ of $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}]$ if $u,v\in \sigma (s)$. Note that each child $s$ of $t$ can witness at most $O(h^2)$ edges, because $|\sigma (s)|\le h$. Due to our requirement, if an edge $uv$ of $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}\setminus Z^{\prime }]$ violates condition B above, i.e., $u$ and $v$ lie in different connected components of $G[Z_i\setminus Z^{\prime }]$, then $Z^{\prime }$ must contain at least one vertex in $\gamma (s)\setminus \sigma (s)$ for every child $s$ of $t$ satisfying $u,v\in \sigma (s)$, and in particular $(u,v)$ is witnessed by a bad node. Since $t$ has at most $|Z^{\prime }|$ bad children and each of them can witness $O(h^2)$ edges, the total number of edges of $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}\setminus Z^{\prime }]$ violating condition B is bounded by $O(|Z^{\prime }|)$.

Based on the above argument, it now suffices to construct $p$-RCDs for each torso of $(T,\beta )$ such that the partition $Z_1,\mathrm{\dots },Z_p$ obtained by combining these local RCDs satisfies the aforementioned requirement for all $i\in [p]$ and $t\in V(T)$. However, the current form of our requirement is global, because whether it is satisfied at a node $t$ depends on the construction at not only $t$ but also all descendants of $t$ in $T$. So next, let us transform it to a “local” form which can be checked by looking at the construction at each torso independently. We first observe that the following condition implies our previous requirement (which can be shown by a simple induction argument).

• For every edge $uv$ of $\mathrm{𝗍𝗈𝗋}(t)[Z_i^{(t)}]$, the endpoints $u$ and $v$ lie in the same connected component of $\mathrm{𝗍𝗈𝗋}(s)[(Z_i^{(s)}\setminus \sigma (s))\cup \{u,v\}]$ for every child $s$ of $t$ such that $u,v\in \sigma (s)$.

The above is actually equivalent to saying that for every child $s$ of $t$, all $u,v\in \sigma (s)\cap Z_i^{(s)}$ lie in the same connected component of $\mathrm{𝗍𝗈𝗋}(s)[(Z_i^{(s)}\setminus \sigma (s))\cup \{u,v\}]$. Importantly, this condition only depends on the construction of $Z_1^{(s)},\mathrm{\dots },Z_p^{(s)}$, the RCD of $\mathrm{𝗍𝗈𝗋}(s)$. If this condition holds on every node of $T$, then our previous requirement is also satisfied for every node of $T$. Therefore, we have our new goal. For every node $t\in V(T)$, we want the following.

1. (A)

   $Z_1^{(t)},\mathrm{\dots },Z_p^{(t)}$ is an RCD of $\mathrm{𝗍𝗈𝗋}(t)$.

2. (B)

   For all $i\in [p]$, any two vertices $u,v\in \sigma (t)\cap Z_i^{(t)}$ lie in the same connected component of $\mathrm{𝗍𝗈𝗋}(t)[(Z_i^{(t)}\setminus \sigma (t))\cup \{u,v\}]$.

Now the new conditions above are both local, which allows us to consider each torso individually. We shall construct the RCDs of the torsos in a top-down manner from the root of $T$ to the leaves. Suppose we are at the node $t\in V(T)$ and going to construct the RCD $Z_1^{(t)},\mathrm{\dots },Z_p^{(t)}$ of $\mathrm{𝗍𝗈𝗋}(t)$, At this point, the RCD at the parent of $t$ has been constructed, so each vertex in $\sigma (t)$ has already been assigned to one of the $p$ classes $Z_1^{(t)},\mathrm{\dots },Z_p^{(t)}$. We then compute a $p$-RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ with an additional property that the $i$-th class of the RCD “connects” the vertices in $\sigma (t)\cap Z_i^{(t)}$ for all $i\in [p]$. Combining this with the partition of $\sigma (t)$ gives us the desired $Z_1^{(t)},\mathrm{\dots },Z_p^{(t)}$ satisfying the above two conditions. As long as such a single step can be achieved, we can eventually construct $Z_1,\mathrm{\dots },Z_p$. So from now, we can restrict ourselves to one torso.

Before discussing how to construct the desired RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$, we need another twist to simplify the task in hand. We notice that constructing an RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ satisfying the additional connectivity property is actually impossible if we do not add any assumption on how the vertices in $\sigma (t)$ belong to the $p$ classes. To see this, consider the following simple example where $\mathrm{𝗍𝗈𝗋}(t)$ is a star of 5 vertices, one central vertex connecting with 4 other vertices. All vertices are contained in $\sigma (t)$ except the central vertex. In $\sigma (t)$, two vertices belong to the class $Z_1^{(t)}$ and the other two vertices belong to $Z_2^{(t)}$. Now in order to connect the two vertices in $\sigma (t)\cap Z_1^{(t)}$, the RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ must assign the central vertex to $Z_1^{(t)}$. But if this is the case, we fail to connect the two vertices in $\sigma (t)\cap Z_2^{(t)}$. Therefore, in this example, it is impossible to construct the desired RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$. In order to fix this issue, we have to somehow guarantee the “connectivity task” that $\sigma (t)$ leaves to us is not too complicated.

Fortunately, using a stronger version of Robertson-Seymour decomposition, we are able to reach a nice situation where only one class of vertices in $\sigma (t)$ need to be connected by the RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$. This version of Robertson-Seymour decomposition, as stated in [6, 9], guarantees that for every node $t\in V(T)$ and every child $s$ of $t$, the adhesion $\sigma (s)$ contains at most three vertices in the embeddable part of $\mathrm{𝗍𝗈𝗋}(t)$ (recall that $\mathrm{𝗍𝗈𝗋}(t)$ is an $h$-almost-embeddable graph consisting of an embeddable part, vortices, and apices). To see why this result helps us, let us consider an ideal case where every torso in the Robertson-Seymour decomposition has no vortices and apices. In this case, every adhesion $\sigma (t)$ is of size at most three, because all vertices in the torso $\mathrm{𝗍𝗈𝗋}(t^{\prime })$ of the parent $t^{\prime }$ of $t$ are in the embeddable part of $\mathrm{𝗍𝗈𝗋}(t^{\prime })$ and thus $\sigma (t)$ can contain at most three of them. Since $|\sigma (t)|\le 3$, there can be at most one class $Z_i^{(t)}$ that contains at least two vertices in $\sigma (t)$. Therefore, when constructing the RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$, we only need the $i$-th class to connect the vertices in $\sigma (t)\cap Z_i^{(t)}$. In the general case where the torsos have vortices and apices, the situation becomes complicated. But we can still manage to achieve this, which requires us to construct the RCD of each torso more carefully and then use the “three-vertex” property as above.

Now our goal becomes to construct an RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ in which one class is required to connect the corresponding vertices in $\sigma (t)$. Essentially, we achieve this by proving the following.²²2The actual result is more complicated, in which the sets $Z_1,\mathrm{\dots },Z_p$ have some additional properties and also there is an additional assumption on the almost-embeddable graph $G$. As we are not going to cover these technical details in this overview, considering this simplified version should be enough.

To see why the above lemma achieves our goal, note that $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ is $h$-almost-embeddable. Furthermore, by constructing the Robertson-Seymour decomposition $(T,\beta )$ carefully, we can always make $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ connected and make every vertex in $\sigma (t)$ have a neighbor in $\beta (t)\setminus \sigma (t)$ in the torso $\mathrm{𝗍𝗈𝗋}(t)$. Without loss of generality, suppose we want to connect the vertices in $\sigma (t)\cap Z_k^{(t)}$ using the $k$-th class of the RCD of $\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$. For each $v\in \sigma (t)\cap Z_i^{(t)}$, we mark a vertex $v^{\prime }\in \beta (t)\setminus \sigma (t)$ that is neighboring to $v$ in $\mathrm{𝗍𝗈𝗋}(t)$. Let $\mathrm{\Phi }\subseteq \beta (t)\setminus \sigma (t)$ be the set of marked vertices. Now apply Lemma 4 with $G=\mathrm{𝗍𝗈𝗋}(t)-\sigma (t)$ and the set $\mathrm{\Phi }$. We then get the disjoint sets $Z_1,\mathrm{\dots },Z_p\subseteq \beta (t)\setminus \sigma (t)$. The vertices in $Z_i$ are assigned to the class $Z_i^{(t)}$ for all $i\in [p]$. Finally, the vertices in $(\beta (t)\setminus \sigma (t))\setminus ({\bigcup }_{i=1}^p{Z}_i)$ are assigned to the class $Z_k^{(t)}$. Then condition 1 of Lemma 4 implies that $Z_1^{(t)},\mathrm{\dots },Z_p^{(t)}$ is an RCD of $\mathrm{𝗍𝗈𝗋}(t)$ and condition 2 guarantees that all $u,v\in \sigma (t)\cap Z_k^{(t)}$ lie in the same connected component of $\mathrm{𝗍𝗈𝗋}(s)[(Z_k^{(t)}\setminus \sigma (t))\cup \{u,v\}]$. Next, we summarize our ideas for proving Lemma 4.

As mentioned at the beginning, the recent work [2] already gives RCDs for almost-embeddable graphs, that is, it proves the special case of Lemma 4 without the set $\mathrm{\Phi }$ and condition 2. Therefore, it is natural to ask whether one can directly generalize (possibly with slight modifications) the proof in [2] to obtain a proof of Lemma 4. Unfortunately, this is not the case. A close look at the proof in [2] reveals that the construction of $Z_1,\mathrm{\dots },Z_p$ in [2] “inherently” prevents us from having condition 2 of Lemma 4. To see this, we need to briefly review how [2] constructs the sets $Z_1,\mathrm{\dots },Z_p$.

For convenience, we discuss the proof of [2] on a surface-embedded graph instead of an almost-embeddable graph. In fact, the most difficult part of the work [2] also lies in decomposing a surface-embedded graph (specifically, the embeddable part of an almost-embeddable graph), and generalizing to almost-embeddable graphs is somehow easy. In [2], the construction of $Z_1,\mathrm{\dots },Z_p$ itself is simple, while the analysis of the RCD condition is involved. In the first step, it generalizes the outerplanar layering for planar graphs to surface-embedded graphs. Recall that the outerplanar layering partitions the vertices of a planar graph $G$ into layers $L_1,\mathrm{\dots },L_m\subseteq V(G)$, where $L_i$ consists of the vertices on the outer boundary of $G-{\bigcup }_{j=1}^{i-1}{L}_j$. Thus, $L_1$ is outer boundary of $G$, $L_2$ is the outer boundary of $G-L_1$, and so forth. If $G$ is a graph embedded in a surface $\mathrm{\Sigma }$, the same layering procedure still applies. Indeed, we can fix a reference point $x_0\in \mathrm{\Sigma }$ and define the outer boundary of a $\mathrm{\Sigma }$-embedded graph as the boundary of the face containing $x_0$ (assuming the image of the embedding is disjoint from $x_0$). Given this, we can layer $G$ in the same way as above, by defining $L_i$ to be the vertices on the outer boundary of $G-{\bigcup }_{j=1}^{i-1}{L}_j$. We call this generalization radial layering for surface-embedded graphs. Now let $L_1,\mathrm{\dots },L_m$ be the radial layering of $G$. The analysis in [2] implies the following property of the layers (though not stated explicitly in [2]).

Then [2] simply defines each set $Z_i$ as the union of equidistant layers with distance $O(p)$ apart, that is, $Z_i=L_{q_i}\cup L_{\mathrm{\Delta }+q_i}\cup L_{2\mathrm{\Delta }+q_i}\cup \mathrm{\cdots }$ for some number $q_i\in [\mathrm{\Delta }]$ where $\mathrm{\Delta }=O(p)$. If the choices of $q_1,\mathrm{\dots },q_p$ are different, $Z_1,\mathrm{\dots },Z_p$ are disjoint. By Lemma 5, $Z_1,\mathrm{\dots },Z_p$ satisfy the RCD condition.

Now let us see what is the difficulty to generalize this construction so that it further satisfies condition 2 of Lemma 4. Consider the given set $\mathrm{\Phi }$ in Lemma 4, which is of size $c$. We want $\mathrm{\Phi }$ to be contained in the complement $G-{\bigcup }_{i=1}^p{Z}_i$, and more importantly, $\mathrm{\Phi }$ has to be in one connected component of $G-{\bigcup }_{i=1}^p{Z}_i$. To make $\mathrm{\Phi }$ contained in $G-{\bigcup }_{i=1}^p{Z}_i$ is easy. We can mark the layers $L_i$ intersecting $\mathrm{\Phi }$ as “bad” layers. There can be at most $c$ bad layers. When constructing $Z_1,\mathrm{\dots },Z_p$, we do not include these bad layers. According to Lemma 5, we can still guarantee that $Z_1,\mathrm{\dots },Z_p$ satisfy condition 1 of Lemma 4 even if we miss all bad layers, because the constant hidden in the bound of condition 1 can depend on $c$. However, to further require the vertices in $\mathrm{\Phi }$ lying in the same connected component of $G-{\bigcup }_{i=1}^p{Z}_i$ is impossible. Indeed, one can easily see that each layer $L_i$ is a separator in $G$ that separates the layers $L_1,\mathrm{\dots },L_{i-1}$ from the layers $L_{i+1},\mathrm{\dots },L_m$. The layers in $Z_1,\mathrm{\dots },Z_p$ separate the remaining part of $G$ into many “small” pieces where each piece consists of at most $O(p)$ consecutive layers. This highly-disconnected structure of $G-{\bigcup }_{i=1}^p{Z}_i$ naturally prevents the vertices in $\mathrm{\Phi }$ from lying in the same connected component, unless the layers containing $\mathrm{\Phi }$ are all close to each other.

Based on the above discussion, in order to satisfy both conditions in Lemma 4, we need to significantly modify the construction of [2] with various new ideas. As we have seen, in the previous construction, the layers in $Z_1,\mathrm{\dots },Z_p$ serve as “barriers” that prevent the vertices in $\mathrm{\Phi }$ from being connected in the complement graph. Therefore, a natural idea is to “break” these layers a little bit (i.e., remove some vertices from $Z_1,\mathrm{\dots },Z_p$) so that the vertices in $\mathrm{\Phi }$ can go across the barriers to connect with each other. However, by doing this, the layers in each $Z_i$ become broken, and thus the new $Z_i$ might violate the RCD condition, i.e., condition 1 of Lemma 4 (as we have fewer vertices to contract). As such, we have to break the layers in some structured way such that the vertices in $\mathrm{\Phi }$ can be connected in the complement graph and simultaneously the RCD condition of $Z_1,\mathrm{\dots },Z_p$ preserves, which is the main challenge in our construction. At this point, it is totally not clear how to achieve this goal. So next, we begin with some simple intuitions.

Let us consider the simplest case where $\mathrm{\Phi }$ only contains two vertices $s$ and $t$. In this case, it suffices to properly find an $(s,t)$-path $\pi$ in $G$ and then remove the vertices in $Z_1,\mathrm{\dots },Z_p$ on this path. Since we do not want to lose the RCD condition of $Z_1,\mathrm{\dots },Z_p$, $\pi$ should break each layer in $Z_1,\mathrm{\dots },Z_p$ as “little” as possible. So intuitively, a path that visits the layers $L_1,\mathrm{\dots },L_m$ monotonely (left part of Figure 2) is preferable to a path that goes back and forth across the layers many times (right part of Figure 2). If we do not have any requirement on the embedding of $G$ in $\mathrm{\Sigma }$, it is not always possible to find a monotone (or mostly monotone) path connecting $s$ and $t$. Thus, at the beginning (before the radial layering), we need to first modify the embedding of $G$ to a nice one, and do everything with respect to the nice embedding. For surface graphs, a $2$-cell embedding, in which each face is homeomorphic to a disk, is the nice embedding we need. One can always compute a $2$-cell embedding for $G$ in polynomial time as long as the genus of $G$ is a constant. (For almost-embeddable graphs, however, the situation is more involved, as we are not able to arbitrarily change the embedding of the embeddable part because of the vortices. We have to define another type of embedding for which we can safely modify a given embedding of the embeddable part to.) Now if $L_1,\mathrm{\dots },L_m$ are the radial layers for a 2-cell embedding of $G$, then one can go from every vertex in a layer $L_j$ to the previous layer $L_{j-1}$ by walking around the boundary of a face in between $L_{j-1}$ and $L_j$. It turns out that for every vertex $v\in L_j$ and index $i\le j$, there exists a path from $v$ to (some vertex in) $L_i$ that visits $L_j,L_{j-1},\mathrm{\dots },L_i$ monotonely. Suppose $s\in L_i$ and $t\in L_j$ where $i\le j$. Note that although we can go from $t$ to $L_i$ monotonely, there does not necessarily exist a monotone path from $t$ to $s$. So the key idea here is to, instead of using one path connecting $s$ and $t$, construct two monotone paths ${\pi }_s$ and ${\pi }_t$, where ${\pi }_s$ (resp., ${\pi }_t$) goes from $s$ (resp., $t$) to $L_1$. Then we do not include the layer $L_1$ in any of $Z_1,\mathrm{\dots },Z_p$ (which is fine according to Lemma 5). Because $L_1$ is the outer boundary of $G$ and the embedding of $G$ is 2-cell, $G[L_1]$ is connected. Therefore, $L_1$ together with the two paths ${\pi }_s$ and ${\pi }_t$ connects $s$ and $t$. The same idea directly generalizes to the case where $\mathrm{\Phi }$ has more than two vertices. For each vertex $v\in \mathrm{\Phi }$, we try to construct a path ${\pi }_v$ which goes monotonely from $v$ to $L_1$. Now $L_1$ together with all the paths connect everything in $\mathrm{\Phi }$. It then remains to show how to construct these $c$ monotone paths carefully so that they do not break the layers in $Z_1,\mathrm{\dots },Z_p$ too much.

Since $c$ is treated as a constant in Lemma 4, if we are able to construct one path, it is not surprising that the same idea generalizes to constructing $c$ paths. Thus, in what follows, we focus on the case $c=1$. We have $\mathrm{\Phi }=\{v\}$. Since the path $\pi$ from $v$ to $L_1$ we are going to construct is monotone, it crosses each layer $L_i$ at most once, that is, after it leaves $L_i$ for $L_{i-1}$, it never comes back to $L_i$. Therefore, we construct each part $L_i\cap \pi$ of $\pi$ from larger $i$ to smaller $i$ iteratively. When constructing $L_i\cap \pi$, we basically need to consider how to walk in the layer $L_i$ from an arbitrary starting vertex $s\in L_i$ to an “exit” vertex that is adjacent to $L_{i-1}$ so that the walk does not break $L_i$ too much. To this end, we have to figure out what “too much” means. In other words, how much can we break each layer $L_i$ so that $Z_1,\mathrm{\dots },Z_p$ still satisfy the RCD condition? By checking the proof of Lemma 5 in [2], we see that the bound in Lemma 5 mainly relies on the following two properties of each layer $L_i$ (where $L_{>i}$ is the union of $L_{i+1},\mathrm{\dots },L_m$ and $L_{\le i}$ is the union of $L_1,\mathrm{\dots },L_i$).

1. (I)

   The neighbors of each connected component of $G[L_{>i}]$ lie in one face of $G[L_{\le i}]$.

2. (II)

   For every $L^{\prime }\subseteq L_i$, each connected component of $G[L_{>i}]$ is adjacent to $O(|L^{\prime }|)$ vertices in the graph $G/(L_i\setminus L^{\prime })$.

Using the above two properties and the fact that the layers in each of $Z_1,\mathrm{\dots },Z_p$ are only $O(p)$ distance apart, one can finally show that $Z_1,\mathrm{\dots },Z_p$ satisfies the RCD condition. Now we have the path $\pi$ that breaks $L_i$. So we can only include in $Z_1,\mathrm{\dots },Z_p$ the part $L_i\setminus \pi$. In this case, in order to make the proof work, we need the modified version of condition II above: for every $L^{\prime }\subseteq L_i\setminus \pi$, each connected component of $G[L_{>i}]$ is adjacent to $O(|L^{\prime }|)$ vertices in the graph $G/((L_i\setminus \pi )\setminus L^{\prime })$. However, it is easy to see that this is impossible. Consider the simplest case where $L^{\prime }=\mathrm{\varnothing }$. We want each connected component of $G[L_{>i}]$ to have $O(1)$ neighbors in $G/(L_i\setminus \pi )$. But in the worst case, after $\pi$ reaches $L_i$, it needs to go inside $L_i$ for a long distance in order to arrive at an exit vertex to leave $L_i$ for $L_{i-1}$. Therefore, it can happen that $\pi$ contains a large fraction of $L_i$ in which many vertices can be adjacent to the same connected component $C$ of $G[L_{>i}]$. As these vertices are not contracted in $G/(L_i\setminus \pi )$, the number of neighbors of $C$ in $G/(L_i\setminus \pi )$ can be unbounded.

Going deeper into the proof of [2] shows that the reason for why the above two properties help is basically the following. These two properties allow us to partition $G$ into two parts $G[L_{\le i}]$ and $G[L_{>i}]$ such that the connection between these two parts becomes “weak” after contracting a large subset of $L_i$, namely, each connected component of $G[L_{>i}]$ is only adjacent to few vertices in $G[L_{\le i}]$ which lie in one face of $G[L_{\le i}]$ (before contraction). Now because the part in $L_i\cap \pi$ cannot be contracted, we are no longer able to have a weak connection between $G[L_{\le i}]$ and $G[L_{>i}]$. To get rid of this issue, our key idea here is to partition $G$ into two parts in a different way. Specifically, when determining the part of $\pi$ contained in $L_i$, we also compute another subset $L_i^{+}\subseteq L_i$. Then we partition $G$ into two parts $G[L_{\le i}\setminus L_i^{+}]$ and $G[L_{>i}\cup L_i^{+}]$, that is, we move $L_i^{+}$ from the part $G[L_{\le i}]$ to the part $G[L_{>i}]$. The choice of $L_i^{+}$ will guarantee the aforementioned weak connection between the two new parts. Formally, $L_i^{+}$ (and $\pi$) satisfies the following properties.