**► Lemma 1.** A simple graph $G$ satisfies paw $\not\leq_{tm} G$ if and only if each connected component of $G$ is either a cycle or a tree.

**Proof.** It is easy to see that neither a cycle nor a tree contain the paw as a topological minor. Let $G$ be a graph such that paw $\not\leq_{tm} G$. Let us assume w.l.o.g. that $G$ is connected. If $G$ does not contain a cycle, then it is a tree. Otherwise, let $C$ be a chordless cycle in $G$. If $G$ contains a vertex $v$ that is not in $C$, then, as $G$ is connected, there exists a path from $v$ to $C$ containing at least 2 vertices. This is not possible, as it would imply that $G$ contains the paw as a topological minor. As $C$ is chordless and $G$ is simple, we obtain that $G$ is exactly the cycle $C$, and the lemma follows. ◀

We present an algorithm that solves the decision version of {$PAW$}-TM-DELETION. As the algorithm that we presented for {$C_4$}-TM-DELETION in [1], this algorithm is based on the one given in [2, Section 3.5] for FEEDBACK VERTEX SET. Let $G$ be a graph and $k$ be an integer. The idea of the following algorithm is to partition $V(G)$ into three sets. The first one will be the solution set $S$, the second one will be a set $F$ of vertices that induces a forest, and the third one will be a set $C$ of vertices that induces a collection of cycles. If we can partition our graph into three such sets ($S, F, C$) such that there is no edge between a vertex of $F$ and a vertex of $C$ and such that $|S| \leq k$, then, using Lemma 1, we know that $tm_{\{paw\}}(G) \leq k$. On the other hand, if such a partition does not exist, we know that $tm_{\{paw\}}(G) > k$. The main idea of this algorithm is to combine classical dynamic programming techniques in order to verify that $C$ induces a collection of cycles, and the rank-based approach in order to verify that $F$ induces a forest.

As for {$C_4$}-TM-DELETION (see [1]), we define a new graph $G_0 = (V(G) \cup \{v_0\}, E(G) \cup E_0)$, where $v_0$ is a new vertex and $E_0 = \{\{v_0, v\} | v \in V(G)\}$. For each subgraph $H$ of $G_0$, for each $Z_1 \subseteq V(H)$, and for each $Y \subseteq E_0 \cap E(H[Z_1])$, we denote by $H\langle Z_1, Y \rangle$ the graph $(Z_1, Y \cup E(H[Z_1 \setminus \{v_0\}]))$.

Given a nice tree decomposition of $G$ of width $w$, we define a nice tree decomposition (($T, \mathcal{X}$), $r, \mathcal{G}$) of $G_0$ of width $w+1$ such that the only empty bags are the root and the leaves and for each $t \in T$, if $X_t \neq \emptyset$, then $v_0 \in X_t$. Note that this can be done in linear time. For each bag $t$, each integers $i, j$, and $\ell$, each function $s: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, each function $s_0: \{v_0\} \times s^{-1}(1) \to \{0, 1\}$, and each partition $p \in \Pi(s^{-1}(1))$, we define:

$$
\begin{align*}
\mathcal{E}_t(p, \mathbf{s}, \mathbf{s}_0, i, j, \ell) &= \{(Z_1, Z_2, Y) \mid (Z_1, Z_2, Y) \in 2^{V_t} \times 2^{V_t} \times 2^{E_0 \cap E(G_t)}, Z_1 \cap Z_2 = \emptyset, \\
& \qquad |Z_1| = i, |Z_2| = \ell, |E(G_t[Z_1 \setminus \{v_0\}]) \cup Y| = j, \\
& \qquad \forall e \in E_0 \cap E_t, \mathbf{s}_0(e) = 1 \Leftrightarrow e \in Y, \\
& \qquad \forall v \in Z_2 \cap X_t, \mathbf{s}(v) = 2_z \text{ with } z = \deg_{G_t[Z_2]}(v), \\
& \qquad \forall v \in Z_2 \setminus X_t, \deg_{G_t[Z_2]}(v) = 2, \\
& \qquad Z_1 \cap X_t = s^{-1}(1), v_0 \in X_t \Rightarrow \mathbf{s}(v_0) = 1, \\
& \qquad \forall u \in Z_1 \setminus X_t: \text{ either } t \text{ is the root or} \\
& \qquad \quad \exists u' \in s^{-1}(1): u \text{ and } u' \text{ are connected in } G_t\langle Z_1, Y \rangle, \\
& \qquad \forall v_1, v_2 \in s^{-1}(1): p \subseteq V_t[\{v_1, v_2\}] \Leftrightarrow v_1 \text{ and } v_2 \text{ are connected in } G_t\langle Z_1, Y \rangle, \\
& \qquad \forall (u, v) \in (Z_1 \setminus \{v_0\}) \times Z_2, \{u, v\} \notin E(G_t)
\end{align*}
$$

$$
\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \{p \mid p \in \Pi(\mathbf{s}^{-1}(1)), \mathcal{E}_t(p, \mathbf{s}, \mathbf{s}_0, i, j, \ell) \neq \emptyset\}.
$$
**► Lemma 1.** A simple graph $G$ satisfies paw $\not\leq_{tm} G$ if and only if each connected component of $G$ is either a cycle or a tree.

**Proof.** It is easy to see that neither a cycle nor a tree contain the paw as a topological minor. Let $G$ be a graph such that paw $\not\leq_{tm} G$. Let us assume w.l.o.g. that $G$ is connected. If $G$ does not contain a cycle, then it is a tree. Otherwise, let $C$ be a chordless cycle in $G$. If $G$ contains a vertex $v$ that is not in $C$, then, as $G$ is connected, there exists a path from $v$ to $C$ containing at least 2 vertices. This is not possible, as it would imply that $G$ contains the paw as a topological minor. As $C$ is chordless and $G$ is simple, we obtain that $G$ is exactly the cycle $C$, and the lemma follows. ◀

We present an algorithm that solves the decision version of {$PAW$}-TM-DELETION. As the algorithm that we presented for {$C_4$}-TM-DELETION in [1], this algorithm is based on the one given in [2, Section 3.5] for FEEDBACK VERTEX SET. Let $G$ be a graph and $k$ be an integer. The idea of the following algorithm is to partition $V(G)$ into three sets. The first one will be the solution set $S$, the second one will be a set $F$ of vertices that induces a forest, and the third one will be a set $C$ of vertices that induces a collection of cycles. If we can partition our graph into three such sets ($S, F, C$) such that there is no edge between a vertex of $F$ and a vertex of $C$ and such that $|S| \leq k$, then, using Lemma 1, we know that $tm_{\{paw\}}(G) \leq k$. On the other hand, if such a partition does not exist, we know that $tm_{\{paw\}}(G) > k$. The main idea of this algorithm is to combine classical dynamic programming techniques in order to verify that $C$ induces a collection of cycles, and the rank-based approach in order to verify that $F$ induces a forest.

As for {$C_4$}-TM-DELETION (see [1]), we define a new graph $G_0 = (V(G) \cup \{v_0\}, E(G) \cup E_0)$, where $v_0$ is a new vertex and $E_0 = \{\{v_0, v\} | v \in V(G)\}$. For each subgraph $H$ of $G_0$, for each $Z_1 \subseteq V(H)$, and for each $Y \subseteq E_0 \cap E(H[Z_1])$, we denote by $H\langle Z_1, Y \rangle$ the graph $(Z_1, Y \cup E(H[Z_1 \setminus \{v_0\}]))$.

Given a nice tree decomposition of $G$ of width $w$, we define a nice tree decomposition (($T, \mathcal{X}$), $r, \mathcal{G}$) of $G_0$ of width $w+1$ such that the only empty bags are the root and the leaves and for each $t \in T$, if $X_t \neq \emptyset$, then $v_0 \in X_t$. Note that this can be done in linear time. For each bag $t$, each integers $i, j$, and $\ell$, each function $s: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, each function $s_0: \{v_0\} \times s^{-1}(1) \to \{0, 1\}$, and each partition $p \in \Pi(s^{-1}(1))$, we define:

$$
\begin{align*}
\mathcal{E}_t(p, \mathbf{s}, \mathbf{s}_0, i, j, \ell) &= \{(Z_1, Z_2, Y) \mid (Z_1, Z_2, Y) \in 2^{V_t} \times 2^{V_t} \times 2^{E_0 \cap E(G_t)}, Z_1 \cap Z_2 = \emptyset, \\
& \quad |Z_1| = i, |Z_2| = \ell, |E(G_t[Z_1 \setminus \{v_0\}]) \cup Y| = j, \\
& \quad \forall e \in E_0 \cap E_t, \mathbf{s}_0(e) = 1 \Leftrightarrow e \in Y, \\
& \quad \forall v \in Z_2 \cap X_t, \mathbf{s}(v) = 2_z \text{ with } z = \deg_{G_t[Z_2]}(v), \\
& \quad \forall v \in Z_2 \setminus X_t, \deg_{G_t[Z_2]}(v) = 2, \\
& \quad Z_1 \cap X_t = s^{-1}(1), v_0 \in X_t \Rightarrow \mathbf{s}(v_0) = 1, \\
& \quad \forall u \in Z_1 \setminus X_t: \text{ either } t \text{ is the root or} \\
& \quad \quad \exists u' \in s^{-1}(1) : u \text{ and } u' \text{ are connected in } G_t\langle Z_1, Y \rangle, \\
& \quad \quad \forall v_1, v_2 \in s^{-1}(1) : p \subseteq V_t[\{v_1, v_2\}] \Leftrightarrow v_1 \text{ and } v_2 \text{ are connected in } G_t\langle Z_1, Y \rangle, \\
& \quad \quad \forall (u, v) \in (Z_1 \setminus \{v_0\}) \times Z_2, \{u, v\} \notin E(G_t)
\end{align*}
$$

$$
\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \{p \mid p \in \Pi(\mathbf{s}^{-1}(1)), \mathcal{E}_t(p, \mathbf{s}, \mathbf{s}_0, i, j, \ell) \neq \emptyset\}.
$$
## 2:6 A Complexity Dichotomy for Hitting Small Planar Minors

In the definition of $\mathcal{E}_t$, the sets $Z_1$ (resp. $Z_2$) correspond to the set $F$ (resp. $C$) restricted to $G_t$. The vertex $v_0$ and the set $Y$ exist to ensure that $F$ will be connected.

By Lemma 1, we have that the given instance of $\{\text{PAW}\}$-TM-DELETION is a YES-instance if and only if for some $i$ and $\ell$, $i + \ell \ge |V(G) \cup \{v_0\}| - k$ and $\mathcal{A}_r(\emptyset, i, i - 1, \ell) \ne \emptyset$. For each $t \in V(T)$, we assume that we have already computed $\mathcal{A}_{t'}$ for every children $t'$ of $t$, and we proceed to the computation of $\mathcal{A}_t$. As usual, we distinguish several cases depending on the type of node $t$.

**Leaf.** By definition of $\mathcal{A}_t$, we have $\mathcal{A}_t(\emptyset, \emptyset, 0, 0, 0) = \{\emptyset\}$.

**Introduce vertex.** Let $v$ be the insertion vertex of $X_t$, let $t'$ be the child of $t$, let $\mathbf{s}: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, $\mathbf{s}_0: \{v_0\} \times \mathbf{s}^{-1}(1) \to \{0, 1\}$, and let $H = G_t(\mathbf{s}^{-1}(1), \mathbf{s}_0^{-1}(1))$.

- If $v = v_0$ and $\mathbf{s}(v_0) \in \{0, 2_0, 2_1, 2_2\}$, then by definition of $\mathcal{A}_t$ we have that $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \emptyset$.

- Otherwise, if $v = v_0$, then by construction of the nice tree decomposition, we know that $t'$ is a leaf of $T$ and so $\mathbf{s} = \{(v_0, 1)\}$, $j = \ell = i - 1 = 0$ and $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \text{ins}(\{v_0\}, \mathcal{A}_{t'}(\emptyset, \emptyset, 0, 0, 0))$.

- Otherwise, if $\mathbf{s}(v) = 0$, then, by definition of $\mathcal{A}_t$, it holds that $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \mathcal{A}_{t'}(\mathbf{s}|_{X_{t'}}, \mathbf{s}|_{E_{t'}}, i, j, \ell)$.

- Otherwise, if $\mathbf{s}(v) = 2_z$, $z \in \{0, 1, 2\}$, then let $Z'_2 = N_{G_t[X_t]}(v) \setminus \mathbf{s}^{-1}(0)$. If $Z'_2 \not\subseteq \mathbf{s}^{-1}(\{2_1, 2_2\})$ or $|Z'_2| \ne z$, then $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \emptyset$. Otherwise $Z'_2 \subseteq \mathbf{s}^{-1}(\{2_1, 2_2\})$ and $|Z'_2| = z$, and with $\mathbf{s}' : X_{t'} \to \{0, 1, 2_0, 2_1, 2_2\}$ defined such that $\forall v' \in X_{t'} \setminus Z'_2$, $\mathbf{s}'(v') = \mathbf{s}(v')$ and for each $v' \in Z'_2$ such that $\mathbf{s}(v') = 2_{z'}$, $z' \in \{1, 2\}$, $\mathbf{s}'(v') = 2_{z' - 1}$. It holds that $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \mathcal{A}_{t'}(\mathbf{s}', \mathbf{s}_0, i, j, \ell - 1)$.

- Otherwise, we know that $v \ne v_0$, $\mathbf{s}(v) = 1$, and $v_0 \in N_{G[\mathbf{s}^{-1}(1)]}(v)$. First, if $N_{G_t[X_t]}(v) \setminus \mathbf{s}^{-1}(0) \not\subseteq \mathbf{s}^{-1}(1)$, then $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \emptyset$. Indeed, this implies that the cycle part and the forest part are connected. As $\mathbf{s}(v) = 1$, we have to insert $v$ in the forest part and we have to make sure that all vertices of $N_H[v]$ are in the same connected component of $H$. The only remaining choice is to insert the edge $\{v, v_0\}$ or not. Again, this is handled by the function $\mathbf{s}_0$. By adding $v$, we add one vertex and $|N_H(v)|$ edges in the forest part. Therefore, we have that

$$ \mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, \mathbf{r}, i, j, \ell) = \text{glue}(N_H[v], \text{ins}(\{v\}, \mathcal{A}_{t'}(\mathbf{s}|_{X_{t'}}, \mathbf{s}_0|_{E_{t'}}, i-1, j-|N_H(v)|, \ell))) $$

**Forget vertex.** Let $v$ be the forget vertex of $X_t$, let $t'$ be the child of $t$, and let $\mathbf{s}: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$. As a vertex from the collection of cycles can be removed only if it has exactly two neighbors, we obtain that

$$ \begin{align*} \mathcal{A}_t(\mathbf{s}, i, j, \ell) &= \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 0)\}, \mathbf{s}_0, i, j, \ell) \\ &\quad \uplus \text{proj}(\{v\}, \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 1)\}, \mathbf{s}_0 \cup \{(\{v_0, v\}, 0)\}, i, j, \ell)) \\ &\quad \uplus \text{proj}(\{v\}, \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 1)\}, \mathbf{s}_0 \cup \{(\{v_0, v\}, 1)\}, i, j, \ell)) \\ &\quad \uplus \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 2_2)\}, \mathbf{s}_0, i, j, \ell). \end{align*} $$

**Join.** Let $t'$ and $t''$ be the two children of $t$, let $\mathbf{s}: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, $\mathbf{s}_0: \{v_0\} \times \mathbf{s}^{-1}(1) \to \{0, 1\}$, and let $H = G_t(\mathbf{s}^{-1}(1), \mathbf{s}_0^{-1}(1))$. Given three functions $\mathbf{s}^*, \mathbf{s}', \mathbf{s}''$: $X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, we say that $\mathbf{s}^* = \mathbf{s}' \oplus \mathbf{s}''$ if for each $v \in \mathbf{s}^{-1}(\{0, 1\})$, $\mathbf{s}^*(v) = \mathbf{s}'(v) = \mathbf{s}''(v)$, and for each $v \in X_t$ such that $\mathbf{s}^*(v) = 2_z$, $z \in \{0, 1, 2\}$, there exist $z'$, $z'' \in \{0, 1, 2\}$ such that $\mathbf{s}'(v) = 2_{z'}$, $\mathbf{s}''(v) = 2_{z''}$, and $z = z' + z'' - \text{deg}_{G_t[X_t \setminus \mathbf{s}^{-1}(0)]}(v)$.
## 2:6 A Complexity Dichotomy for Hitting Small Planar Minors

In the definition of $\mathcal{E}_t$, the sets $Z_1$ (resp. $Z_2$) correspond to the set $F$ (resp. $C$) restricted to $G_t$. The vertex $v_0$ and the set $Y$ exist to ensure that $F$ will be connected.

By Lemma 1, we have that the given instance of {PAW}-TM-DELETION is a YES-instance if and only if for some $i$ and $\ell$, $i + \ell \ge |V(G) \cup \{v_0\}| - k$ and $\mathcal{A}_r(\emptyset, i, i - 1, \ell) \ne \emptyset$. For each $t \in V(T)$, we assume that we have already computed $\mathcal{A}_{t'}$ for every children $t'$ of $t$, and we proceed to the computation of $\mathcal{A}_t$. As usual, we distinguish several cases depending on the type of node $t$.

**Leaf.** By definition of $\mathcal{A}_t$, we have $\mathcal{A}_t(\emptyset, \emptyset, 0, 0, 0) = \{\emptyset\}$.

**Introduce vertex.** Let $v$ be the insertion vertex of $X_t$, let $t'$ be the child of $t$, let $\mathbf{s}: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, $\mathbf{s}_0: \{v_0\} \times \mathbf{s}^{-1}(1) \to \{0, 1\}$, and let $H = G_t(\mathbf{s}^{-1}(1), \mathbf{s}_0^{-1}(1))$.

- If $v = v_0$ and $\mathbf{s}(v_0) \in \{0, 2_0, 2_1, 2_2\}$, then by definition of $\mathcal{A}_t$ we have that $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \emptyset$.

- Otherwise, if $v = v_0$, then by construction of the nice tree decomposition, we know that $t'$ is a leaf of $T$ and so $\mathbf{s} = \{(v_0, 1)\}$, $j = \ell = i - 1 = 0$ and $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \text{ins}(\{v_0\}, \mathcal{A}_{t'}(\emptyset, \emptyset, 0, 0, 0))$.

- Otherwise, if $\mathbf{s}(v) = 0$, then, by definition of $\mathcal{A}_t$, it holds that $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \mathcal{A}_{t'}(\mathbf{s}|_{X_{t'}}, \mathbf{s}|_{E_{t'}}, i, j, \ell)$.

- Otherwise, if $\mathbf{s}(v) = 2_z$, $z \in \{0, 1, 2\}$, then let $Z'_2 = N_{G_t[X_t]}(v) \setminus \mathbf{s}^{-1}(0)$. If $Z'_2 \not\subseteq \mathbf{s}^{-1}(\{2_1, 2_2\})$ or $|Z'_2| \ne z$, then $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \emptyset$. Otherwise $Z'_2 \subseteq \mathbf{s}^{-1}(\{2_1, 2_2\})$ and $|Z'_2| = z$, and with $\mathbf{s}' : X_{t'} \to \{0, 1, 2_0, 2_1, 2_2\}$ defined such that $\forall v' \in X_{t'} \setminus Z'_2$, $\mathbf{s}'(v') = \mathbf{s}(v')$ and for each $v' \in Z'_2$ such that $\mathbf{s}(v') = 2_{z'}$, $z' \in \{1, 2\}$, $\mathbf{s}'(v') = 2_{z' - 1}$. It holds that $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \mathcal{A}_{t'}(\mathbf{s}', \mathbf{s}_0, i, j, \ell - 1)$.

- Otherwise, we know that $v \ne v_0$, $\mathbf{s}(v) = 1$, and $v_0 \in N_{G[\mathbf{s}^{-1}(1)]}(v)$. First, if $N_{G_t[X_t]}(v) \setminus \mathbf{s}^{-1}(0) \not\subseteq \mathbf{s}^{-1}(1)$, then $\mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \emptyset$. Indeed, this implies that the cycle part and the forest part are connected. As $\mathbf{s}(v) = 1$, we have to insert $v$ in the forest part and we have to make sure that all vertices of $N_H[v]$ are in the same connected component of $H$. The only remaining choice is to insert the edge $\{v, v_0\}$ or not. Again, this is handled by the function $\mathbf{s}_0$. By adding $v$, we add one vertex and $|N_H(v)|$ edges in the forest part. Therefore, we have that

$$ \mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, \mathbf{r}, i, j, \ell) = \text{glue}(N_H[v], \text{ins}(\{v\}, \mathcal{A}_{t'}(\mathbf{s}|_{X_{t'}}, \mathbf{s}_0|_{E_{t'}}, i-1, j-|N_H(v)|, \ell))) $$

**Forget vertex.** Let $v$ be the forget vertex of $X_t$, let $t'$ be the child of $t$, and let $\mathbf{s}: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$. As a vertex from the collection of cycles can be removed only if it has exactly two neighbors, we obtain that

$$ \begin{align*} \mathcal{A}_t(\mathbf{s}, i, j, \ell) &= \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 0)\}, \mathbf{s}_0, i, j, \ell) \\ &\quad \uplus \text{proj}(\{v\}, \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 1)\}, \mathbf{s}_0 \cup \{(\{v_0, v\}, 0)\}, i, j, \ell)) \\ &\quad \uplus \text{proj}(\{v\}, \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 1)\}, \mathbf{s}_0 \cup \{(\{v_0, v\}, 1)\}, i, j, \ell)) \\ &\quad \uplus \mathcal{A}_{t'}(\mathbf{s} \cup \{(v, 2_2)\}, \mathbf{s}_0, i, j, \ell). \end{align*} $$

**Join.** Let $t'$ and $t''$ be the two children of $t$, let $\mathbf{s}: X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, $\mathbf{s}_0: \{v_0\} \times \mathbf{s}^{-1}(1) \to \{0, 1\}$, and let $H = G_t(\mathbf{s}^{-1}(1), \mathbf{s}_0^{-1}(1))$. Given three functions $\mathbf{s}^*, \mathbf{s}', \mathbf{s}'' : X_t \to \{0, 1, 2_0, 2_1, 2_2\}$, we say that $\mathbf{s}^* = \mathbf{s}' \oplus \mathbf{s}''$ if for each $v \in \mathbf{s}^{-1}(\{0, 1\})$, $\mathbf{s}^*(v) = \mathbf{s}'(v) = \mathbf{s}''(v)$, and for each $v \in X_t$ such that $\mathbf{s}^*(v) = 2_z$, $z \in \{0, 1, 2\}$, there exist $z'$, $z'' \in \{0, 1, 2\}$ such that $\mathbf{s}'(v) = 2_{z'}$, $\mathbf{s}''(v) = 2_{z''}$, and $z = z' + z'' - \text{deg}_{G_t[X_t \setminus \mathbf{s}^{-1}(0)]}(v)$.
We join every compatible entries $A_t'(\mathbf{s}', \mathbf{s}'_0, i', j', \ell')$ and $A_{t''}(\mathbf{s}''_0, \mathbf{s}''_0, i'', j'', \ell'')$. For two such entries being compatible, we need $\mathbf{s}' \oplus \mathbf{s}''$ to be defined and $\mathbf{s}'_0 = \mathbf{s}''_0$. We obtain that

$$ \mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \biguplus \text{join}(A_{t'}(\mathbf{s}', \mathbf{s}_0, i', j', \ell'), A_{t''}(\mathbf{s}''_0, \mathbf{r}''_0, i'', j'', \ell'')). $$
$$ \begin{array}{l} \mathbf{s}', \mathbf{s}'' : X_t \to \{0,1,2_0,2_1,2_2\}, \\ \mathbf{s} = \mathbf{s}_1 \oplus \mathbf{s}_2 \\ i'+i''=i+|V(H)| \\ j'+j''=j+|E(H)| \\ \ell'+\ell''=\ell+|\mathbf{s}^{-1}(\{2_0,2_1,2_2\})| \end{array} $$

**▶ Theorem 2.** {PAW}-TM-DELETION can be solved in time $2^{O(\mathrm{tw})} \cdot n^7$.

**Proof.** The algorithm works in the following way. For each node $t \in V(T)$ and for each entry $M$ of its table, instead of storing $\mathcal{A}_t(M)$, we store $\mathcal{A}'_t(M) = \text{reduce}(\mathcal{A}_t(M))$ by using [2, Theorem 3.7]. As each of the operations we use preserves representation by [2, Lemma 3.6], we obtain that for each node $t \in V(T)$ and for each possible entry $M$, $\mathcal{A}'_t(M)$ represents $\mathcal{A}_t(M)$. In particular, we have that $\mathcal{A}'_t(M) = \text{reduce}(\mathcal{A}_t(M))$ for each possible entry $M$. Using the definition of $\mathcal{A}_t$ and Lemma 1, we have that $\text{tm}_{\{\text{paw}\}}(G) \le k$ if and only if for some $i$ and $\ell$, $i + \ell \ge |V(G) \cup \{v_0\}| - k$ and $\mathcal{A}'_t(\emptyset, i, i-1, \ell) \ne \emptyset$.

We now focus on the running time of the algorithm. The size of the intermediate sets of weighted partitions for a leaf node and for an introduce vertex node, are upper-bounded by $2^{|\mathbf{s}^{-1}(1)|}$. For a forget vertex node, we take the union of four sets of size $2^{|\mathbf{s}^{-1}(1)|}$, so the intermediate sets of weighted partitions have size at most $4 \cdot 2^{|\mathbf{s}^{-1}(1)|}$. For a join node, as in the big union operation we take into consideration at most $5^{|X_t|}$ possible functions $\mathbf{s}'$, as many functions $\mathbf{s}''$, at most $n + |\mathbf{s}^{-1}(1)|$ choices for $i'$ and $i''$, at most $n + |\mathbf{s}^{-1}(1)|$ choices for $j'$ and $j''$ (as we can always assume, during the algorithm, that $H$ is a forest), and at most $n + |\mathbf{s}^{-1}(\{2_0, 2_1, 2_2\})|$ choices for $\ell'$ and $\ell''$, we obtain that the intermediate sets of weighted partitions have size at most $25^{|X_t|} \cdot (n + |\mathbf{s}^{-1}(1)|)^2 \cdot (n + |\mathbf{s}^{-1}(\{2_0, 2_1, 2_2\})|) \cdot 4^{|\mathbf{s}^{-1}(1)|}$. We obtain that the intermediate sets of weighted partitions have size at most $(n + |X_t|)^3 \cdot 100^{|X_t|}$. Moreover, for each node $t \in V(T)$, the function reduce will be called as many times as the number of possible entries, i.e., at most $2^{O(w)} \cdot n^3$ times. Thus, using [2, Theorem 3.7], $\mathcal{A}'_t$ can be computed in time $2^{O(w)} \cdot n^6$. The theorem follows by taking into account the linear number of nodes in a nice tree decomposition. ◀

## 4 Superexponential lower bounds

Let $\mathcal{Q} = \{P_5\} \cup \{K_{2,s} \mid s \ge 3\} \cup \{\theta_s \mid s \ge 3\}$ and let $\mathcal{R} = \{K_{1,s} \mid s \ge 4\}$. In this section, we provide superexponential lower bounds for $\{H\}$-M-DELETION when $H \in \mathcal{Q} \cup \mathcal{R}$, for $\{H\}$-TM-DELETION when $H \in \mathcal{Q}$, and for both problems for some particular graphs on 5 vertices depicted in Figure 1, namely the **cricket**, the **px**, the **butterfly**, the **co-banner**, the **bull**, the **kite**, and the ** dart**. As mentioned before, the reductions of this section are strongly inspired by the ideas of Bonnet et al. [4]. More precisely, we will prove the following theorems.

**▶ Theorem 3.** Let $H \in \mathcal{Q} \cup \mathcal{R}$. Unless the ETH fails, $\{H\}$-M-DELETION cannot be solved in time $2^{o(\mathrm{tw} \log \mathrm{tw})} \cdot n^{O(1)}$.

**▶ Theorem 4.** Let $H \in \mathcal{Q}$. Unless the ETH fails, $\{H\}$-TM-DELETION cannot be solved in time $2^{o(\mathrm{tw} \log \mathrm{tw})} \cdot n^{O(1)}$.

**▶ Theorem 5.** Let $H \in \{\{\text{cricket}\}, \{\text{px}\}, \{\text{butterfly}\}, \{\text{co-banner}\}, \{\text{bull}\}, \{\text{kite}\}, \{\text{ dart}\}\}$. Unless the ETH fails, neither $\{H\}$-M-DELETION nor $\{H\}$-TM-DELETION can be solved in time $2^{o(\mathrm{tw} \log \mathrm{tw})} \cdot n^{O(1)}$.
We join every compatible entries $A_t'(\mathbf{s}', \mathbf{s}'_0, i', j', \ell')$ and $A_{t''}(\mathbf{s}'', \mathbf{s}''_0, i'', j'', \ell'')$. For two such entries being compatible, we need $\mathbf{s}' \oplus \mathbf{s}''$ to be defined and $\mathbf{s}'_0 = \mathbf{s}''_0$. We obtain that

$$ \mathcal{A}_t(\mathbf{s}, \mathbf{s}_0, i, j, \ell) = \biguplus \text{join}(A_{t'}(\mathbf{s}', \mathbf{s}_0, i', j', \ell'), A_{t''}(\mathbf{s}'', \mathbf{s}_0, \mathbf{r}'', i'', j'', \ell'')). $$
$$ \begin{array}{l} \mathbf{s}', \mathbf{s}'' : X_t \to \{0,1,2_0,2_1,2_2\}, \\ \mathbf{s} = \mathbf{s}_1 \oplus \mathbf{s}_2 \\ i'+i''=i+|V(H)| \\ j'+j''=j+|E(H)| \\ \ell'+\ell''=\ell+|\mathbf{s}^{-1}(\{2_0,2_1,2_2\})| \end{array} $$

**▶ Theorem 2.** {PAW}-TM-DELETION can be solved in time $2^{O(\mathrm{tw})} \cdot n^7$.

**Proof.** The algorithm works in the following way. For each node $t \in V(T)$ and for each entry $M$ of its table, instead of storing $\mathcal{A}_t(M)$, we store $\mathcal{A}'_t(M) = \text{reduce}(\mathcal{A}_t(M))$ by using [2, Theorem 3.7]. As each of the operations we use preserves representation by [2, Lemma 3.6], we obtain that for each node $t \in V(T)$ and for each possible entry $M$, $\mathcal{A}'_t(M)$ represents $\mathcal{A}_t(M)$. In particular, we have that $\mathcal{A}'_t(M) = \text{reduce}(\mathcal{A}_t(M))$ for each possible entry $M$. Using the definition of $\mathcal{A}_t$ and Lemma 1, we have that $\text{tm}_{\{\text{paw}\}}(G) \le k$ if and only if for some $i$ and $\ell$, $i + \ell \ge |V(G) \cup \{v_0\}| - k$ and $\mathcal{A}'_t(\emptyset, i, i - 1, \ell) \ne \emptyset$.

We now focus on the running time of the algorithm. The size of the intermediate sets of weighted partitions for a leaf node and for an introduce vertex node, are upper-bounded by $2^{|\mathbf{s}^{-1}(1)|}$. For a forget vertex node, we take the union of four sets of size $2^{|\mathbf{s}^{-1}(1)|}$, so the intermediate sets of weighted partitions have size at most $4 \cdot 2^{|\mathbf{s}^{-1}(1)|}$. For a join node, as in the big union operation we take into consideration at most $5^{|X_t|}$ possible functions $\mathbf{s}'$, as many functions $\mathbf{s}''$, at most $n + |\mathbf{s}^{-1}(1)|$ choices for $i'$ and $i''$, at most $n + |\mathbf{s}^{-1}(1)|$ choices for $j'$ and $j''$ (as we can always assume, during the algorithm, that $H$ is a forest), and at most $n + |\mathbf{s}^{-1}(\{2_0, 2_1, 2_2\})|$ choices for $\ell'$ and $\ell''$, we obtain that the intermediate sets of weighted partitions have size at most $25^{|X_t|} \cdot (n + |\mathbf{s}^{-1}(1)|)^2 \cdot (n + |\mathbf{s}^{-1}(\{2_0, 2_1, 2_2\})|) \cdot 4^{|\mathbf{s}^{-1}(1)|}$. We obtain that the intermediate sets of weighted partitions have size at most $(n + |X_t|)^3 \cdot 100^{|X_t|}$. Moreover, for each node $t \in V(T)$, the function reduce will be called as many times as the number of possible entries, i.e., at most $2^{O(w)} \cdot n^3$ times. Thus, using [2, Theorem 3.7], $\mathcal{A}'_t$ can be computed in time $2^{O(w)} \cdot n^6$. The theorem follows by taking into account the linear number of nodes in a nice tree decomposition. ▼

## 4 Superexponential lower bounds

Let $\mathcal{Q} = \{P_5\} \cup \{K_{2,s} \mid s \ge 3\} \cup \{\theta_s \mid s \ge 3\}$ and let $\mathcal{R} = \{K_{1,s} \mid s \ge 4\}$. In this section, we provide superexponential lower bounds for $\{H\}$-M-DELETION when $H \in \mathcal{Q} \cup \mathcal{R}$, for $\{H\}$-TM-DELETION when $H \in \mathcal{Q}$, and for both problems for some particular graphs on 5 vertices depicted in Figure 1, namely the **cricket**, the **px**, the **butterfly**, the **co-banner**, the **bull**, the **kite**, and the ** dart**. As mentioned before, the reductions of this section are strongly inspired by the ideas of Bonnet et al. [4]. More precisely, we will prove the following theorems.

**▶ Theorem 3.** Let $H \in \mathcal{Q} \cup \mathcal{R}$. Unless the ETH fails, $\{H\}$-M-DELETION cannot be solved in time $2^{o(\mathrm{tw} \log \mathrm{tw})} \cdot n^{O(1)}$.

**▶ Theorem 4.** Let $H \in \mathcal{Q}$. Unless the ETH fails, $\{H\}$-TM-DELETION cannot be solved in time $2^{o(\mathrm{tw} \log \mathrm{tw})} \cdot n^{O(1)}$.

**▶ Theorem 5.** Let $H \in \{\{\text{cricket}\}, \{\text{px}\}, \{\text{butterfly}\}, \{\text{co-banner}\}, \{\text{bull}\}, \{\text{kite}\}, \{\text{ dart}\}\}$. Unless the ETH fails, neither $\{H\}$-M-DELETION nor $\{H\}$-TM-DELETION can be solved in time $2^{o(\mathrm{tw} \log \mathrm{tw})} \cdot n^{O(1)}$.
## 2:8 A Complexity Dichotomy for Hitting Small Planar Minors

In the following we focus on the proof of Theorem 3 and Theorem 5. Theorem 4 can be proved by using the same reductions as for Theorem 3 by just replacing “minor” by “topological minor” and “-M-DELETION” by “-TM-DELETION”. Note that this holds when $H \in Q$ but not when $H \in \mathcal{R}$.

We first provide in Section 4.1 a general framework that will be used for every $H \in Q \cup \mathcal{R}$ and the graphs $H$ listed in Theorem 5, and then we explain how to modify this framework for each specific $H$. Namely, in Section 4.2 we deal with $P_5$ and in Section 4.3 with the stars. The other cases can be found in the full version of this article. All these proofs for particular graphs are quite similar and follow the same structure, but we need different gadgets and slight changes in the analysis to deal with each of the graphs $H$.

### 4.1 The general construction

In order to prove Theorems 3 and 5, we present several reductions from $k \times k$ PERMUTATION INDEPENDENT SET, introduced by Lokshtanov et al. [14].

**$k \times k$ PERMUTATION INDEPENDENT SET**

**Input:** An integer $k$ and a graph $G$ with vertex set $[1, k] \times [1, k]$.

**Parameter:** $k$.

**Output:** Is there an independent set of size $k$ in $G$ with exactly one element from each row and one element from each column?

**► Theorem 6 (Lokshtanov et al. [14]).** The $k \times k$ PERMUTATION INDEPENDENT SET problem cannot be solved in time $2^{o(k \log k)}$ unless the ETH fails.

The general construction that we proceed to present only depends on the number of vertices of $H$. Let $H \in Q \cup \mathcal{R} \cup \{\{cricket\}, \{px\}, \{butterfly\}, \{co-banner\}, \{bull\}, \{kite\}, \{ dart \}\}$ and let $(G, k)$ be an instance of $k \times k$ PERMUTATION INDEPENDENT SET. As we are asking for an independent set that contains exactly one vertex in each row, we will assume w.l.o.g. that, for each $(i, j), (i, j') \in V(G), \{(i, j), (i, j')\} \in E(G)$. Let $n = |V(G)|$ and $m = |E(G)|$. We proceed to construct a graph $F$ that displays the encoding of the $m$ subgraphs of $G$ consisting of exactly one edge. This is done in such a way that each edge is encoded exactly once. Moreover, these encodings are arranged in a cyclic way separated by gadgets ensuring the consistency of the selected solution.

Namely, we first define the graph $K = K_{h-1}$ where $h = |V(H)|$. For each $e \in E(G)$, and each $(i, j) \in [1, k]^2$, we define the graph $B_{i,j}^e$ to be the disjoint union of two copies of $K$ and two new vertices $a_{i,j}^e$ and $b_{i,j}^e$. Informally, every graph $B_{i,j}^e, e \in E(G)$, plays the same role and corresponds to the vertex $(i, j) \in V(G)$. For each $e \in E(G)$ and each $j \in [1, k]$, we define the graph $C_j^e$ obtained from the disjoint union of every $B_{i,j}^e, i \in [1, k]$, such that two graphs $B_{i_1,j}^e$ and $B_{i_2,j}^e, i_1 \neq i_2$, are complete to each other, i.e., for every $i_1 \neq i_2$, if $v_1 \in V(B_{i_1,j}^e)$ and $v_2 \in V(B_{i_2,j}^e)$, then $\{v_1, v_2\} \in E(C_j^e)$. Informally, every graph $C_j^e, e \in E(G)$, plays the same role and corresponds to the column $j$ of $G$.

For every $e \in E(G)$, we also define the graph $D^e$ obtained from the disjoint union of every $C_j^e, j \in [1, k]$, by adding, if $e = \{(i, j), (i', j')\}$, every edge $\{v_1, v_2\}$ such that $v_1 \in V(B_{i,j}^e)$ and $v_2 \in V(B_{i',j'}^e)$. The graph $D^e$ is depicted in Figure 2. Informally, the graph $D^e, e \in E(G)$, encodes the edge $e$ of the graph $G$.

For every $e \in E(G)$, we also define $J^e$ such that $V(J^e) = \{c_j^e | j \in [1, k]\} \cup \{r_i^e | i \in [1, k]\}$ is a set of new vertices and $E(J^e) = \emptyset$. The graphs $J^e, e \in E(G)$, are the separators that will ensure the consistency of the selected solution.

Finally, the graph $F$ is obtained from the disjoint union of every $D^e, e \in E(G)$, and every $J^e, e \in E(G)$, by adding the following edges, for a given fixed cyclic permutation
In the following we focus on the proof of Theorem 3 and Theorem 5. Theorem 4 can be proved by using the same reductions as for Theorem 3 by just replacing “minor” by “topological minor” and “-M-DELETION” by “-TM-DELETION”. Note that this holds when $H \in \mathcal{Q}$ but not when $H \in \mathcal{R}$.

We first provide in Section 4.1 a general framework that will be used for every $H \in \mathcal{Q} \cup \mathcal{R}$ and the graphs $H$ listed in Theorem 5, and then we explain how to modify this framework for each specific $H$. Namely, in Section 4.2 we deal with $P_5$ and in Section 4.3 with the stars. The other cases can be found in the full version of this article. All these proofs for particular graphs are quite similar and follow the same structure, but we need different gadgets and slight changes in the analysis to deal with each of the graphs $H$.

## 4.1 The general construction

In order to prove Theorems 3 and 5, we present several reductions from $k \times k$ PERMUTATION INDEPENDENT SET, introduced by Lokshtanov et al. [14].

### $k \times k$ PERMUTATION INDEPENDENT SET

**Input:** An integer $k$ and a graph $G$ with vertex set $[1, k] \times [1, k]$.

**Parameter:** $k$.

**Output:** Is there an independent set of size $k$ in $G$ with exactly one element from each row and one element from each column?

**► Theorem 6 (Lokshtanov et al. [14]).** The $k \times k$ PERMUTATION INDEPENDENT SET problem cannot be solved in time $2^{o(k \log k)}$ unless the ETH fails.

The general construction that we proceed to present only depends on the number of vertices of $H$. Let $H \in \mathcal{Q} \cup \mathcal{R} \cup \{\{cricket\}, \{px\}, \{butterfly\}, \{co-banner\}, \{bull\}, \{kite\}, \{ dart \}\}$ and let $(G, k)$ be an instance of $k \times k$ PERMUTATION INDEPENDENT SET. As we are asking for an independent set that contains exactly one vertex in each row, we will assume w.l.o.g. that, for each $(i, j), (i, j') \in V(G), \{(i, j), (i, j')\} \in E(G)$. Let $n = |V(G)|$ and $m = |E(G)|$. We proceed to construct a graph $F$ that displays the encoding of the $m$ subgraphs of $G$ consisting of exactly one edge. This is done in such a way that each edge is encoded exactly once. Moreover, these encodings are arranged in a cyclic way separated by gadgets ensuring the consistency of the selected solution.

Namely, we first define the graph $K = K_{h-1}$ where $h = |V(H)|$. For each $e \in E(G)$, and each $(i, j) \in [1, k]^2$, we define the graph $B_{i,j}^e$ to be the disjoint union of two copies of $K$ and two new vertices $a_{i,j}^e$ and $b_{i,j}^e$. Informally, every graph $B_{i,j}^e, e \in E(G)$, plays the same role and corresponds to the vertex $(i, j) \in V(G)$. For each $e \in E(G)$ and each $j \in [1, k]$, we define the graph $C_j^e$ obtained from the disjoint union of every $B_{i,j}^e, i \in [1, k]$, such that two graphs $B_{i_1,j}^e$ and $B_{i_2,j}^e, i_1 \neq i_2$, are complete to each other, i.e., for every $i_1 \neq i_2$, if $v_1 \in V(B_{i_1,j}^e)$ and $v_2 \in V(B_{i_2,j}^e)$, then $\{v_1, v_2\} \in E(C_j^e)$. Informally, every graph $C_j^e, e \in E(G)$, plays the same role and corresponds to the column $j$ of $G$.

For every $e \in E(G)$, we also define the graph $D^e$ obtained from the disjoint union of every $C_j^e, j \in [1, k]$, by adding, if $e = \{(i, j), (i', j')\}$, every edge $\{v_1, v_2\}$ such that $v_1 \in V(B_{i,j}^e)$ and $v_2 \in V(B_{i',j'}^e)$. The graph $D^e$ is depicted in Figure 2. Informally, the graph $D^e, e \in E(G)$, encodes the edge $e$ of the graph $G$.

For every $e \in E(G)$, we also define $J^e$ such that $V(J^e) = \{c_j^e | j \in [1, k]\} \cup \{r_i^e | i \in [1, k]\}$ is a set of new vertices and $E(J^e) = \emptyset$. The graphs $J^e, e \in E(G)$, are the separators that will ensure the consistency of the selected solution.

Finally, the graph $F$ is obtained from the disjoint union of every $D^e, e \in E(G)$, and every $J^e, e \in E(G)$, by adding the following edges, for a given fixed cyclic permutation
<figure><img src="image_19.png" /><figcaption>Figure 2 The graph $D^e$ for $e = \{(1, 1), (2, 2)\} \in E(G)$ where $k = 3$. A bold edge means that two graphs $B$ are connected in a complete bipartite way.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 3 The shape of the framework graph $F$ assuming that $k = 3$, $G$ contains only the three edges $e_1, e_2$, and $e_3$, and $\sigma$ is the cyclic permutation $(e_1, e_2, e_3)$.</figcaption></figure>

$\sigma$ of the elements of $E(G)$: for each $e \in E(G)$ and each $i, j \in [1, k]$, we add the edges $\{a_{i,j}^e, r_i^e\}$, $\{r_i^e, b_{i,j}^{\sigma^{-1}(e)}\}$, $\{b_{i,j}^{\sigma^{-1}(e)}, c_j^e\}$, and $\{c_j^e, a_{i,j}\}$ to $E(F)$. This concludes the definition of the framework graph $F$, which is depicted in Figure 3 (a similar figure appears in [4]). The pair $(F, \ell := 2h(k-1)km)$ is called the *H-framework* of $(G, k)$. For convenience, we always assume that we know the permutation $\sigma$ linked to the graph $F$.

Let us now discuss about the treewidth of $F$. First note that for each $e \in E(G)$, the set $V(J^e) \cup V(J^{\sigma(e)})$ disconnects the vertex set $V(D^e)$ from the remaining part of $F$. Moreover, if $e = \{(i, j), (i', j')\}$, then the bags $V(C_1^e) \cup V(B_{i,j}^e) \cup V(B_{i',j'}^e)$, $V(C_2^e) \cup V(B_{i,j}^e) \cup V(B_{i',j'}^e), \dots, V(C_k^e) \cup V(B_{i,j}^e) \cup V(B_{i',j'}^e)$ form a path decomposition of $D^e$ of width $2h(k+2)-1$. Combining this decomposition with the circular shape of $F$ and the fact that $V(J^e) \cup V(J^{\sigma(e)})$ disconnects the vertex set $V(D^e)$ from the remaining part of $F$, we obtain that the treewidth (in fact, also the pathwidth) of $F$ is at most $6k+2h(k+2)-1$, and therefore $\text{tw}(F) = O(k)$.

For each graph $H$, we will consider $(F, \ell)$, the *H-framework* of $(G, k)$, and create another pair $(F_H, \ell)$, where $F_H$ is a graph obtained starting from $F$ by adding some vertices and edges. We will claim that there exists a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$ if and only if there exists a solution of $\{H\}$-M-DELETION on $(F_H, \ell)$. In order to do this, we will prove the two following properties for each graph $H$.

**Property 1.** Let $S$ be a solution of $\{H\}$-M-DELETION on $(F_H, \ell)$. For every $e \in E(G)$ and $j \in [1, k]$ such that $|V(C_j^e) \setminus S|$ is maximized, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S \subseteq V(B_{i,j}^e)$.

The above property states that for each column $C_j^e$, $j \in [1, k]$ and $e \in E(G)$, containing a minimum number of vertices of the solution, the remaining vertices all belong to the same row.
<figure><img src="image_20.png" /><figcaption>Figure 2 The graph $D^e$ for $e = \{(1, 1), (2, 2)\} \in E(G)$ where $k = 3$. A bold edge means that two graphs $B$ are connected in a complete bipartite way.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Figure 3 The shape of the framework graph $F$ assuming that $k = 3$, $G$ contains only the three edges $e_1, e_2$, and $e_3$, and $\sigma$ is the cyclic permutation $(e_1, e_2, e_3)$.</figcaption></figure>

$\sigma$ of the elements of $E(G)$: for each $e \in E(G)$ and each $i, j \in [1, k]$, we add the edges $\{a_{i,j}^e, r_i^e\}$, $\{r_i^e, b_{i,j}^{\sigma^{-1}(e)}\}$, $\{b_{i,j}^{\sigma^{-1}(e)}, c_j^e\}$, and $\{c_j^e, a_{i,j}\}$ to $E(F)$. This concludes the definition of the framework graph $F$, which is depicted in Figure 3 (a similar figure appears in [4]). The pair $(F, \ell := 2h(k-1)km)$ is called the *H-framework* of $(G, k)$. For convenience, we always assume that we know the permutation $\sigma$ linked to the graph $F$.

Let us now discuss about the treewidth of $F$. First note that for each $e \in E(G)$, the set $V(J^e) \cup V(J^{\sigma(e)})$ disconnects the vertex set $V(D^e)$ from the remaining part of $F$. Moreover, if $e = \{(i, j), (i', j')\}$, then the bags $V(C_1^e) \cup V(B_{i,j}^e) \cup V(B_{i',j'}^e)$, $V(C_2^e) \cup V(B_{i,j}^e) \cup V(B_{i',j'}^e)$, ..., $V(C_k^e) \cup V(B_{i,j}^e) \cup V(B_{i',j'}^e)$ form a path decomposition of $D^e$ of width $2h(k+2)-1$. Combining this decomposition with the circular shape of $F$ and the fact that $V(J^e) \cup V(J^{\sigma(e)})$ disconnects the vertex set $V(D^e)$ from the remaining part of $F$, we obtain that the treewidth (in fact, also the pathwidth) of $F$ is at most $6k+2h(k+2)-1$, and therefore $\text{tw}(F) = O(k)$.

For each graph $H$, we will consider $(F, \ell)$, the *H-framework* of $(G, k)$, and create another pair $(F_H, \ell)$, where $F_H$ is a graph obtained starting from $F$ by adding some vertices and edges. We will claim that there exists a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$ if and only if there exists a solution of $\{H\}$-M-DELETION on $(F_H, \ell)$. In order to do this, we will prove the two following properties for each graph $H$.

**Property 1.** Let $S$ be a solution of $\{H\}$-M-DELETION on $(F_H, \ell)$. For every $e \in E(G)$ and $j \in [1, k]$ such that $|V(C_j^e) \setminus S|$ is maximized, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S \subseteq V(B_{i,j}^e)$.

The above property states that for each column $C_j^e$, $j \in [1, k]$ and $e \in E(G)$, containing a minimum number of vertices of the solution, the remaining vertices all belong to the same row.
2:10 A Complexity Dichotomy for Hitting Small Planar Minors

**► Property 2.** Let $S$ be a solution of $\{H\}$-M-DELETION on $(F_H, \ell)$. For every $e \in E(G)$, and for every $i, j \in [1, k]$, if $b_{i,j}^e \notin S$, then for every $i' \in [1, k] \setminus \{i\}$, we have $a_{i',j}^{\sigma(e)} \in S$.

The above property states that the choices of the vertices $a_{i,j}^e, b_{i,j}^e$ are consistent through
the whole framework graph $F_H$.

If we assume that Property 1 holds, we have the following lemma.

**► Lemma 7.** If Property 1 holds, then for every solution $S$ of $\{H\}$-M-DELETION on $(F_H, \ell = 2h(k-1)km)$, for every $e \in E(G)$, and for every $j \in [1, k]$, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S = V(B_{i,j}^e)$. Moreover, for every $e \in E(G)$, $V(J^e) \cap S = \emptyset$.

**Proof.** Assume that Property 1 holds and let $S$ be a solution of $\{H\}$-M-DELETION on $(F_H, 2h(k-1)km)$. By Property 1, we know that for every $e \in E(G)$, and for every $j \in [1, k]$, $|V(C_j^e) \cap S| \ge 2h(k-1)$. As there are exactly $m$ edges and $k$ columns, the budget is tight and we obtain that $|V(C_j^e) \cap S| = 2h(k-1)$. This implies that $|V(C_j^e) \setminus S| = 2h$, corresponding to the size of a set $B_{i,j}^e$ for some $i \in [1, k]$. The lemma follows. ◀

For each specific graph $H$, in order to prove Property 1 and Property 2, we will first
prove Property 1 and then use Lemma 7 in order to prove Property 2.

**► Lemma 8 (★).** If Property 1 and Property 2 hold and there exists a solution $S$ of $\{H\}$-M-DELETION on $(F_H, \ell = 2h(k-1)km)$, then, for any $e \in E(G)$, the set $T^e = \{(i,j) \mid V(B_{i,j}^e) \cap S = \emptyset\}$ is a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$.

Using the same argumentation, we obtain the same results for the topological minor
version.

**► Property 3.** Let $S$ be a solution of $\{H\}$-TM-DELETION on $(F_H, \ell)$. For every $e \in E(G)$ and $j \in [1, k]$ such that $|V(C_j^e) \setminus S|$ is maximized, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S \subseteq V(B_{i,j}^e)$.

**► Property 4.** Let $S$ be a solution of $\{H\}$-TM-DELETION on $(F_H, \ell)$. For every $e \in E(G)$, and for every $i, j \in [1, k]$, if $b_{i,j}^e \notin S$, then for every $i' \in [1, k] \setminus \{i\}$, we have $a_{i',j}^{\sigma(e)} \in S$.

**► Lemma 9.** If Property 3 holds, then for every solution $S$ of $\{H\}$-TM-DELETION on $(F_H, \ell = 2h(k-1)km)$, for every $e \in E(G)$, and for every $j \in [1, k]$, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S = V(B_{i,j}^e)$. Moreover, for every $e \in E(G)$, $V(J^e) \cap S = \emptyset$.

**► Lemma 10.** If Property 3 and Property 4 hold and there exists a solution $S$ of $\{H\}$-TM-DELETION on $(F_H, \ell = 2h(k-1)km)$, then, for any $e \in E(G)$, the set $T^e = \{(i,j) \mid V(B_{i,j}^e) \cap S = \emptyset\}$ is a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$.

Given a solution $T$ of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$, we define
$S_T = \{v \in V(F_H) \mid v \in B_{i,j}^e : e \in E(G), (i,j) \in [1, k]^2 \setminus T\}$. Note that $|S_T| = 2h(k-1)km$.

4.2 The reduction for $P_5$

We are ready to present the hardness reduction when $H = P_5$.

**► Theorem 11.** {$P_5$}-M-DELETION cannot be solved in time $2^{o(\mathrm{tw}\log \mathrm{tw})} \cdot n^{O(1)}$ unless the ETH fails.
2:10 A Complexity Dichotomy for Hitting Small Planar Minors

**► Property 2.** Let $S$ be a solution of $\{H\}$-M-DELETION on $(F_H, \ell)$. For every $e \in E(G)$, and for every $i, j \in [1, k]$, if $b_{i,j}^e \notin S$, then for every $i' \in [1, k] \setminus \{i\}$, we have $a_{i',j}^{\sigma(e)} \in S$.

The above property states that the choices of the vertices $a_{i,j}^e$, $b_{i,j}^e$ are consistent through
the whole framework graph $F_H$.

If we assume that Property 1 holds, we have the following lemma.

**► Lemma 7.** If Property 1 holds, then for every solution $S$ of $\{H\}$-M-DELETION on $(F_H, \ell = 2h(k-1)km)$, for every $e \in E(G)$, and for every $j \in [1, k]$, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S = V(B_{i,j}^e)$. Moreover, for every $e \in E(G)$, $V(J^e) \cap S = \emptyset$.

**Proof.** Assume that Property 1 holds and let $S$ be a solution of $\{H\}$-M-DELETION on $(F_H, 2h(k-1)km)$. By Property 1, we know that for every $e \in E(G)$, and for every $j \in [1, k]$, $|V(C_j^e) \cap S| \ge 2h(k-1)$. As there are exactly $m$ edges and $k$ columns, the budget is tight and we obtain that $|V(C_j^e) \cap S| = 2h(k-1)$. This implies that $|V(C_j^e) \setminus S| = 2h$, corresponding to the size of a set $B_{i,j}^e$ for some $i \in [1, k]$. The lemma follows. ◀

For each specific graph $H$, in order to prove Property 1 and Property 2, we will first
prove Property 1 and then use Lemma 7 in order to prove Property 2.

**► Lemma 8 (★).** If Property 1 and Property 2 hold and there exists a solution $S$ of $\{H\}$-M-DELETION on $(F_H, \ell = 2h(k-1)km)$, then, for any $e \in E(G)$, the set $T^e = \{(i,j) \mid V(B_{i,j}^e) \cap S = \emptyset\}$ is a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$.

Using the same argumentation, we obtain the same results for the topological minor
version.

**► Property 3.** Let $S$ be a solution of $\{H\}$-TM-DELETION on $(F_H, \ell)$. For every $e \in E(G)$ and $j \in [1, k]$ such that $|V(C_j^e) \setminus S|$ is maximized, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S \subseteq V(B_{i,j}^e)$.

**► Property 4.** Let $S$ be a solution of $\{H\}$-TM-DELETION on $(F_H, \ell)$. For every $e \in E(G)$, and for every $i, j \in [1, k]$, if $b_{i,j}^e \notin S$, then for every $i' \in [1, k] \setminus \{i\}$, we have $a_{i',j}^{\sigma(e)} \in S$.

**► Lemma 9.** If Property 3 holds, then for every solution $S$ of $\{H\}$-TM-DELETION on $(F_H, \ell = 2h(k-1)km)$, for every $e \in E(G)$, and for every $j \in [1, k]$, there exists $i \in [1, k]$ such that $V(C_j^e) \setminus S = V(B_{i,j}^e)$. Moreover, for every $e \in E(G)$, $V(J^e) \cap S = \emptyset$.

**► Lemma 10.** If Property 3 and Property 4 hold and there exists a solution $S$ of $\{H\}$-TM-DELETION on $(F_H, \ell = 2h(k-1)km)$, then, for any $e \in E(G)$, the set $T^e = \{(i,j) \mid V(B_{i,j}^e) \cap S = \emptyset\}$ is a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$.

Given a solution $T$ of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$, we define
$S_T = \{v \in V(F_H) \mid v \in B_{i,j}^e : e \in E(G), (i,j) \in [1, k]^2 \setminus T\}$. Note that $|S_T| = 2h(k-1)km$.

4.2 The reduction for $P_5$

We are ready to present the hardness reduction when $H = P_5$.

**► Theorem 11.** {$P_5$}-M-DELETION cannot be solved in time $2^{o(\mathrm{tw}\log \mathrm{tw})} \cdot n^{O(1)}$ unless the ETH fails.
**Proof.** Let $H = P_5$. Let $(G, k)$ be an instance of $k \times k$ PERMUTATION INDEPENDENT SET and let $(F, \ell)$ be the $H$-framework of $(G, k)$, as defined in Section 4.1. Note that $\ell = 10(k-1)km$. In this theorem, we define $F_{P_5} = F$ without any modification.

Let $T$ be a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$. One can check that every connected component of $F \setminus S_T$ is of size 4. Indeed, the connected components of $F \setminus S_T$ are either the copies of the graph $K$, which is of size 4, or the subgraph induced by the edges $\{a_{i,j}^e, r_i^e\}, \{r_i^e, b_{i,j}^{\sigma^{-1}(e)}\}, \{b_{i,j}^{\sigma^{-1}(e)}, c_j^e\}$, and $\{c_j^e, a_{i,j}^e\}$, for every $(i,j) \in T$. Thus $F \setminus S_T$ does not contain any $P_5$ as a minor and $S_T$ is a solution of $\{P_5\}$-M-DELETION of size $10(k-1)km$.

Assume now that $S$ is a solution of $\{P_5\}$-M-DELETION on $G$ of size $10(k-1)km$. We first prove that Property 1 holds. Let $e \in E(G)$ and $j \in [1, k]$ that maximize the size of $|V(C_j^e) \setminus S|$. By the pigeonhole principle, $|V(C_j^e) \setminus S| \ge 10$. Let $U_M$ be a set $V(B_{i,j}^e) \setminus S$, $i \in [1, k]$, with the maximum number of elements, and let $U_A = V(C_j^e) \setminus (S \cup U_M)$. If $|U_M| = 1$, then, as $|V(C_j^e) \setminus S| \ge 10$, we obtain that $K_{10}$ is a subgraph of $C_j^e$, contradicting the definition of $S$. If $|U_M| \ge 2$ and $|U_A| \ge 3$ or if $|U_M| \ge 3$ and $|U_A| \ge 2$, then $C_j^e$ contains a $K_{2,3}$ as a subgraph, also contradicting the definition of $S$. Finally if $|U_A| = 1$, we have that $|U_M| = 9$ and so, $C_j^e[U_M]$ contains a $K_4$ that, combined with the element of $U_A$, produces a $K_5$ that is forbidden by the definition of $S$. Thus $|U_A| = 0$ and Property 1 holds.

Let $e \in E(G)$ and let $i,j \in [1,k]$ such that $b_{i,j}^e \notin S$. Let $i' \in [1,k]$ such that $i \neq i'$. If $a_{i',j}^{\sigma(e)} \notin S$, then, as by Lemma 7 $S \cap V(J^{\sigma(e)}) = \emptyset$, we have that the path $r_{i'}^{\sigma(e)}, a_{i',j}^{\sigma(e)}, c_j^{\sigma(e)}, b_{i,j}^e, r_i^e$ is a subgraph of $F \setminus S$. Since, by definition of $S$, $F \setminus S$ does not contain $P_5$ as a minor, we have that $a_{i',j}^{\sigma(e)} \in S$. Thus Property 2 holds and the theorem follows. ◀

## 4.3 The reduction for $K_{1,s}$

The next theorem should be compared to the result in the full version stating that there exist single-exponential algorithms for hitting $K_{1,s}$ as a topological minor for every $s \ge 1$, while in Theorem 12 we prove that it is not the case for hitting $K_{1,s}$ as a minor, for every $s \ge 4$. It should be noted that the bound on $s$ of Theorem 12 is tight, as if $s \le 3$, then $\{K_{1,s}\}$-M-DELETION is exactly $\{K_{1,s}\}$-TM-DELETION, and therefore it can be solved in single-exponential time; see the full version for the details.

**Theorem 12.** *Given $s \ge 4$, $\{K_{1,s}\}$-M-DELETION cannot be solved in time $2^{o(\mathrm{tw}\log \mathrm{tw})} \cdot n^{O(1)}$ unless the ETH fails.*

**Proof.** Let $s \ge 4$ and let $H = K_{1,s}$. Let $(G, k)$ be an instance of $k \times k$ PERMUTATION INDEPENDENT SET and let $(F, \ell)$ be the $H$-framework of $(G, k)$, as defined in Section 4.1. Note that $\ell = 2(s+1)(k-1)km$. We construct the graph $F_H$ from $F$ by adding a pendant vertex to every vertex $a_{i,j}^e, e \in E(G)$, $i, j \in [1, k]$, and by adding $s-3$ pendant vertices to every vertex $b_{i,j}^e, e \in E(G)$, $i, j \in [1, k]$.

Let $T$ be a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$. Then every connected component of $F_H \setminus S_T$ is either a copy of the graph $K$, which is of size $s$, or the subgraph induced by $a_{i,j}^e, r_i^e, b_{i,j}^{\sigma^{-1}(e)}, c_j^e$, and the vertices that are pendant to $a_{i,j}^e$ and $b_{i,j}^{\sigma^{-1}(e)}$, for every $(i,j) \in T$. This latter subgraph, depicted in Figure 4, does not contain $K_{1,s}$ as a minor. Thus $F_H \setminus S_T$ does not contain any $K_{1,s}$ as a minor and $S_T$ is a solution of $\{K_{1,s}\}$-M-DELETION of size $2(s+1)(k-1)km$.

Assume now that $S$ is a solution of $\{K_{1,s}\}$-M-DELETION on $G$ of size $2(s+1)(k-1)km$. We first prove that Property 1 holds. Let $e \in E(G)$ and $j \in [1, k]$ that maximize the size of
**Proof.** Let $H = P_5$. Let $(G, k)$ be an instance of $k \times k$ PERMUTATION INDEPENDENT SET and let $(F, \ell)$ be the $H$-framework of $(G, k)$, as defined in Section 4.1. Note that $\ell = 10(k-1)km$. In this theorem, we define $F_{P_5} = F$ without any modification.

Let $T$ be a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$. One can check that every connected component of $F \setminus S_T$ is of size 4. Indeed, the connected components of $F \setminus S_T$ are either the copies of the graph $K$, which is of size 4, or the subgraph induced by the edges $\{a_{i,j}^e, r_i^e\}$, $\{r_i^e, b_{i,j}^{\sigma^{-1}(e)}\}$, $\{b_{i,j}^{\sigma^{-1}(e)}, c_j^e\}$, and $\{c_j^e, a_{i,j}^e\}$, for every $(i,j) \in T$. Thus $F \setminus S_T$ does not contain any $P_5$ as a minor and $S_T$ is a solution of $\{P_5\}$-M-DELETION of size $10(k-1)km$.

Assume now that $S$ is a solution of $\{P_5\}$-M-DELETION on $G$ of size $10(k-1)km$. We first prove that Property 1 holds. Let $e \in E(G)$ and $j \in [1, k]$ that maximize the size of $|V(C_j^e) \setminus S|$. By the pigeonhole principle, $|V(C_j^e) \setminus S| \ge 10$. Let $U_M$ be a set $V(B_{i,j}^e) \setminus S$, $i \in [1, k]$, with the maximum number of elements, and let $U_A = V(C_j^e) \setminus (S \cup U_M)$. If $|U_M| = 1$, then, as $|V(C_j^e) \setminus S| \ge 10$, we obtain that $K_{10}$ is a subgraph of $C_j^e$, contradicting the definition of $S$. If $|U_M| \ge 2$ and $|U_A| \ge 3$ or if $|U_M| \ge 3$ and $|U_A| \ge 2$, then $C_j^e$ contains a $K_{2,3}$ as a subgraph, also contradicting the definition of $S$. Finally if $|U_A| = 1$, we have that $|U_M| = 9$ and so, $C_j^e[U_M]$ contains a $K_4$ that, combined with the element of $U_A$, produces a $K_5$ that is forbidden by the definition of $S$. Thus $|U_A| = 0$ and Property 1 holds.

Let $e \in E(G)$ and let $i,j \in [1, k]$ such that $b_{i,j}^e \notin S$. Let $i' \in [1, k]$ such that $i \neq i'$. If $a_{i',j}^{\sigma(e)} \notin S$, then, as by Lemma 7 $S \cap V(J^{\sigma(e)}) = \emptyset$, we have that the path $r_{i'}^{\sigma(e)}, a_{i',j}^{\sigma(e)}, c_j^{\sigma(e)}, b_{i,j}^e, r_i^e$ is a subgraph of $F \setminus S$. Since, by definition of $S$, $F \setminus S$ does not contain $P_5$ as a minor, we have that $a_{i',j}^{\sigma(e)} \in S$. Thus Property 2 holds and the theorem follows. ◀

## 4.3 The reduction for $K_{1,s}$

The next theorem should be compared to the result in the full version stating that there exist single-exponential algorithms for hitting $K_{1,s}$ as a topological minor for every $s \ge 1$, while in Theorem 12 we prove that it is not the case for hitting $K_{1,s}$ as a minor, for every $s \ge 4$. It should be noted that the bound on $s$ of Theorem 12 is tight, as if $s \le 3$, then $\{K_{1,s}\}$-M-DELETION is exactly $\{K_{1,s}\}$-TM-DELETION, and therefore it can be solved in single-exponential time; see the full version for the details.

**Theorem 12.** *Given $s \ge 4$, $\{K_{1,s}\}$-M-DELETION cannot be solved in time $2^{o(tw \log tw)} \cdot n^{O(1)}$ unless the ETH fails.*

**Proof.** Let $s \ge 4$ and let $H = K_{1,s}$. Let $(G, k)$ be an instance of $k \times k$ PERMUTATION INDEPENDENT SET and let $(F, \ell)$ be the $H$-framework of $(G, k)$, as defined in Section 4.1. Note that $\ell = 2(s+1)(k-1)km$. We construct the graph $F_H$ from $F$ by adding a pendant vertex to every vertex $a_{i,j}^e$, $e \in E(G)$, $i, j \in [1, k]$, and by adding $s-3$ pendant vertices to every vertex $b_{i,j}^e$, $e \in E(G)$, $i, j \in [1, k]$.

Let $T$ be a solution of $k \times k$ PERMUTATION INDEPENDENT SET on $(G, k)$. Then every connected component of $F_H \setminus S_T$ is either a copy of the graph $K$, which is of size $s$, or the subgraph induced by $a_{i,j}^e, r_i^e, b_{i,j}^{\sigma^{-1}(e)}, c_j^e$, and the vertices that are pendant to $a_{i,j}^e$ and $b_{i,j}^{\sigma^{-1}(e)}$, for every $(i,j) \in T$. This latter subgraph, depicted in Figure 4, does not contain $K_{1,s}$ as a minor. Thus $F_H \setminus S_T$ does not contain any $K_{1,s}$ as a minor and $S_T$ is a solution of $\{K_{1,s}\}$-M-DELETION of size $2(s+1)(k-1)km$.

Assume now that $S$ is a solution of $\{K_{1,s}\}$-M-DELETION on $G$ of size $2(s+1)(k-1)km$. We first prove that Property 1 holds. Let $e \in E(G)$ and $j \in [1, k]$ that maximize the size of
<figure><img src="image_21.png" /><figcaption>Figure 4 A connected component of $F_H \setminus S$ that is not a copy of $K$, with $s=6$.</figcaption></figure>

$|V(C_j^e) \setminus S|$. By the pigeonhole principle, $|V(C_j^e) \setminus S| \ge 2(s+1)$. Let $U_M$ be a set $V(B_{i,j}^e) \setminus S$, $i \in [1, k]$, with the maximum number of elements, and let $U_A = V(C_j^e) \setminus (S \cup U_M)$. If $1 \le |U_M| < s$, then $|U_A| \ge s$ and $K_{1,s}$ is a subgraph of $C_j^e$, contradicting the definition of $S$. If $|U_M| \ge s$ and $|U_A| \ge 1$, then again $K_{1,s}$ is a subgraph of $C_j^e$, contradicting again the definition of $S$. Thus $|U_A| = 0$ and Property 1 holds.

Let $e \in E(G)$ and let $i,j \in [1,k]$ such that $b_{i,j}^e \notin S$. Let $i' \in [1,k]$ such that $i \neq i'$. If $a_{i',j}^{\sigma(e)} \notin S$, then, as by Lemma 7 it holds that $S \cap V(J^{\sigma(e)}) = \emptyset$, we have that the path $r_{i'}^{\sigma(e)}$, $a_{i',j}^{\sigma(e)}$, $c_j^{\sigma(e)}$, $b_{i,j}^e$, $r_i^e$ combined with the vertex pendant to $a_{i',j}^{\sigma(e)}$ and the $s-3$ vertices pendant to $b_{i,j}^e$ is a subgraph of $F_H \setminus S$ and $K_{1,s}$ is a minor of it. As, by definition of $S$, $F_H \setminus S$ does not contains $K_{1,s}$ as a minor, we have that $a_{i',j}^{\sigma(e)} \in S$. Thus Property 2 holds and the theorem follows. ◀

5 Conclusions and further research

The ultimate goal in this line of research is to establish the *tight* complexity of {$H$}-M-DELETION and {$H$}-TM-DELETION for any graph $H$, but we are still very far from it. In particular, we do not know whether there exists some $H$ for which a double-exponential lower bound can be proved. Very recently, Kociumaka and Pilipczuk [13] studied the problem of deleting a minimum number of vertices to obtain a graph of Euler genus at most $g$, and presented an algorithm running in time $2^{O_g(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$. Generalizing their technique to $H$-minor-free graphs (which would correspond to the general {$H$}-M-DELETION problem) seems quite challenging, as this would involve a huge amount of technical details.

We managed to classify the complexity of {$H$}-M-DELETION when $H$ is a connected planar graph on at most 5 vertices (cf. Figure 1). While we consider this dichotomy a significant result, most of the algorithms and the reductions are ad hoc, and therefore our approach does not seem to be easily applicable for dealing with larger graphs $H$. The case where $H$ is planar and connected is already very interesting, since the results in [1] imply that {$H$}-M-DELETION cannot be solved in time $2^{O(\text{tw})} \cdot n^{O(1)}$ under the ETH and can be solved in time $2^{O(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$. Thus, it makes sense to guess that, in this case, the complexity of {$H$}-M-DELETION is either $2^{\Theta(\text{tw})} \cdot n^{O(1)}$ or $2^{\Theta(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$, as it happens if $|V(H)| \le 5$. We conjecture that for every connected simple planar graph $H$ with $|V(H)| \ge 6$, the latter case holds. In fact, we conjecture the following property, which is easily seen to imply the previous conjecture: if $H$ and $H'$ are graphs such that $H \preceq_m H'$ and {$H$}-M-DELETION is not solvable under the ETH in time $f(\text{tw}) \cdot n^{O(1)}$ for some function $f$, then {$H'$}-M-DELETION is not solvable under the ETH in time $f(\text{tw}) \cdot n^{O(1)}$ either. We think that the equivalent property for the topological minor version also holds. Note that for establishing a dichotomy for {$H$}-TM-DELETION when $H$ is a connected planar graph on at most 5 vertices, it remains to obtain algorithms in time $2^{O(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$ for the graphs in Figure 1 that have maximum degree 4, like the *gem* or the * dart*, as for those graphs [1, Theorem 6] cannot be applied.
<figure><img src="image_22.png" /><figcaption>Figure 4 A connected component of $F_H \setminus S$ that is not a copy of $K$, with $s=6$.</figcaption></figure>

$|V(C_j^e) \setminus S|$. By the pigeonhole principle, $|V(C_j^e) \setminus S| \ge 2(s+1)$. Let $U_M$ be a set $V(B_{i,j}^e) \setminus S$, $i \in [1, k]$, with the maximum number of elements, and let $U_A = V(C_j^e) \setminus (S \cup U_M)$. If $1 \le |U_M| < s$, then $|U_A| \ge s$ and $K_{1,s}$ is a subgraph of $C_j^e$, contradicting the definition of $S$. If $|U_M| \ge s$ and $|U_A| \ge 1$, then again $K_{1,s}$ is a subgraph of $C_j^e$, contradicting again the definition of $S$. Thus $|U_A| = 0$ and Property 1 holds.

Let $e \in E(G)$ and let $i,j \in [1,k]$ such that $b_{i,j}^e \notin S$. Let $i' \in [1,k]$ such that $i \neq i'$. If $a_{i',j}^{\sigma(e)} \notin S$, then, as by Lemma 7 it holds that $S \cap V(J^{\sigma(e)}) = \emptyset$, we have that the path $r_{i'}^{\sigma(e)}$, $a_{i',j}^{\sigma(e)}$, $c_j^{\sigma(e)}$, $b_{i,j}^e$, $r_i^e$ combined with the vertex pendant to $a_{i',j}^{\sigma(e)}$ and the $s-3$ vertices pendant to $b_{i,j}^e$ is a subgraph of $F_H \setminus S$ and $K_{1,s}$ is a minor of it. As, by definition of $S$, $F_H \setminus S$ does not contains $K_{1,s}$ as a minor, we have that $a_{i',j}^{\sigma(e)} \in S$. Thus Property 2 holds and the theorem follows. ◀

5 Conclusions and further research

The ultimate goal in this line of research is to establish the *tight* complexity of {$H$}-M-DELETION and {$H$}-TM-DELETION for any graph $H$, but we are still very far from it. In particular, we do not know whether there exists some $H$ for which a double-exponential lower bound can be proved. Very recently, Kociumaka and Pilipczuk [13] studied the problem of deleting a minimum number of vertices to obtain a graph of Euler genus at most $g$, and presented an algorithm running in time $2^{O_g(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$. Generalizing their technique to $H$-minor-free graphs (which would correspond to the general {$H$}-M-DELETION problem) seems quite challenging, as this would involve a huge amount of technical details.

We managed to classify the complexity of {$H$}-M-DELETION when $H$ is a connected planar graph on at most 5 vertices (cf. Figure 1). While we consider this dichotomy a significant result, most of the algorithms and the reductions are ad hoc, and therefore our approach does not seem to be easily applicable for dealing with larger graphs $H$. The case where $H$ is planar and connected is already very interesting, since the results in [1] imply that {$H$}-M-DELETION cannot be solved in time $2^{O(\text{tw})} \cdot n^{O(1)}$ under the ETH and can be solved in time $2^{O(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$. Thus, it makes sense to guess that, in this case, the complexity of {$H$}-M-DELETION is either $2^{\Theta(\text{tw})} \cdot n^{O(1)}$ or $2^{\Theta(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$, as it happens if $|V(H)| \le 5$. We conjecture that for every connected simple planar graph $H$ with $|V(H)| \ge 6$, the latter case holds. In fact, we conjecture the following property, which is easily seen to imply the previous conjecture: if $H$ and $H'$ are graphs such that $H \preceq_m H'$ and {$H$}-M-DELETION is not solvable under the ETH in time $f(\text{tw}) \cdot n^{O(1)}$ for some function $f$, then {$H'$}-M-DELETION is not solvable under the ETH in time $f(\text{tw}) \cdot n^{O(1)}$ either. We think that the equivalent property for the topological minor version also holds. Note that for establishing a dichotomy for {$H$}-TM-DELETION when $H$ is a connected planar graph on at most 5 vertices, it remains to obtain algorithms in time $2^{O(\text{tw}\cdot\log \text{tw})} \cdot n^{O(1)}$ for the graphs in Figure 1 that have maximum degree 4, like the *gem* or the * dart*, as for those graphs [1, Theorem 6] cannot be applied.
Finally, note that the only connected (simple) graph on at most 5 vertices missing in Figure 1 is $K_5$. We think that, using techniques similar as those developed in [11], $\{K_5\}$-M-DELETION is solvable in time $2^{O(\mathrm{tw}\cdot\log \mathrm{tw})} \cdot n^{O(1)}$, which would be tight.

References

1. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. In *Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC)*, volume 89 of *LIPIcs*, pages 4:1–4:12, 2017.

2. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Information and Computation*, 243:86–111, 2015.

3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A $c^k n$ 5-Approximation Algorithm for Treewidth. *SIAM Journal on Computing*, 45(2):317–378, 2016.

4. Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In *Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC)*, volume 89 of *LIPIcs*, pages 7:1–7:13, 2017.

5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

6. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In *Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)*, pages 150–159, 2011.

7. Reinhard Diestel. *Graph Theory*, volume 173. Springer-Verlag, 4th edition, 2010.

8. R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

9. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. *Journal of the ACM*, 63(4):29:1–29:60, 2016.

10. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? *Journal of Computer and System Sciences*, 63(4):512–530, 2001.

11. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A Near-Optimal Planarization Algorithm. In *Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 1802–1811, 2014.

12. T. Kloks. *Treewidth. Computations and Approximations*. Springer-Verlag LNCS, 1994.

13. Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. *CoRR*, abs/1706.04065, 2017. arXiv:1706.04065.

14. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly Superexponential Parameterized Problems. In *Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 760–776, 2011.

15. Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. *Discrete Applied Mathematics*, 231:211–216, 2017.
Finally, note that the only connected (simple) graph on at most 5 vertices missing in Figure 1 is $K_5$. We think that, using techniques similar as those developed in [11], $\{K_5\}$-M-DELETION is solvable in time $2^{O(\mathrm{tw}\cdot\log \mathrm{tw})} \cdot n^{O(1)}$, which would be tight.

References

1. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal Algorithms for Hitting (Topological) Minors on Graphs of Bounded Treewidth. In *Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC)*, volume 89 of *LIPIcs*, pages 4:1–4:12, 2017.

2. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Information and Computation*, 243:86–111, 2015.

3. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A $c^k n$ 5-Approximation Algorithm for Treewidth. *SIAM Journal on Computing*, 45(2):317–378, 2016.

4. Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In *Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC)*, volume 89 of *LIPIcs*, pages 7:1–7:13, 2017.

5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

6. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In *Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)*, pages 150–159, 2011.

7. Reinhard Diestel. *Graph Theory*, volume 173. Springer-Verlag, 4th edition, 2010.

8. R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

9. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. *Journal of the ACM*, 63(4):29:1–29:60, 2016.

10. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? *Journal of Computer and System Sciences*, 63(4):512–530, 2001.

11. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A Near-Optimal Planarization Algorithm. In *Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 1802–1811, 2014.

12. T. Kloks. *Treewidth. Computations and Approximations*. Springer-Verlag LNCS, 1994.

13. Tomasz Kociumaka and Marcin Pilipczuk. Deleting vertices to graphs of bounded genus. *CoRR*, abs/1706.04065, 2017. arXiv:1706.04065.

14. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly Superexponential Parameterized Problems. In *Proc. of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 760–776, 2011.

15. Marcin Pilipczuk. A tight lower bound for Vertex Planarization on graphs of bounded treewidth. *Discrete Applied Mathematics*, 231:211–216, 2017.
<figure><img src="image_22.png" /></figure>
<figure><img src="image_23.png" /></figure>
# Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Bas A. M. van Geffen

University of Oxford
bas.vangeffen@kellogg.ox.ac.uk

Bart M. P. Jansen<fnref n="1" />

Eindhoven University of Technology
b.m.p.jansen@tue.nl

https://orcid.org/0000-0001-8204-1268

Arnoud A. W. M. de Kroon

University of Oxford
noud.kroon@keble.ox.ac.uk

Rolf Morel

University of Oxford
rolf.morel@sjc.ox.ac.uk

## Abstract

Many combinatorial problems can be solved in time $O*(c^{tw})$ on graphs of treewidth $tw$, for a problem-specific constant $c$. In several cases, matching upper and lower bounds on $c$ are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, INDEPENDENT SET cannot be solved in $O^*((2 - \varepsilon)^{tw})$ time, and DOMINATING SET cannot be solved in $O^*((3 - \varepsilon)^{tw})$ time. By designing a new crossover gadget, we extend these lower bounds even to planar graphs of bounded cutwidth or treewidth. Hence planarity does not help when solving INDEPENDENT SET or DOMINATING SET on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently.

**2012 ACM Subject Classification** Theory of computation → Graph algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** planarization, dominating set, cutwidth, lower bounds, strong exponential time hypothesis

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.3

**Related Version** A full version of the paper is available on arXiv [16], https://arxiv.org/abs/1806.10513.

<figure><img src="image_23.png" /></figure>

<footnote n="1">¹ Supported by NWO Gravitation grant “Networks” and NWO Veni grant “Frontiers in Parameterized Preprocessing”.</footnote>
# Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Bas A. M. van Geffen

University of Oxford
bas.vangeffen@kellogg.ox.ac.uk

Bart M. P. Jansen<fnref n="1" />

Eindhoven University of Technology
b.m.p.jansen@tue.nl

https://orcid.org/0000-0001-8204-1268

Arnoud A. W. M. de Kroon

University of Oxford
noud.kroon@keble.ox.ac.uk

Rolf Morel

University of Oxford
rolf.morel@sjc.ox.ac.uk

## Abstract

Many combinatorial problems can be solved in time $O*(c^{tw})$ on graphs of treewidth $tw$, for a problem-specific constant $c$. In several cases, matching upper and lower bounds on $c$ are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, INDEPENDENT SET cannot be solved in $O^*((2 - \varepsilon)^{tw})$ time, and DOMINATING SET cannot be solved in $O^*((3 - \varepsilon)^{tw})$ time. By designing a new crossover gadget, we extend these lower bounds even to planar graphs of bounded cutwidth or treewidth. Hence planarity does not help when solving INDEPENDENT SET or DOMINATING SET on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently.

**2012 ACM Subject Classification** Theory of computation → Graph algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** planarization, dominating set, cutwidth, lower bounds, strong exponential time hypothesis

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.3

**Related Version** A full version of the paper is available on arXiv [16], https://arxiv.org/abs/1806.10513.

<figure><img src="image_24.png" /></figure>

<footnote n="1">¹ Supported by NWO Gravitation grant “Networks” and NWO Veni grant “Frontiers in Parameterized Preprocessing”.</footnote>
1 Introduction

Dynamic programming on graphs of bounded treewidth is a powerful tool in the algorithm
designer’s toolbox, which has many applications (cf. [5]) and is captured by several meta-
theorems [7, 25]. Through clever use of techniques such as Möbius transformation, fast
subset convolution [2, 28], cut & count [9], and representative sets [4, 8, 14], algorithms
were developed that can solve numerous combinatorial problems on graphs of treewidth *tw*
in $O^*(c^{tw})$ time, for a problem-specific constant $c$. In recent work [23], it was shown that under
the *Strong Exponential Time Hypothesis* (SETH, see [18, 19]), the base of the exponent $c$
achieved by the best-known algorithm is actually optimal for DOMINATING SET ($c=3$) and
INDEPENDENT SET ($c=2$), amongst others. This prompts the following questions:

1. Do faster algorithms exist for bounded-treewidth graphs that are *planar*?

2. Do faster algorithms exist for a more restrictive graph parameter, such as cutwidth?

It turns out that these questions are related, because the nature of cutwidth allows crossover
gadgets to be inserted to planarize a graph without increasing its width significantly.

Before going into our results, we briefly motivate these questions. There is a rich
bidimensionality theory (cf. [10]) of how the planarity of a graph can be exploited to obtain
better algorithms than in the nonplanar case, leading to what has been called the *square-root
phenomenon* [24]: in several settings, parameterized algorithms on planar graphs can be
faster by a square-root factor in the exponent, compared to their nonplanar counterparts.
Hence it may be tempting to believe that problems on bounded-width graphs can be solved
more efficiently when they are planar. Lokshtanov et al. [23, §9] explicitly ask whether their
SETH-based lower bounds continue to apply for planar graphs. The same problem is posed
by Baste and Sau [1, p. 3] in their investigation on the influence of planarity when solving
connectivity problems parameterized by treewidth. This motivates question 1.

When faced with lower bounds for the parameterization by treewidth, it is natural
to investigate whether these continue to hold for more restrictive graph parameters. We
work with the parameter cutwidth since it is one of the classic graph layout parameters
(cf. [11]) which takes larger values than treewidth [22], and has been the subject of frequent
study [17, 26, 27]. In their original work, Lokshtanov et al. [23] showed that their lower
bounds also hold for pathwidth instead of treewidth. However, the parameterization by
cutwidth has so far not been considered, which leads us to question 2. (See Section 2 for the
definition of cutwidth.)

**Our results.** We answer questions 1 and 2 for the problems INDEPENDENT SET and DOMINATING SET, which are formally defined in Section 2. Our conceptual contribution towards answering question 1 comes from the following insight: any graph $G$ can be drawn in the plane (generally with crossings) such that the graph $G'$ obtained by replacing each crossing by a vertex of degree four, does not have larger cutwidth than $G$. Hence the property of having bounded cutwidth can be preserved while planarizing the graph, which was independently<fnref n="2" /> discovered by Eppstein [13]. When we planarize by replacing each crossing by a planar crossover gadget $H$ instead of a single vertex, then we obtain $\text{ctw}(G') \le \text{ctw}(G) + \text{ctw}(H) + 4$ if the endpoints of the crossing edges each obtain at most one neighbor in the crossover gadget. This gives a means to reduce a problem instance on a general graph of bounded

<footnote n="2">² We learned of Eppstein’s result while a previous version of this work was under submission at a different venue; see Footnote 2 in [13]. Our previous manuscript, cited by Eppstein, was later split into two separate parts due to its excessive length. The present paper is one part, and [21] is the other.</footnote>
1 Introduction

Dynamic programming on graphs of bounded treewidth is a powerful tool in the algorithm
designer’s toolbox, which has many applications (cf. [5]) and is captured by several meta-
theorems [7, 25]. Through clever use of techniques such as Möbius transformation, fast
subset convolution [2, 28], cut & count [9], and representative sets [4, 8, 14], algorithms
were developed that can solve numerous combinatorial problems on graphs of treewidth *tw*
in $O^*(c^{tw})$ time, for a problem-specific constant $c$. In recent work [23], it was shown that under
the *Strong Exponential Time Hypothesis* (SETH, see [18, 19]), the base of the exponent $c$
achieved by the best-known algorithm is actually optimal for DOMINATING SET ($c=3$) and
INDEPENDENT SET ($c=2$), amongst others. This prompts the following questions:

1. Do faster algorithms exist for bounded-treewidth graphs that are *planar*?

2. Do faster algorithms exist for a more restrictive graph parameter, such as cutwidth?

It turns out that these questions are related, because the nature of cutwidth allows crossover
gadgets to be inserted to planarize a graph without increasing its width significantly.

Before going into our results, we briefly motivate these questions. There is a rich
bidimensionality theory (cf. [10]) of how the planarity of a graph can be exploited to obtain
better algorithms than in the nonplanar case, leading to what has been called the *square-root
phenomenon* [24]: in several settings, parameterized algorithms on planar graphs can be
faster by a square-root factor in the exponent, compared to their nonplanar counterparts.
Hence it may be tempting to believe that problems on bounded-width graphs can be solved
more efficiently when they are planar. Lokshtanov et al. [23, §9] explicitly ask whether their
SETH-based lower bounds continue to apply for planar graphs. The same problem is posed
by Baste and Sau [1, p. 3] in their investigation on the influence of planarity when solving
connectivity problems parameterized by treewidth. This motivates question 1.

When faced with lower bounds for the parameterization by treewidth, it is natural
to investigate whether these continue to hold for more restrictive graph parameters. We
work with the parameter cutwidth since it is one of the classic graph layout parameters
(cf. [11]) which takes larger values than treewidth [22], and has been the subject of frequent
study [17, 26, 27]. In their original work, Lokshtanov et al. [23] showed that their lower
bounds also hold for pathwidth instead of treewidth. However, the parameterization by
cutwidth has so far not been considered, which leads us to question 2. (See Section 2 for the
definition of cutwidth.)

**Our results.** We answer questions 1 and 2 for the problems INDEPENDENT SET and DOMINATING SET, which are formally defined in Section 2. Our conceptual contribution towards answering question 1 comes from the following insight: any graph $G$ can be drawn in the plane (generally with crossings) such that the graph $G'$ obtained by replacing each crossing by a vertex of degree four, does not have larger cutwidth than $G$. Hence the property of having bounded cutwidth can be preserved while planarizing the graph, which was independently<fnref n="2" /> discovered by Eppstein [13]. When we planarize by replacing each crossing by a planar crossover gadget $H$ instead of a single vertex, then we obtain $\text{ctw}(G') \le \text{ctw}(G) + \text{ctw}(H) + 4$ if the endpoints of the crossing edges each obtain at most one neighbor in the crossover gadget. This gives a means to reduce a problem instance on a general graph of bounded

<footnote n="2">² We learned of Eppstein’s result while a previous version of this work was under submission at a different venue; see Footnote 2 in [13]. Our previous manuscript, cited by Eppstein, was later split into two separate parts due to its excessive length. The present paper is one part, and [21] is the other.</footnote>
cutwidth to a planar graph of bounded cutwidth, if a suitable crossover gadget is available. The parameter cutwidth is special in this regard: one cannot planarize a drawing of $K_{3,n}$ while keeping the pathwidth or treewidth constant [12, 13].

For the INDEPENDENT SET problem, the crossover gadget developed by Garey, Johnson, and Stockmeyer [15] can be used in the process described above. Together with the observation that the SETH-based lower bound construction by Lokshtanov et al. [23] for the treewidth parameterization also works for the cutwidth parameterization, this yields our first result.<fnref n="3" />

**Theorem 1.** *Assuming SETH, there is no $\varepsilon > 0$ such that INDEPENDENT SET on a planar graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((2 - \varepsilon)^k)$.*

For the DOMINATING SET problem, more work is needed to obtain a lower bound for planar graphs of bounded cutwidth. While the lower bound construction of Lokshtanov et al. [23] also works for the parameter cutwidth after a minor tweak, no crossover gadget for the DOMINATING SET problem was known. Our main technical contribution therefore consists of the design of a crossover gadget for DOMINATING SET, which we believe to be of independent interest. Together with the framework above, this gives our second result.

**Theorem 2.** *Assuming SETH, there is no $\varepsilon > 0$ such that DOMINATING SET on a planar graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((3 - \varepsilon)^k)$.*

Since any linear ordering of cutwidth $k$ can be transformed into a tree decomposition of width at most $k$ in polynomial time (cf. [3, Theorem 47]), the lower bounds of Theorems 1 and 2 also apply to the parameterization by treewidth. Hence our work resolves the question raised by Lokshtanov et al. [23] and by Baste and Sau [1] whether the SETH-lower bounds for INDEPENDENT SET and DOMINATING SET parameterized by treewidth also apply for planar graphs.

**Organization.** In Section 2 we provide preliminaries. In Section 3 we present a general theorem for planarizing graphs of bounded cutwidth, using a crossover gadget. It leads to a proof of Theorem 1. In Section 4 we prove Theorem 2. Finally, we provide some conclusions in Section 5. Due to space restrictions, proofs for statements marked (★) have been deferred to the full version [16].

## 2 Preliminaries

We use $\mathbb{N}$ to denote the natural numbers, including 0. For a positive integer $n$ and a set $X$ we use $\binom{X}{n}$ to denote the collection of all subsets of $X$ of size $n$. The power set of $X$ is denoted $2^X$. The set $\{1, \dots, n\}$ is abbreviated as $[n]$. The $O^*$ notation suppresses polynomial factors in the input size $n$, such that $O^*(f(k))$ is shorthand for $O(f(k)n^{O(1)})$. All our logarithms have base two.

We consider finite, simple, and undirected graphs $G$, consisting of a vertex set $V(G)$ and edge set $E(G) \subseteq \binom{V(G)}{2}$. The neighbors of a vertex $v$ in $G$ are denoted $N_G(v)$. The closed neighborhood of $v$ is $N_G[v] := N_G(v) \cup \{v\}$. For a vertex set $S \subseteq V(G)$ the open neighborhood is $N_G(S) := \bigcup_{v \in S} N_G(v) \setminus S$ and the closed neighborhood is $N_G[S] := N_G(S) \cup S$. The subgraph of $G$ induced by a vertex subset $U \subseteq V(G)$ is denoted $G[U]$. The operation of identifying vertices $u$ and $v$ in a graph $G$ results in the graph $G'$ that is obtained from $G$ by replacing the two vertices $u$ and $v$ by a new vertex $w$ with $N_{G'}(w) = N_G(\{u, v\})$.

<footnote n="3">³ The analogous lower bound of $\Omega((2 - \varepsilon)^k)$ for solving INDEPENDENT SET on planar graphs of pathwidth $k$ was already observed by Jansen and Wulms [20], based on an elaborate ad-hoc argument.</footnote>
cutwidth to a planar graph of bounded cutwidth, if a suitable crossover gadget is available. The parameter cutwidth is special in this regard: one cannot planarize a drawing of $K_{3,n}$ while keeping the pathwidth or treewidth constant [12, 13].

For the INDEPENDENT SET problem, the crossover gadget developed by Garey, Johnson, and Stockmeyer [15] can be used in the process described above. Together with the observation that the SETH-based lower bound construction by Lokshtanov et al. [23] for the treewidth parameterization also works for the cutwidth parameterization, this yields our first result.<fnref n="3" />

**Theorem 1.** *Assuming SETH, there is no $\varepsilon > 0$ such that INDEPENDENT SET on a planar graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((2 - \varepsilon)^k)$.*

For the DOMINATING SET problem, more work is needed to obtain a lower bound for planar graphs of bounded cutwidth. While the lower bound construction of Lokshtanov et al. [23] also works for the parameter cutwidth after a minor tweak, no crossover gadget for the DOMINATING SET problem was known. Our main technical contribution therefore consists of the design of a crossover gadget for DOMINATING SET, which we believe to be of independent interest. Together with the framework above, this gives our second result.

**Theorem 2.** *Assuming SETH, there is no $\varepsilon > 0$ such that DOMINATING SET on a planar graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((3 - \varepsilon)^k)$.*

Since any linear ordering of cutwidth $k$ can be transformed into a tree decomposition of width at most $k$ in polynomial time (cf. [3, Theorem 47]), the lower bounds of Theorems 1 and 2 also apply to the parameterization by treewidth. Hence our work resolves the question raised by Lokshtanov et al. [23] and by Baste and Sau [1] whether the SETH-lower bounds for INDEPENDENT SET and DOMINATING SET parameterized by treewidth also apply for planar graphs.

**Organization.** In Section 2 we provide preliminaries. In Section 3 we present a general theorem for planarizing graphs of bounded cutwidth, using a crossover gadget. It leads to a proof of Theorem 1. In Section 4 we prove Theorem 2. Finally, we provide some conclusions in Section 5. Due to space restrictions, proofs for statements marked (★) have been deferred to the full version [16].

## 2 Preliminaries

We use $\mathbb{N}$ to denote the natural numbers, including 0. For a positive integer $n$ and a set $X$ we use $\binom{X}{n}$ to denote the collection of all subsets of $X$ of size $n$. The power set of $X$ is denoted $2^X$. The set $\{1, \dots, n\}$ is abbreviated as $[n]$. The $O^*$ notation suppresses polynomial factors in the input size $n$, such that $O^*(f(k))$ is shorthand for $O(f(k)n^{O(1)})$. All our logarithms have base two.

We consider finite, simple, and undirected graphs $G$, consisting of a vertex set $V(G)$ and edge set $E(G) \subseteq \binom{V(G)}{2}$. The neighbors of a vertex $v$ in $G$ are denoted $N_G(v)$. The closed neighborhood of $v$ is $N_G[v] := N_G(v) \cup \{v\}$. For a vertex set $S \subseteq V(G)$ the open neighborhood is $N_G(S) := \bigcup_{v \in S} N_G(v) \setminus S$ and the closed neighborhood is $N_G[S] := N_G(S) \cup S$. The subgraph of $G$ induced by a vertex subset $U \subseteq V(G)$ is denoted $G[U]$. The operation of identifying vertices $u$ and $v$ in a graph $G$ results in the graph $G'$ that is obtained from $G$ by replacing the two vertices $u$ and $v$ by a new vertex $w$ with $N_{G'}(w) = N_G(\{u, v\})$.

<footnote n="3">³ The analogous lower bound of $\Omega((2-\varepsilon)^k)$ for solving INDEPENDENT SET on planar graphs of pathwidth $k$ was already observed by Jansen and Wulms [20], based on an elaborate ad-hoc argument.</footnote>
3:4 Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

An *independent set* is a set of pairwise nonadjacent vertices. A *vertex cover* in a graph *G* is a set *S* ⊆ *V*(*G*) such that *S* contains at least one endpoint from every edge. A set *S* ⊆ *V*(*G*) *dominates* the vertices *N*<sub>*G*</sub>[*S*]. A *dominating set* is a vertex set *S* such that *N*<sub>*G*</sub>[*S*] = *V*(*G*). The associated decision problems ask, given a graph *G* and integer *t*, whether an independent set (dominating set) of size *t* exists in *G*. The size of a maximum independent set (resp. minimum dominating set) in *G* is denoted *OPT<sub>IS</sub>*(*G*) (resp. *OPT<sub>DS</sub>*(*G*)). The *q*-SAT problem asks whether a given Boolean formula, in conjunctive normal form with clauses of size at most *q*, has a satisfying assignment.

► **Strong Exponential Time Hypothesis ([18, 19]).** For every $\varepsilon > 0$, there is a constant $q$
such that $\text{q-SAT}$ on $n$ variables cannot be solved in time $O^*( (2 - \varepsilon)^n )$.

**Drawings.** A drawing of a graph $G$ is a function $\psi$ that assigns a unique point $\psi(v) \in \mathbb{R}^2$ to each vertex $v \in V(G)$, and a curve $\psi(e) \subseteq \mathbb{R}^2$ to each edge $e \in E(G)$, such that the following four conditions hold. (1) For $e = \{u, v\} \in E(G)$, the endpoints of $\psi(e)$ are exactly $\psi(u)$ and $\psi(v)$. (2) The interior of a curve $\psi(e)$ does not contain the image of any vertex. (3) No three curves representing edges intersect in a common point, except possibly at their endpoints. (4) The interiors of the curves $\psi(e), \psi(e')$ for distinct edges intersect in at most one point. If the interiors of all the curves representing edges are pairwise-disjoint, then we have a *planar drawing*. In this paper we combine (nonplanar) drawings with crossover gadgets to build planar drawings. A graph is *planar* if it admits a planar drawing.

**Cutwidth.** For an *n*-vertex graph *G*, a *linear layout* of *G* is a linear ordering of its vertex set, as given by a bijection $\pi: V(G) \rightarrow [n]$. The *cutwidth* of *G* with respect to the layout $\pi$ is:

$$
\mathrm{ctw}_{\pi}(G) = \max_{1 \le i < n} \left| \{ \{u, v\} \in E(G) \mid \pi(u) \le i \land \pi(v) > i \} \right|.
$$

The cutwidth ctw(*G*) of a graph *G* is the minimum cutwidth attained by any linear layout.
It is well-known that ctw(*G*) ≥ pw(*G*) ≥ tw(*G*), where the latter denote the pathwidth and
treewidth of *G*, respectively (cf. [3]).

3 Planarizing graphs while preserving cutwidth

In this section we show how to planarize a graph without blowing up its cutwidth. An intuitive
way to think about cutwidth is to consider the vertices as being placed on a horizontal line
in the order dictated by the layout π, with edges drawn as x-monotone curves. For any
position i we consider the gap between vertex π⁻¹(i) and π⁻¹(i + 1), and count the edges
that cross the gap by having one endpoint at position at most i and the other at position
after i. The cutwidth of a layout is the maximum number of edges crossing any single gap;
see Figure 1. The simple but useful fact on which our approach hinges is the following. If we
obtain G' by replacing a crossing in the drawing by a new vertex of degree four, and we let π'
be the left-to-right order of the vertices in the resulting drawing, then ctwπ(G) = ctwπ'(G').
Hence by repeating this procedure we can eliminate all crossings to obtain a planarized
version of G without increasing the cutwidth. To utilize this idea in reductions, we formalize
a version of this approach where we planarize the graph by inserting gadgets, rather than
simply replacing crossings by degree-four vertices.

**Definition 3.** A *crossover gadget* is a graph *H* with terminal vertices *u*, *u'*, *v*, *v'* such that:
1. there is a planar drawing *ψ* of *H* in which all terminals lie on the outer face, and
2. there is a closed curve intersecting the drawing *ψ* only in the terminals, which visits the terminals in the order *u*, *v*, *u'*, *v'*.
3:4 Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

An *independent set* is a set of pairwise nonadjacent vertices. A *vertex cover* in a graph *G* is a set *S* ⊆ *V*(*G*) such that *S* contains at least one endpoint from every edge. A set *S* ⊆ *V*(*G*) *dominates* the vertices *N*<sub>*G*</sub>[*S*]. A *dominating set* is a vertex set *S* such that *N*<sub>*G*</sub>[*S*] = *V*(*G*). The associated decision problems ask, given a graph *G* and integer *t*, whether an independent set (dominating set) of size *t* exists in *G*. The size of a maximum independent set (resp. minimum dominating set) in *G* is denoted *OPT<sub>IS</sub>*(*G*) (resp. *OPT<sub>DS</sub>*(*G*)). The *q*-SAT problem asks whether a given Boolean formula, in conjunctive normal form with clauses of size at most *q*, has a satisfying assignment.

► **Strong Exponential Time Hypothesis ([18, 19]).** For every $\varepsilon > 0$, there is a constant $q$
such that $\text{q-SAT}$ on $n$ variables cannot be solved in time $O^*(((2 - \varepsilon)^n))$.

**Drawings.** A drawing of a graph $G$ is a function $\psi$ that assigns a unique point $\psi(v) \in \mathbb{R}^2$ to each vertex $v \in V(G)$, and a curve $\psi(e) \subseteq \mathbb{R}^2$ to each edge $e \in E(G)$, such that the following four conditions hold. (1) For $e = \{u, v\} \in E(G)$, the endpoints of $\psi(e)$ are exactly $\psi(u)$ and $\psi(v)$. (2) The interior of a curve $\psi(e)$ does not contain the image of any vertex. (3) No three curves representing edges intersect in a common point, except possibly at their endpoints. (4) The interiors of the curves $\psi(e), \psi(e')$ for distinct edges intersect in at most one point. If the interiors of all the curves representing edges are pairwise-disjoint, then we have a *planar drawing*. In this paper we combine (nonplanar) drawings with crossover gadgets to build planar drawings. A graph is *planar* if it admits a planar drawing.

**Cutwidth.** For an *n*-vertex graph *G*, a *linear layout* of *G* is a linear ordering of its vertex set, as given by a bijection $\pi: V(G) \rightarrow [n]$. The *cutwidth* of *G* with respect to the layout $\pi$ is:

$$
\mathrm{ctw}_{\pi}(G) = \max_{1 \le i < n} \left| \{ \{u, v\} \in E(G) \mid \pi(u) \le i \land \pi(v) > i \} \right|.
$$

The cutwidth ctw(*G*) of a graph *G* is the minimum cutwidth attained by any linear layout.
It is well-known that ctw(*G*) ≥ pw(*G*) ≥ tw(*G*), where the latter denote the pathwidth and
treewidth of *G*, respectively (cf. [3]).

3 Planarizing graphs while preserving cutwidth

In this section we show how to planarize a graph without blowing up its cutwidth. An intuitive
way to think about cutwidth is to consider the vertices as being placed on a horizontal line
in the order dictated by the layout $\pi$, with edges drawn as $x$-monotone curves. For any
position $i$ we consider the gap between vertex $\pi^{-1}(i)$ and $\pi^{-1}(i+1)$, and count the edges
that cross the gap by having one endpoint at position at most $i$ and the other at position
after $i$. The cutwidth of a layout is the maximum number of edges crossing any single gap;
see Figure 1. The simple but useful fact on which our approach hinges is the following. If we
obtain $G'$ by replacing a crossing in the drawing by a new vertex of degree four, and we let $\pi'$
be the left-to-right order of the vertices in the resulting drawing, then $ctw_{\pi'}(G) = ctw_{\pi'}(G')$.
Hence by repeating this procedure we can eliminate all crossings to obtain a planarized
version of $G$ without increasing the cutwidth. To utilize this idea in reductions, we formalize
a version of this approach where we planarize the graph by inserting gadgets, rather than
simply replacing crossings by degree-four vertices.

**Definition 3.** A *crossover gadget* is a graph *H* with terminal vertices *u*, *u'*, *v*, *v'* such that:
1. there is a planar drawing *ψ* of *H* in which all terminals lie on the outer face, and
2. there is a closed curve intersecting the drawing *ψ* only in the terminals, which visits the terminals in the order *u*, *v*, *u'*, *v'*.
<figure><img src="image_24.png" /><figcaption>Figure 1 Top-left: a linear layout $\pi$ of a graph $G$ with $ctw_{\pi}(G) = 4$. The largest cutsize is attained after vertices 4 and 5. Bottom-left: after inserting vertices at the crossings to obtain $G'$ and extending $\pi$ to $\pi'$ based on the $x$-coordinates of the inserted vertices, we have $ctw_{\pi}(G) = ctw_{\pi'}(G')$. Top-right: enlarged view. Bottom-right: replacing a crossing by gadget $H$.</figcaption></figure>

**Definition 4.** Let $\{a, b\}$ and $\{c, d\}$ be disjoint edges of a graph $G$, and let $H$ be a crossover gadget. The operation of replacing $\{\{a, b\}, \{c, d\}\}$ by $H$ removes edges $\{a, b\}$ and $\{c, d\}$, inserts a new copy of the graph $H$, and inserts the edges $\{a, u\}$, $\{u', b\}$, $\{c, v\}$, $\{v', d\}$.

For a crossover gadget to be useful to planarize instances of a decision problem, a replacement should have a predictable effect on the answer. To formalize this, we say that a *decision problem* $\Pi$ *on graphs* is a decision problem whose input consists of a graph $G$ and integer $t$.

**Definition 5.** A crossover gadget $H$ is useful for a decision problem $\Pi$ on graphs if there exists an integer $c_{\Pi}$ such that the following holds. If $(G, t)$ is an instance of $\Pi$ containing disjoint edges $\{a, b\}$, $\{c, d\}$, and $G'$ is the result of replacing these edges by $H$, then $(G, t)$ is a YES-instance of $\Pi$ if and only if $(G', t + c_{\Pi})$ is a YES-instance of $\Pi$.

The following theorem proves that a useful crossover gadget can be used to efficiently planarize instances without blowing up their cutwidth.

**Theorem 6.** If $H$ is a crossover gadget that is useful for decision problem $\Pi$ on graphs, then there is a polynomial-time algorithm that, given an instance $(G, t)$ of $\Pi$ and a linear layout $\pi$ of $G$, outputs an instance $(G', t')$ and a linear layout $\pi'$ of $G'$ such that:

1. $G'$ is planar,

2. $ctw_{\pi'}(G') \le ctw_{\pi}(G) + ctw(H) + 4$, and

3. $(G, t)$ is a YES-instance of $\Pi$ if and only if $(G', t')$ is a YES-instance of $\Pi$.

*Proof.* Consider the crossover gadget $H$ for $\Pi$ with terminals $u, u, v, v'$. Let $\pi_H$ be a linear layout of $H$ of minimum cutwidth, which is hardcoded into the algorithm along with the integer $c_{\Pi}$ described in Definition 5.

Let $(G, t)$ be an instance of $\Pi$ with a linear layout $\pi$. We start by constructing a (nonplanar) drawing $\psi$ of $G$ with the following properties.

1. The vertices of $G$ are placed on the $x$-axis, in the order dictated by $\pi$.

2. The image of each edge of $G$ is a strictly $x$-monotone curve.

3. If the drawings of two edges intersect in their interior, then their endpoints are all distinct and the corresponding curves properly cross; they do not only touch.
<figure><img src="image_25.png" /><figcaption>Figure 1 Top-left: a linear layout $\pi$ of a graph $G$ with $ctw_{\pi}(G) = 4$. The largest cutsize is attained after vertices 4 and 5. Bottom-left: after inserting vertices at the crossings to obtain $G'$ and extending $\pi$ to $\pi'$ based on the $x$-coordinates of the inserted vertices, we have $ctw_{\pi}(G) = ctw_{\pi'}(G')$. Top-right: enlarged view. Bottom-right: replacing a crossing by gadget $H$.</figcaption></figure>

**Definition 4.** Let $\{a, b\}$ and $\{c, d\}$ be disjoint edges of a graph $G$, and let $H$ be a crossover gadget. The operation of replacing $\{\{a, b\}, \{c, d\}\}$ by $H$ removes edges $\{a, b\}$ and $\{c, d\}$, inserts a new copy of the graph $H$, and inserts the edges $\{a, u\}, \{u', b\}, \{c, v\}, \{v', d\}$.

For a crossover gadget to be useful to planarize instances of a decision problem, a replacement should have a predictable effect on the answer. To formalize this, we say that a *decision problem* $\Pi$ *on graphs* is a decision problem whose input consists of a graph $G$ and integer $t$.

**Definition 5.** A crossover gadget $H$ is useful for a decision problem $\Pi$ on graphs if there exists an integer $c_{\Pi}$ such that the following holds. If $(G, t)$ is an instance of $\Pi$ containing disjoint edges $\{a, b\}, \{c, d\}$, and $G'$ is the result of replacing these edges by $H$, then $(G, t)$ is a YES-instance of $\Pi$ if and only if $(G', t + c_{\Pi})$ is a YES-instance of $\Pi$.

The following theorem proves that a useful crossover gadget can be used to efficiently planarize instances without blowing up their cutwidth.

**Theorem 6.** If $H$ is a crossover gadget that is useful for decision problem $\Pi$ on graphs, then there is a polynomial-time algorithm that, given an instance $(G, t)$ of $\Pi$ and a linear layout $\pi$ of $G$, outputs an instance $(G', t')$ and a linear layout $\pi'$ of $G'$ such that:

1. $G'$ is planar,

2. $ctw_{\pi'}(G') \le ctw_{\pi}(G) + ctw(H) + 4$, and

3. $(G, t)$ is a YES-instance of $\Pi$ if and only if $(G', t')$ is a YES-instance of $\Pi$.

**Proof.** Consider the crossover gadget $H$ for $\Pi$ with terminals $u, u, v, v'$. Let $\pi_H$ be a linear layout of $H$ of minimum cutwidth, which is hardcoded into the algorithm along with the integer $c_{\Pi}$ described in Definition 5.

Let $(G, t)$ be an instance of $\Pi$ with a linear layout $\pi$. We start by constructing a (nonplanar) drawing $\psi$ of $G$ with the following properties.

1. The vertices of $G$ are placed on the $x$-axis, in the order dictated by $\pi$.

2. The image of each edge of $G$ is a strictly $x$-monotone curve.

3. If the drawings of two edges intersect in their interior, then their endpoints are all distinct and the corresponding curves properly cross; they do not only touch.
4. For each pair of edges, their drawings intersect in at most one point.

5. The x-coordinates of all crossings are distinct from each other, and from the x-coordinates of the vertices.

It is easy to see that such a drawing always exists and can be found in polynomial time; we omit the details as they are not interesting. Properties 1 and 2 together ensure that for any $i \in [|V(G)| - 1]$, the set of edges that cross the gap after vertex $\pi^{-1}(i)$ in the linear layout is exactly the set of edges intersected by a vertical line between $\pi^{-1}(i)$ and $\pi^{-1}(i+1)$, which therefore has size at most $\text{ctw}_{\pi}(G)$. We will use this property later.

The algorithm replaces the crossings one by one. If two edges $\{a, b\}$ and $\{c, d\}$ intersect in their interior, then their endpoints are all distinct by (3) and they properly cross. Hence we can replace these two edges by a copy of $H$ as in Definition 4. Since there is a planar drawing of $H$ with the terminals alternating along the outer face, after possibly swapping the labels of $a$ and $b$, and of $c$ and $d$, the drawing can be updated so that the crossing between $\{a, b\}$ and $\{c, d\}$ is eliminated. Since each of $a, b, c, d$ is made adjacent to exactly one vertex of $H$, the replacement can be done such that the remaining crossings are in exactly the same locations as before; see the right side of Figure 1. When inserting the crossover gadget, we scale it down sufficiently far that the following holds: all vertices and crossings that were originally on the left of the crossing between $\{a, b\}$ and $\{c, d\}$ lie to the left of all vertices that are inserted to replace this crossing; and all vertices and crossings that were on the right of the $\{\{a, b\}, \{c, d\}\}$ crossing, lie to the right of all vertices inserted for its replacement.

Since each pair of edges intersects at most once by (4), the number of crossings is $O(|V(G)|^2)$. Hence in polynomial time we can replace all crossings by copies of $H$ to arrive at a graph $G'$. If $\ell$ is the number of replaced crossings, then we set $t' := t + \ell \cdot c_{\Pi}$. By Definition 5 and transitivity it follows that $(G, t)$ is a YES-instance of $\Pi$ if and only if $(G', t')$ is a YES-instance. By construction, $G'$ is planar. It remains to define a linear layout of $G'$ and bound its cutwidth.

The layout $\pi'$ of $G'$ is defined as follows. Let the *elements* of the original drawing $\psi$ of $G$ consist of its vertices and its crossings. The elements of $\psi$ are linearly ordered by their x-coordinates, by (5). The linear layout $\pi'$ of $G'$ has one block per element of $\psi$, and these blocks are ordered according to the x-coordinates of the corresponding element. For elements that consist of a vertex $v$, the block simply consists of $v$. For elements that consist of a crossing $X$, the block consists of the vertices of the copy of $H$ that was inserted to replace $X$, in the order dictated by $\pi_H$. It is easy to see that $\pi'$ can be constructed in polynomial time.

We classify the edges of $G'$ into two types. We have *internal* edges, which are edges within an inserted copy of $H$, and we have *external edges* which connect two different copies of $H$, or which connect a vertex of $V(G) \cap V(G')$ to a copy of $H$. Using this classification we argue that for an arbitrary vertex $v^*$ of $G'$, the cut crossing the gap after vertex $v^*$ in $\pi'$ contains at most $\text{ctw}_{\pi}(G) + \text{ctw}(H) + 4$ edges. To do so, we distinguish two cases depending on whether $v^*$ is an original vertex from $G$, or was inserted as part of a copy of $H$.

**Claim 7.** If $v^* \in V(G) \cap V(G')$, then the size of the cut after $v^*$ in $\pi'$ is at most $\text{ctw}_{\pi}(G)$.

**Proof.** The layout $\pi'$ consists of blocks, and $v^* \in V(G) \cap V(G')$ is a block. So for each copy $C$ of a crossover gadget, the vertices of $C$ all appear on the same side of $v^*$ in the ordering. Hence no internal edge of $C$ crosses the cut after $v^*$, implying that no internal edge is in the cut. Each external edge crossing the cut is (a segment of) an edge of $G$ that is intersected by a vertical line after $v^*$ in the drawing $\psi$; see Figure 1. As such a line intersects at most $\text{ctw}_{\pi}(G)$ edges as observed above, the cut after $v^*$ has size at most $\text{ctw}_{\pi}(G)$. ∎
4. For each pair of edges, their drawings intersect in at most one point.

5. The x-coordinates of all crossings are distinct from each other, and from the x-coordinates of the vertices.

It is easy to see that such a drawing always exists and can be found in polynomial time; we omit the details as they are not interesting. Properties 1 and 2 together ensure that for any $i \in [|V(G)| - 1]$, the set of edges that cross the gap after vertex $\pi^{-1}(i)$ in the linear layout is exactly the set of edges intersected by a vertical line between $\pi^{-1}(i)$ and $\pi^{-1}(i+1)$, which therefore has size at most $\text{ctw}_{\pi}(G)$. We will use this property later.

The algorithm replaces the crossings one by one. If two edges $\{a, b\}$ and $\{c, d\}$ intersect in their interior, then their endpoints are all distinct by (3) and they properly cross. Hence we can replace these two edges by a copy of $H$ as in Definition 4. Since there is a planar drawing of $H$ with the terminals alternating along the outer face, after possibly swapping the labels of $a$ and $b$, and of $c$ and $d$, the drawing can be updated so that the crossing between $\{a, b\}$ and $\{c, d\}$ is eliminated. Since each of $a, b, c, d$ is made adjacent to exactly one vertex of $H$, the replacement can be done such that the remaining crossings are in exactly the same locations as before; see the right side of Figure 1. When inserting the crossover gadget, we scale it down sufficiently far that the following holds: all vertices and crossings that were originally on the left of the crossing between $\{a, b\}$ and $\{c, d\}$ lie to the left of all vertices that are inserted to replace this crossing; and all vertices and crossings that were on the right of the $\{\{a, b\}, \{c, d\}\}$ crossing, lie to the right of all vertices inserted for its replacement.

Since each pair of edges intersects at most once by (4), the number of crossings is $O(|V(G)|^2)$. Hence in polynomial time we can replace all crossings by copies of $H$ to arrive at a graph $G'$. If $\ell$ is the number of replaced crossings, then we set $t' := t + \ell \cdot c_{\Pi}$. By Definition 5 and transitivity it follows that $(G, t)$ is a YES-instance of $\Pi$ if and only if $(G', t')$ is a YES-instance. By construction, $G'$ is planar. It remains to define a linear layout of $G'$ and bound its cutwidth.

The layout $\pi'$ of $G'$ is defined as follows. Let the elements of the original drawing $\psi$ of $G$ consist of its vertices and its crossings. The elements of $\psi$ are linearly ordered by their x-coordinates, by (5). The linear layout $\pi'$ of $G'$ has one block per element of $\psi$, and these blocks are ordered according to the x-coordinates of the corresponding element. For elements that consist of a vertex $v$, the block simply consists of $v$. For elements that consist of a crossing $X$, the block consists of the vertices of the copy of $H$ that was inserted to replace $X$, in the order dictated by $\pi_H$. It is easy to see that $\pi'$ can be constructed in polynomial time.

We classify the edges of $G'$ into two types. We have *internal edges*, which are edges within an inserted copy of $H$, and we have *external edges* which connect two different copies of $H$, or which connect a vertex of $V(G) \cap V(G')$ to a copy of $H$. Using this classification we argue that for an arbitrary vertex $v^*$ of $G'$, the cut crossing the gap after vertex $v^*$ in $\pi'$ contains at most $\text{ctw}_{\pi}(G) + \text{ctw}(H) + 4$ edges. To do so, we distinguish two cases depending on whether $v^*$ is an original vertex from $G$, or was inserted as part of a copy of $H$.

**Claim 7.** If $v^* \in V(G) \cap V(G')$, then the size of the cut after $v^*$ in $\pi'$ is at most $\text{ctw}_{\pi}(G)$.

**Proof.** The layout $\pi'$ consists of blocks, and $v^* \in V(G) \cap V(G')$ is a block. So for each copy $C$ of a crossover gadget, the vertices of $C$ all appear on the same side of $v^*$ in the ordering. Hence no internal edge of $C$ crosses the cut after $v^*$, implying that no internal edge is in the cut. Each external edge crossing the cut is (a segment of) an edge of $G$ that is intersected by a vertical line after $v^*$ in the drawing $\psi$; see Figure 1. As such a line intersects at most $\text{ctw}_{\pi}(G)$ edges as observed above, the cut after $v^*$ has size at most $\text{ctw}_{\pi}(G)$. ∎
**Claim 8.** If $v^* \in V(G')$ is a vertex of a copy $C$ of a crossover gadget that was inserted to replace a crossing $X$, then the size of the cut after $v^*$ in $\pi'$ is at most $\text{ctw}_{\pi'}(G) + \text{ctw}(H) + 4$.

**Proof.** The number of internal edges in the cut after $v^*$ is at most $\text{ctw}(H)$, since the only internal edges in the cut all belong to the same copy $C$ that contains $v^*$ and we ordered them according to an optimal layout $\pi_H$. There are at most four external edges incident on a vertex of $C$, which contribute at most four to the cut. Finally, for each of the remaining external edges in the cut there is a unique edge of $G$ intersected by a vertical line through crossing $X$ in the drawing $\psi$. As at most $\text{ctw}_{\pi'}(G)$ edges are intersected by any vertical line, as observed above, it follows that the size of the cut is at most $\text{ctw}_{\pi'}(G) + \text{ctw}(H) + 4$. ▼

The two claims together show that any gap in the ordering $\pi'$ is crossed by at most $\text{ctw}_{\pi'}(G) + \text{ctw}(H) + 4$ edges, which bounds the cutwidth of $G'$ as required. ◀

Using Theorem 6 we can now elegantly prove Theorem 1 by combining two known results.

**Theorem 1.** *Assuming SETH, there is no $\varepsilon > 0$ such that INDEPENDENT SET on a planar graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((2 - \varepsilon)^k)$.*

**Proof.** First, we observe that the crossover gadget for VERTEX COVER due to Garey, Johnson, and Stockmeyer [15, Thm. 2.7] satisfies our conditions of a useful crossover gadget. Since an $n$-vertex graph has a vertex cover of size $k$ if and only if it has an independent set of size $n-k$, it also acts as a useful crossover gadget for INDEPENDENT SET with $c_{\pi} = 9$ (cf. [20, Proposition 20]). Second, we observe that by a different analysis of a construction due to Lokshtanov et al. [23], it follows that (assuming SETH) there is no $\varepsilon > 0$ such that INDEPENDENT SET on a graph $G$ with a linear layout of cutwidth $k$ can be solved in time $O^*((2 - \varepsilon)^k)$. We prove this in the full version [16]. By Theorem 6, if such a runtime could be achieved on planar graphs of a given cutwidth, it could be achieved for a general graph as well, since the insertion of crossover gadgets increases the cutwidth by only a constant. Hence Theorem 1 follows. ◀

## 4 Lower bound for dominating set on planar graphs of bounded cutwidth

In this section we prove a runtime lower bound for solving DOMINATING SET on planar graphs of bounded cutwidth. Our starting point is the insight that through a minor modification, the lower bound by Lokshtanov et al. [23] for the parameterization by pathwidth can be lifted to apply to the parameterization by cutwidth as well.

**Theorem 9 (★).** *Assuming SETH, there is no $\varepsilon > 0$ such that DOMINATING SET on a (nonplanar) graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((3 - \varepsilon)^k)$.*

Our contribution is to extend the lower bound of Theorem 9 to apply to planar graphs. Following the strategy outlined in Section 3, to achieve this it suffices to develop a useful crossover gadget for DOMINATING SET as per Definition 5. Since our crossover gadget is fairly complicated (it has more than 100 vertices), we describe its design in steps. The main idea is as follows. We first show that an edge in a DOMINATING SET instance can be replaced by a longer double-path structure, which contains several triangles. Then we show that when two triangles cross, we can replace their crossing by a suitable adaptation of the VERTEX COVER crossover gadget due to Garey, Johnson, and Stockmeyer [15, Thm. 2.7].
**Claim 8.** If $v^* \in V(G')$ is a vertex of a copy $C$ of a crossover gadget that was inserted to replace a crossing $X$, then the size of the cut after $v^*$ in $\pi'$ is at most $\text{ctw}_{\pi'}(G) + \text{ctw}(H) + 4$.

**Proof.** The number of internal edges in the cut after $v^*$ is at most $\text{ctw}(H)$, since the only internal edges in the cut all belong to the same copy $C$ that contains $v^*$ and we ordered them according to an optimal layout $\pi_H$. There are at most four external edges incident on a vertex of $C$, which contribute at most four to the cut. Finally, for each of the remaining external edges in the cut there is a unique edge of $G$ intersected by a vertical line through crossing $X$ in the drawing $\psi$. As at most $\text{ctw}_{\pi'}(G)$ edges are intersected by any vertical line, as observed above, it follows that the size of the cut is at most $\text{ctw}_{\pi'}(G) + \text{ctw}(H) + 4$. ∎

The two claims together show that any gap in the ordering $\pi'$ is crossed by at most $\text{ctw}_{\pi'}(G) + \text{ctw}(H) + 4$ edges, which bounds the cutwidth of $G'$ as required. ◀

Using Theorem 6 we can now elegantly prove Theorem 1 by combining two known results.

**Theorem 1.** *Assuming SETH, there is no $\varepsilon > 0$ such that INDEPENDENT SET on a planar graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((2 - \varepsilon)^k)$.*

**Proof.** First, we observe that the crossover gadget for VERTEX COVER due to Garey, Johnson, and Stockmeyer [15, Thm. 2.7] satisfies our conditions of a useful crossover gadget. Since an $n$-vertex graph has a vertex cover of size $k$ if and only if it has an independent set of size $n-k$, it also acts as a useful crossover gadget for INDEPENDENT SET with $c_{\pi} = 9$ (cf. [20, Proposition 20]). Second, we observe that by a different analysis of a construction due to Lokshtanov et al. [23], it follows that (assuming SETH) there is no $\varepsilon > 0$ such that INDEPENDENT SET on a graph $G$ with a linear layout of cutwidth $k$ can be solved in time $O^*((2 - \varepsilon)^k)$. We prove this in the full version [16]. By Theorem 6, if such a runtime could be achieved on planar graphs of a given cutwidth, it could be achieved for a general graph as well, since the insertion of crossover gadgets increases the cutwidth by only a constant. Hence Theorem 1 follows. ◀

## 4 Lower bound for dominating set on planar graphs of bounded cutwidth

In this section we prove a runtime lower bound for solving DOMINATING SET on planar graphs of bounded cutwidth. Our starting point is the insight that through a minor modification, the lower bound by Lokshtanov et al. [23] for the parameterization by pathwidth can be lifted to apply to the parameterization by cutwidth as well.

**Theorem 9 (★).** *Assuming SETH, there is no $\varepsilon > 0$ such that DOMINATING SET on a (nonplanar) graph $G$ given along with a linear layout of cutwidth $k$ can be solved in time $O^*((3 - \varepsilon)^k)$.*

Our contribution is to extend the lower bound of Theorem 9 to apply to planar graphs. Following the strategy outlined in Section 3, to achieve this it suffices to develop a useful crossover gadget for DOMINATING SET as per Definition 5. Since our crossover gadget is fairly complicated (it has more than 100 vertices), we describe its design in steps. The main idea is as follows. We first show that an edge in a DOMINATING SET instance can be replaced by a longer double-path structure, which contains several triangles. Then we show that when two triangles cross, we can replace their crossing by a suitable adaptation of the VERTEX COVER crossover gadget due to Garey, Johnson, and Stockmeyer [15, Thm. 2.7].
<figure><img src="image_25.png" /><figcaption>Figure 2 Overview of the method to eliminate an edge crossing in an instance of DOMINATING SET. Each edge is transformed into a double-path structure, to turn a single crossing edge into four crossing triangles (middle figure). Then each crossing triangle is replaced by a planar gadget (right figure). Some vertices have been omitted for readability. For each red edge {$u, v$}, there is a hidden degree-two vertex in the graph that forms a triangle with $u$ and $v$.</figcaption></figure>

This two-step approach is illustrated in Figure 2. We follow the same two steps in proving its correctness, starting with the insertion of the double-path structure.

**Lemma 10.** Let {$x, y$} be an edge in a graph $G$. If $G'$ is obtained from $G$ by replacing {$x, y$} by a double-path structure as shown in Figure 3, then $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 6$.

*Proof.* We prove equality by establishing matching upper- and lower bounds.

(≤ To show $\text{OPT}_{\text{DS}}(G') \le \text{OPT}_{\text{DS}}(G) + 6$, consider a minimum dominating set $S \subseteq V(G)$ of $G$. If $S \cap \{x, y\} = \emptyset$, or $S \cap \{x, y\} = \{x, y\}$, then the edge $\{x, y\}$ is not used to dominate vertex $x$ or $y$, and therefore $S \cup \{b_x, b_y, e_x, e_y, g_x, g_y\}$ is a dominating set of size $|S| + 6 = \text{OPT}_{\text{DS}}(G) + 6$ in graph $G'$; see Figure 3. If $S \cap \{x, y\} = \{x\}$, then $S \cup \{c_x, f_x, h_x, e_y, g_y, a_y\}$ is a dominating set of size $\text{OPT}_{\text{DS}}(G) + 6$ in $G'$: the vertex $a_y$ takes over the role of dominating $y$ after the direct edge $\{x, y\}$ is removed, while $a_x$ is dominated from $x$. Symmetrically, if $S \cap \{x, y\} = \{y\}$, then $S \cup \{c_y, f_y, h_y, e_x, g_x, a_x\}$ is a dominating set in $G'$ of size $\text{OPT}_{\text{DS}}(G) + 6$.

(≥ To show $\text{OPT}_{\text{DS}}(G') \ge \text{OPT}_{\text{DS}}(G) + 6$, we instead prove $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 6$. Consider a minimum dominating set $S' \subseteq V(G')$ of $G'$. Let $B$ be the vertices in the interior of the double-path structure that was inserted into $G'$ to replace edge $\{x, y\}$. If $|S' \cap B| \ge 7$, then $(S \setminus B) \cup \{x\}$ is a dominating set of size at most $|S'| - 6 \le \text{OPT}_{\text{DS}}(G') - 6$ in $G$, since $x$ dominates itself and $y$ using the edge $\{x, y\}$. We assume $|S' \cap B| \le 6$ in the remainder. Then we have $|S' \cap B| = 6$: the closed neighborhoods of the six vertices $\{b_x, b_y, t_x, t_y, t_x'', t_y''\}$ are contained entirely within $B$, and are pairwise disjoint. Hence these six vertices must be dominated by six distinct vertices from $B$. If $S' \cap \{a_x, a_y\} = \emptyset$ then the vertices $x$ and $y$ are not dominated from within the double-path structure, implying that $S' \setminus B$ is a dominating set in $G$ of size $|S'| - 6 \le \text{OPT}_{\text{DS}}(G') - 6$. It remains to consider the case that $S'$ contains $a_x$, or $a_y$, or both.

**Claim 11.** Let $B' \subseteq B$ be a set of size six that dominates the vertices $B \setminus \{a_x, a_y\}$. If $B'$ contains $a_x$, then $B'$ does not dominate $a_y$. Analogously, if $B'$ contains $a_y$ then it does not dominate $a_x$.

*Proof.* We prove that if $a_y \in B'$, then $B'$ does not dominate $a_x$. The other statement follows by symmetry. So assume for a contradiction that $B'$ contains $a_y$ and dominates $a_x$, which implies it contains $a_x$ or $b_x$. Since $B'$ dominates the interior of the double-path structure, it
<figure><img src="image_26.png" /><figcaption>■ **Figure 2** Overview of the method to eliminate an edge crossing in an instance of DOMINATING SET. Each edge is transformed into a double-path structure, to turn a single crossing edge into four crossing triangles (middle figure). Then each crossing triangle is replaced by a planar gadget (right figure). Some vertices have been omitted for readability. For each red edge {$u, v$}, there is a hidden degree-two vertex in the graph that forms a triangle with $u$ and $v$.</figcaption></figure>

This two-step approach is illustrated in Figure 2. We follow the same two steps in proving its correctness, starting with the insertion of the double-path structure.

**Lemma 10.** Let {$x, y$} be an edge in a graph $G$. If $G'$ is obtained from $G$ by replacing {$x, y$} by a double-path structure as shown in Figure 3, then $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 6$.

*Proof.* We prove equality by establishing matching upper- and lower bounds.

(≤ To show $\text{OPT}_{\text{DS}}(G') \le \text{OPT}_{\text{DS}}(G) + 6$, consider a minimum dominating set $S \subseteq V(G)$ of $G$. If $S \cap \{x, y\} = \emptyset$, or $S \cap \{x, y\} = \{x, y\}$, then the edge $\{x, y\}$ is not used to dominate vertex $x$ or $y$, and therefore $S \cup \{b_x, b_y, e_x, e_y, g_x, g_y\}$ is a dominating set of size $|S| + 6 = \text{OPT}_{\text{DS}}(G) + 6$ in graph $G'$; see Figure 3. If $S \cap \{x, y\} = \{x\}$, then $S \cup \{c_x, f_x, h_x, e_y, g_y, a_y\}$ is a dominating set of size $\text{OPT}_{\text{DS}}(G) + 6$ in $G'$: the vertex $a_y$ takes over the role of dominating $y$ after the direct edge $\{x, y\}$ is removed, while $a_x$ is dominated from $x$. Symmetrically, if $S \cap \{x, y\} = \{y\}$, then $S \cup \{c_y, f_y, h_y, e_x, g_x, a_x\}$ is a dominating set in $G'$ of size $\text{OPT}_{\text{DS}}(G) + 6$.

(≥ To show $\text{OPT}_{\text{DS}}(G') \ge \text{OPT}_{\text{DS}}(G) + 6$, we instead prove $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 6$. Consider a minimum dominating set $S' \subseteq V(G')$ of $G'$. Let $B$ be the vertices in the interior of the double-path structure that was inserted into $G'$ to replace edge $\{x, y\}$. If $|S' \cap B| \ge 7$, then $(S \setminus B) \cup \{x\}$ is a dominating set of size at most $|S'| - 6 \le \text{OPT}_{\text{DS}}(G') - 6$ in $G$, since $x$ dominates itself and $y$ using the edge $\{x, y\}$. We assume $|S' \cap B| \le 6$ in the remainder. Then we have $|S' \cap B| = 6$: the closed neighborhoods of the six vertices $\{b_x, b_y, t_x, t_y, t_x'', t_y''\}$ are contained entirely within $B$, and are pairwise disjoint. Hence these six vertices must be dominated by six distinct vertices from $B$. If $S' \cap \{a_x, a_y\} = \emptyset$ then the vertices $x$ and $y$ are not dominated from within the double-path structure, implying that $S' \setminus B$ is a dominating set in $G$ of size $|S'| - 6 \le \text{OPT}_{\text{DS}}(G') - 6$. It remains to consider the case that $S'$ contains $a_x$, or $a_y$, or both.

**Claim 11.** Let $B' \subseteq B$ be a set of size six that dominates the vertices $B \setminus \{a_x, a_y\}$. If $B'$ contains $a_x$, then $B'$ does not dominate $a_y$. Analogously, if $B'$ contains $a_y$ then it does not dominate $a_x$.

*Proof.* We prove that if $a_y \in B'$, then $B'$ does not dominate $a_x$. The other statement follows by symmetry. So assume for a contradiction that $B'$ contains $a_y$ and dominates $a_x$, which implies it contains $a_x$ or $b_x$. Since $B'$ dominates the interior of the double-path structure, it
<figure><img src="image_26.png" /><figcaption>Figure 3 The double-path structure for DOMINATING SET is the subgraph on the top right minus the vertices $x$ and $y$. Top: an edge $\{x, y\}$ is replaced by a double-path structure. Bottom-left: the interior of the double-path structure can be dominated by six vertices (in red). Bottom-right: there is a set of six vertices that dominates $y$ and all vertices of the double-path structure except $a_x$.</figcaption></figure>

contains at least one vertex from the closed neighborhoods of $t_x, t_y, t_x'', t_y''$. Since these are pairwise disjoint, and do not contain $a_y, a_x$, or $b_x$, the set $B'$ contains a vertex from the closed neighborhood of each of $\{t_x, t_y, t_x'', t_y''\}$. Since $B'$ has size six, besides the four vertices from these closed neighborhoods, the vertex $a_y$, and the one vertex in $\{a_x, b_x\}$ there can be no further vertices in $B'$. Hence $B'$ does not contain $c_x$ or $d_x$, as these do not occur in the stated closed neighborhoods. This implies that to dominate $d_x$, the set $B'$ contains $e_x$. Then vertex $t_x'$ is not dominated by the vertex from $N_{G'}[t_x]$, and must therefore be dominated by the vertex in $B'$ from $N_{G'}[t_x'']$, implying that $g_x \in B'$. But the vertices mentioned so far do not dominate $c_y$, and regardless of how a vertex is chosen from the closed neighborhoods of $t_y$ and $t_y''$, the resulting choice does not dominate $c_y$ since no vertex from the closed neighborhoods of $t_y, t_y''$ is adjacent to $c_y$. So $c_y$ is not dominated by $B'$; a contradiction. □

Using the claim we finish the proof. The set $B' := S \cap B$ has size six and dominates all of $B \setminus \{a_x, a_y\}$, since those vertices cannot be dominated from elsewhere. If $B'$ contains $a_x$, then $B'$ does not dominate $a_y$. Since $S'$ is a dominating set, and $y$ is the only neighbor of $a_y$ outside of $B$, it follows that $y \in S'$. But then $S' \setminus B$ is a dominating set in $G$ of size $|S'| - 6 = \text{OPT}_{\text{DS}}(G') - 6$ in $G$: the edge $\{x, y\}$ in $G$ ensures that $y$ dominates $x$. If $B'$ contains $a_y$ instead, then the symmetric argument applies. Hence $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 6$. ◀

Using Lemma 10, we can replace a direct edge by a double-path structure while controlling the domination number. This allows two crossing edges to be reduced to four crossing triangles as in Figure 2. Even though more crossings are created in this way, these crossing triangles actually help to planarize the graph. The key point is that crossing triangles enforce a dominating set to locally act like a vertex cover, which allows us to exploit a known gadget for VERTEX COVER. The following two statements are useful to formalize these ideas. Recall that a vertex $v$ is simplicial in a graph $G$ if $N_G(v)$ forms a clique.

**Observation 12.** If $I$ is an independent set of simplicial degree-two vertices in a graph $G$, then $G$ has a minimum dominating set that contains no vertex of $I$.

**Proposition 13.** Let $U$ be a set of vertices in a graph $G$, such that for each edge $\{x, y\} \in E(G[U])$ there is a vertex $v \in V(G) \setminus U$ with $N_G(v) = \{x, y\}$. Then there is a minimum dominating set $S$ of $G$ such that $S$ forms a vertex cover of $G[U]$.

**Proof.** Construct a set $I$ as follows. For each $\{x, y\} \in E(G[U])$, add a vertex $v \in V(G) \setminus U$ with $N_G(v) = \{x, y\}$ to $I$. Then $I$ is an independent set of simplicial degree-two vertices.
<figure><img src="image_27.png" /><figcaption>Figure 3 The double-path structure for DOMINATING SET is the subgraph on the top right minus the vertices $x$ and $y$. Top: an edge $\{x, y\}$ is replaced by a double-path structure. Bottom-left: the interior of the double-path structure can be dominated by six vertices (in red). Bottom-right: there is a set of six vertices that dominates $y$ and all vertices of the double-path structure except $a_x$.</figcaption></figure>

contains at least one vertex from the closed neighborhoods of $t_x, t_y, t_x'', t_y''$. Since these are pairwise disjoint, and do not contain $a_y, a_x$, or $b_x$, the set $B'$ contains a vertex from the closed neighborhood of each of $\{t_x, t_y, t_x'', t_y''\}$. Since $B'$ has size six, besides the four vertices from these closed neighborhoods, the vertex $a_y$, and the one vertex in $\{a_x, b_x\}$ there can be no further vertices in $B'$. Hence $B'$ does not contain $c_x$ or $d_x$, as these do not occur in the stated closed neighborhoods. This implies that to dominate $d_x$, the set $B'$ contains $e_x$. Then vertex $t_x'$ is not dominated by the vertex from $N_{G'}[t_x]$, and must therefore be dominated by the vertex in $B'$ from $N_{G'}[t_x'']$, implying that $g_x \in B'$. But the vertices mentioned so far do not dominate $c_y$, and regardless of how a vertex is chosen from the closed neighborhoods of $t_y$ and $t_y''$, the resulting choice does not dominate $c_y$ since no vertex from the closed neighborhoods of $t_y, t_y''$ is adjacent to $c_y$. So $c_y$ is not dominated by $B'$; a contradiction. □

Using the claim we finish the proof. The set $B' := S \cap B$ has size six and dominates all of $B \setminus \{a_x, a_y\}$, since those vertices cannot be dominated from elsewhere. If $B'$ contains $a_x$, then $B'$ does not dominate $a_y$. Since $S'$ is a dominating set, and $y$ is the only neighbor of $a_y$ outside of $B$, it follows that $y \in S'$. But then $S' \setminus B$ is a dominating set in $G$ of size $|S'| - 6 = \text{OPT}_{\text{DS}}(G') - 6$ in $G$: the edge $\{x, y\}$ in $G$ ensures that $y$ dominates $x$. If $B'$ contains $a_y$ instead, then the symmetric argument applies. Hence $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 6$. ◀

Using Lemma 10, we can replace a direct edge by a double-path structure while controlling the domination number. This allows two crossing edges to be reduced to four crossing triangles as in Figure 2. Even though more crossings are created in this way, these crossing triangles actually help to planarize the graph. The key point is that crossing triangles enforce a dominating set to locally act like a vertex cover, which allows us to exploit a known gadget for VERTEX COVER. The following two statements are useful to formalize these ideas. Recall that a vertex $v$ is simplicial in a graph $G$ if $N_G(v)$ forms a clique.

**Observation 12.** If $I$ is an independent set of simplicial degree-two vertices in a graph $G$, then $G$ has a minimum dominating set that contains no vertex of $I$.

**Proposition 13.** Let $U$ be a set of vertices in a graph $G$, such that for each edge $\{x, y\} \in E(G[U])$ there is a vertex $v \in V(G) \setminus U$ with $N_G(v) = \{x, y\}$. Then there is a minimum dominating set $S$ of $G$ such that $S$ forms a vertex cover of $G[U]$.

**Proof.** Construct a set $I$ as follows. For each $\{x, y\} \in E(G[U])$, add a vertex $v \in V(G) \setminus U$ with $N_G(v) = \{x, y\}$ to $I$. Then $I$ is an independent set of simplicial degree-two vertices.
<figure><img src="image_27.png" /><figcaption>■ **Figure 4** Three copies of the 18-vertex gadget graph $H_{\text{vc}}$, which has four terminals $\{x, y, p, q\}$. Left: A vertex cover for $H_{\text{vc}}$ that contains $p$ and $q$ and has size eleven is shown in red. Middle: Any vertex cover for $H_{\text{vc}}$ that does not contain $p$ or $q$ contains the neighbors of $p$ and $q$ and at least one endpoint of the three thick edges, and contains at least eleven non-terminals. Right: Any vertex cover for $H_{\text{vc}}$ that does not contain $x$ or $y$ contains the four neighbors of $x$ and $y$ and at least three vertices from each of the two highlighted five-cycles, and contains at least ten non-terminals.</figcaption></figure>

By Observation 12 there is a minimum dominating set $S$ of $G$ that contains no vertex of $I$. Then $S \cap U$ is a vertex cover of $G[U]$: for an arbitrary edge $\{x, y\} \in E(G[U])$ there is a vertex $v$ in $I$ whose open neighborhood is $\{x, y\}$. Since $I \cap S = \emptyset$, at least one of $x$ and $y$ belongs to $S$ to dominate $v$. Hence the edge $\{x, y\}$ is covered by $S$. ◀

Proposition 13 relates minimum dominating sets to vertex covers. We therefore use a simplified version of a VERTEX COVER crossover gadget in our design. We exploit the graph $H_{\text{vc}}$ with four terminals $\{x, y, p, q\}$ that is shown in Figure 4. It was obtained by applying the “folding” reduction rule for VERTEX COVER [6, Lemma 2.3] on the gadget by Garey et al. [15] and omitting two superfluous edges. We use the following property of the graph $H_{\text{vc}}$. It states that in $H_{\text{vc}}$, for every axis from which a vertex cover contains no terminal vertex, the number of non-terminal vertices used in a vertex cover increases.

**Proposition 14.** Let $S$ be a vertex cover of $H_{\text{vc}}$ and let $\ell \in \{0, 1, 2\}$ be the number of pairs among $\{p, q\}$ and $\{x, y\}$ from which $S$ contains no vertices. Then $|S \setminus \{p, q, x, y\}| \ge 9 + \ell$.

**Proof.** We first show $|S \setminus \{p, q, x, y\}| \ge 9$ for any vertex cover $S$ of $H_{\text{vc}}$, proving the claim for $\ell = 0$. The non-terminal vertices of $H_{\text{vc}}$ can be partitioned into four vertex-disjoint triangles and an edge that is vertex-disjoint from the triangles. From any triangle, a vertex cover contains at least two vertices. From the remaining edge, it contains at least one vertex.

If $S$ contains no vertex of $\{p, q\}$, then as illustrated in the middle of Figure 4, $S$ contains at least eleven non-terminals. Hence $|S \setminus \{p, q, x, y\}| \ge 11 \ge 9 + \ell$.

If the previous case does not apply, then $\ell \le 1$ since $S$ contains a vertex of $\{p, q\}$. If $S$ contains no vertex of $\{x, y\}$, then as illustrated on the right of Figure 4, $S$ contains at least ten non-terminals. Hence $|S \setminus \{p, q, x, y\}| \ge 10 \ge 9 + \ell$. ◀

Using Proposition 14 we prove that replacing two crossing triangles in a DOMINATING SET instance by the gadget, increases the optimum by exactly nine.

**Lemma 15.** Let $G$ be a graph, and let $\{x, y, z\}$ and $\{p, q, r\}$ be two vertex-disjoint triangles in $G$ such that $z$ and $r$ have degree two in $G$. Then the graph $G'$ obtained from $G$ by replacing $z$ and $r$ by $H_{\text{vc}}$ as in Figure 5 satisfies $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 9$.

**Proof.** We prove equality by establishing matching upper- and lower bounds.

($\le$ Consider a minimum dominating set $S$ in $G$ that does not contain $r$ or $z$, which exists by Observation 12. Then $S$ contains at least one of $\{p, q\}$ to dominate $z$, and at least one
<figure><img src="image_28.png" /><figcaption>■ **Figure 4** Three copies of the 18-vertex gadget graph $H_{\text{vc}}$, which has four terminals $\{x, y, p, q\}$. Left: A vertex cover for $H_{\text{vc}}$ that contains $p$ and $q$ and has size eleven is shown in red. Middle: Any vertex cover for $H_{\text{vc}}$ that does not contain $p$ or $q$ contains the neighbors of $p$ and $q$ and at least one endpoint of the three thick edges, and contains at least eleven non-terminals. Right: Any vertex cover for $H_{\text{vc}}$ that does not contain $x$ or $y$ contains the four neighbors of $x$ and $y$ and at least three vertices from each of the two highlighted five-cycles, and contains at least ten non-terminals.</figcaption></figure>

By Observation 12 there is a minimum dominating set $S$ of $G$ that contains no vertex of $I$. Then $S \cap U$ is a vertex cover of $G[U]$: for an arbitrary edge $\{x, y\} \in E(G[U])$ there is a vertex $v$ in $I$ whose open neighborhood is $\{x, y\}$. Since $I \cap S = \emptyset$, at least one of $x$ and $y$ belongs to $S$ to dominate $v$. Hence the edge $\{x, y\}$ is covered by $S$. ◀

Proposition 13 relates minimum dominating sets to vertex covers. We therefore use a simplified version of a VERTEX COVER crossover gadget in our design. We exploit the graph $H_{\text{vc}}$ with four terminals $\{x, y, p, q\}$ that is shown in Figure 4. It was obtained by applying the “folding” reduction rule for VERTEX COVER [6, Lemma 2.3] on the gadget by Garey et al. [15] and omitting two superfluous edges. We use the following property of the graph $H_{\text{vc}}$. It states that in $H_{\text{vc}}$, for every axis from which a vertex cover contains no terminal vertex, the number of non-terminal vertices used in a vertex cover increases.

**Proposition 14.** Let $S$ be a vertex cover of $H_{\text{vc}}$ and let $\ell \in \{0, 1, 2\}$ be the number of pairs among $\{p, q\}$ and $\{x, y\}$ from which $S$ contains no vertices. Then $|S \setminus \{p, q, x, y\}| \ge 9 + \ell$.

**Proof.** We first show $|S \setminus \{p, q, x, y\}| \ge 9$ for any vertex cover $S$ of $H_{\text{vc}}$, proving the claim for $\ell = 0$. The non-terminal vertices of $H_{\text{vc}}$ can be partitioned into four vertex-disjoint triangles and an edge that is vertex-disjoint from the triangles. From any triangle, a vertex cover contains at least two vertices. From the remaining edge, it contains at least one vertex.

If $S$ contains no vertex of $\{p, q\}$, then as illustrated in the middle of Figure 4, $S$ contains at least eleven non-terminals. Hence $|S \setminus \{p, q, x, y\}| \ge 11 \ge 9 + \ell$.

If the previous case does not apply, then $\ell \le 1$ since $S$ contains a vertex of $\{p, q\}$. If $S$ contains no vertex of $\{x, y\}$, then as illustrated on the right of Figure 4, $S$ contains at least ten non-terminals. Hence $|S \setminus \{p, q, x, y\}| \ge 10 \ge 9 + \ell$. ◀

Using Proposition 14 we prove that replacing two crossing triangles in a DOMINATING SET instance by the gadget, increases the optimum by exactly nine.

**Lemma 15.** Let $G$ be a graph, and let $\{x, y, z\}$ and $\{p, q, r\}$ be two vertex-disjoint triangles in $G$ such that $z$ and $r$ have degree two in $G$. Then the graph $G'$ obtained from $G$ by replacing $z$ and $r$ by $H_{\text{vc}}$ as in Figure 5 satisfies $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 9$.

**Proof.** We prove equality by establishing matching upper- and lower bounds.

($\le$ Consider a minimum dominating set $S$ in $G$ that does not contain $r$ or $z$, which exists by Observation 12. Then $S$ contains at least one of $\{p, q\}$ to dominate $z$, and at least one
<figure><img src="image_28.png" /><figcaption>Figure 5 Illustration of how a crossing between two triangles is eliminated in an instance of DOMINATING SET. A copy of $H_{\text{VC}}$ is inserted, whose four terminals are identified with the four endpoints of the crossing edge. For each edge $\{u, v\}$ of the inserted copy of $H_{\text{VC}}$, an additional degree-two vertex is inserted that forms a triangle with $u$ and $v$.</figcaption></figure>

of $\{x, y\}$ to dominate $r$. We assume without loss of generality, by symmetry, that $p \in S$ and $x \in S$. As shown in Figure 4, there is a vertex cover for $H_{\text{VC}}$ of size 11 that contains $p$ and $x$, and therefore contains nine vertices from the interior of $H_{\text{VC}}$. Let $T$ be this set of nine vertices, and note that $T$ includes a neighbor of $q$ and a neighbor of $y$. We claim that $S' := S \cup T$ is a dominating set for $G'$ of size $|S| + 9 \le \text{OPT}_{\text{DS}}(G) + 9$. Since $T \cup \{p, x\}$ is a vertex cover of $H_{\text{VC}}$ and $H_{\text{VC}}$ has no isolated vertices, each vertex of $H_{\text{VC}}$ has a neighbor in $S'$ and is dominated. The degree-two vertices that are inserted into $G'$ in the last step are dominated by the vertex that covers the edge with which they form a triangle. Vertices $q$ and $y$ are dominated from their neighbors in $T$. Finally, the remaining vertices of $G'$ are dominated in the same way as in $G$.

(≥ To prove $\text{OPT}_{\text{DS}}(G') \ge \text{OPT}_{\text{DS}}(G) + 9$, we instead show $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 9$. Let $U \subseteq V(G')$ denote the vertices from the copy of $H_{\text{VC}}$ that was inserted; $U$ contains $p, q, x, y$, but $U$ does not contain the degree-two vertices that were inserted as the last step of the transformation. By Proposition 13, there is a minimum dominating set $S'$ of $G'$ such that $S' \cap U$ is a vertex cover of $G'[U]$. Let $\ell \in \{0, 1, 2\}$ be the number of pairs among $\{p, q\}$ and $\{x, y\}$ from which $S'$ contains no vertices. Since $S' \cap U$ is a vertex cover of $G'[U]$, which is isomorphic to $H_{\text{VC}}$, by Proposition 14 we know that $|(S' \cap U) \setminus \{p, q, x, y\}| \ge 9 + \ell$. Now let $S$ be obtained from $S'$ by removing all vertices of $(S' \cap U) \setminus \{p, q, x, y\}$, adding vertex $x$ if $S' \cap \{x, y\} = \emptyset$, and adding vertex $y$ if $S' \cap \{p, q\} = \emptyset$. Then $|S| \le |S'| - 9$ since we remove $9 + \ell$ vertices and add $\ell$ new ones. Since $S$ contains at least one vertex from $\{p, q\}$ and at least one vertex from $\{x, y\}$, it dominates the two triangles in $G$. Since it contains a superset of the terminal vertices that $S'$ contains, the remaining vertices of the graph are dominated as before. Hence $S$ is a dominating set in $G$ and $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 9$. ◀

Using the material so far, we can prove that the transformation operation in Figure 2 increases the size of an optimal dominating set by exactly 48.

**Lemma 16.** Let $\{a, b\}$ and $\{c, d\}$ be two disjoint edges of a graph $G$. Let $G'$ be the graph obtained by replacing these two edges as in Figure 2. Then $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 48$.

**Proof.** The transformation depicted in Figure 2 can be broken down into six steps: transform $\{a, b\}$ into a double-path structure, transform $\{c, d\}$ into a double-path structure, and perform four operations in which crossing triangles are replaced by gadgets. By Lemma 10, the two double-path insertions increase the size of a minimum dominating set by exactly 2·6. By Lemma 15, the four steps in which crossing triangles are eliminated increase the size of a minimum domination set by exactly 4·9. Hence $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 12 + 36$. ◀
<figure><img src="image_29.png" /><figcaption>Figure 5 Illustration of how a crossing between two triangles is eliminated in an instance of DOMINATING SET. A copy of $H_{\text{VC}}$ is inserted, whose four terminals are identified with the four endpoints of the crossing edge. For each edge $\{u, v\}$ of the inserted copy of $H_{\text{VC}}$, an additional degree-two vertex is inserted that forms a triangle with $u$ and $v$.</figcaption></figure>

of $\{x, y\}$ to dominate $r$. We assume without loss of generality, by symmetry, that $p \in S$ and $x \in S$. As shown in Figure 4, there is a vertex cover for $H_{\text{VC}}$ of size 11 that contains $p$ and $x$, and therefore contains nine vertices from the interior of $H_{\text{VC}}$. Let $T$ be this set of nine vertices, and note that $T$ includes a neighbor of $q$ and a neighbor of $y$. We claim that $S' := S \cup T$ is a dominating set for $G'$ of size $|S| + 9 \le \text{OPT}_{\text{DS}}(G) + 9$. Since $T \cup \{p, x\}$ is a vertex cover of $H_{\text{VC}}$ and $H_{\text{VC}}$ has no isolated vertices, each vertex of $H_{\text{VC}}$ has a neighbor in $S'$ and is dominated. The degree-two vertices that are inserted into $G'$ in the last step are dominated by the vertex that covers the edge with which they form a triangle. Vertices $q$ and $y$ are dominated from their neighbors in $T$. Finally, the remaining vertices of $G'$ are dominated in the same way as in $G$.

(≥ To prove $\text{OPT}_{\text{DS}}(G') \ge \text{OPT}_{\text{DS}}(G) + 9$, we instead show $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 9$. Let $U \subseteq V(G')$ denote the vertices from the copy of $H_{\text{VC}}$ that was inserted; $U$ contains $p, q, x, y$, but $U$ does not contain the degree-two vertices that were inserted as the last step of the transformation. By Proposition 13, there is a minimum dominating set $S'$ of $G'$ such that $S' \cap U$ is a vertex cover of $G'[U]$. Let $\ell \in \{0, 1, 2\}$ be the number of pairs among $\{p, q\}$ and $\{x, y\}$ from which $S'$ contains no vertices. Since $S' \cap U$ is a vertex cover of $G'[U]$, which is isomorphic to $H_{\text{VC}}$, by Proposition 14 we know that $|(S' \cap U) \setminus \{p, q, x, y\}| \ge 9 + \ell$. Now let $S$ be obtained from $S'$ by removing all vertices of $(S' \cap U) \setminus \{p, q, x, y\}$, adding vertex $x$ if $S' \cap \{x, y\} = \emptyset$, and adding vertex $y$ if $S' \cap \{p, q\} = \emptyset$. Then $|S| \le |S'| - 9$ since we remove $9 + \ell$ vertices and add $\ell$ new ones. Since $S$ contains at least one vertex from $\{p, q\}$ and at least one vertex from $\{x, y\}$, it dominates the two triangles in $G$. Since it contains a superset of the terminal vertices that $S'$ contains, the remaining vertices of the graph are dominated as before. Hence $S$ is a dominating set in $G$ and $\text{OPT}_{\text{DS}}(G) \le \text{OPT}_{\text{DS}}(G') - 9$. ◀

Using the material so far, we can prove that the transformation operation in Figure 2 increases the size of an optimal dominating set by exactly 48.

**Lemma 16.** Let $\{a, b\}$ and $\{c, d\}$ be two disjoint edges of a graph $G$. Let $G'$ be the graph obtained by replacing these two edges as in Figure 2. Then $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 48$.

**Proof.** The transformation depicted in Figure 2 can be broken down into six steps: transform $\{a, b\}$ into a double-path structure, transform $\{c, d\}$ into a double-path structure, and perform four operations in which crossing triangles are replaced by gadgets. By Lemma 10, the two double-path insertions increase the size of a minimum dominating set by exactly 2·6. By Lemma 15, the four steps in which crossing triangles are eliminated increase the size of a minimum domination set by exactly 4·9. Hence $\text{OPT}_{\text{DS}}(G') = \text{OPT}_{\text{DS}}(G) + 12 + 36$. ◀
3:12 Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Using Lemma 16 we easily obtain the following.

► **Lemma 17.** *There is a useful crossover gadget for DOMINATING SET.*

**Proof.** The gadget that is inserted to replace two edges {a, b} and {c, d} in the procedure of Figure 2 is planar and has its terminals u, u', v, v' on the outer face in the appropriate cyclic ordering. Since Lemma 16 shows that the replacement increases the size of a minimum dominating set by exactly 48, it follows that the structure serves as a useful crossover gadget for DOMINATING SET as per Definition 5.

◀

Theorem 2 now follows by combining Lemma 17 with the planarization argument of
Theorem 6 and the lower bound for the nonplanar case given by Theorem 9.

► **Theorem 2.** *Assuming SETH, there is no* $\varepsilon > 0$ *such that* DOMINATING SET on a planar graph G given along with a linear layout of cutwidth k can be solved in time $O^*((3 - \varepsilon)^k)$.

**Proof.** Suppose DOMINATING SET on a planar graph with a given linear layout of cutwidth $k$ can be solved in $O^*((3 - \varepsilon)^k)$ time for some $\varepsilon > 0$, by an algorithm called $A$. Then DOMINATING SET on a nonplanar graph with a given layout of cutwidth $k$ can be solved in time $O^*((3 - \varepsilon)^k)$ by reducing it to a planar graph with a linear layout of cutwidth $k + O(1)$ (using Theorem 6 and the existence of a useful crossover gadget; this blows up the graph size by at most a polynomial factor) and then running $A$. By Theorem 9, this contradicts SETH.

◀

**5 Conclusion**

In this work we have investigated whether SETH-based lower bounds for solving problems on graphs of bounded treewidth also apply for (1) planar graphs and (2) graphs of bounded cutwidth. To answer these questions, we showed that the graph parameter cutwidth can be preserved when reducing to a planar instance using suitably restricted crossover gadgets.

For both problems considered in this work, the runtime lower bound for solving the problem on graphs of bounded cutwidth continues to hold for *planar* graphs of bounded cutwidth. Hence planarity seems to offer no algorithmic advantage when working with graphs of bounded cutwidth. Moreover, for both INDEPENDENT SET and DOMINATING SET the runtime lower bound for the treewidth parameterization also applies for cutwidth.

Future work may explore other combinatorial problems on graphs of bounded cutwidth.
For example, what is the optimal running time for FEEDBACK VERTEX SET, ODD CYCLE
TRANSVERSAL, or HAMILTONIAN CYCLE on graphs of bounded cutwidth? What is the
complexity of the cutwidth parameterization of these problems on planar graphs? For the
GRAPH *q*-COLORING problem, these questions are answered in a recent manuscript by an
overlapping set of authors [21]: planarity offers no advantage, but the parameterization by
cutwidth *k* can be solved in time O\*(2^*k*) for all *q*, sharply contrasting that the treewidth
parameterization cannot be solved in time O\*((*q* − *ε*)^*k*') under SETH.

References

1 Julien Baste and Ignasi Sau. The role of planarity in connectivity problems parameterized by treewidth. *Theor. Comput. Sci.*, 570:1–14, 2015. doi:10.1016/j.tcs.2014.12.010.

2 Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: Fast subset convolution. In David S. Johnson and Uriel Feige, editors, *Proc. 39th STOC*, pages 67–74. ACM, 2007. doi:10.1145/1250790.1250801.
3:12 Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Using Lemma 16 we easily obtain the following.

► **Lemma 17.** *There is a useful crossover gadget for DOMINATING SET.*

**Proof.** The gadget that is inserted to replace two edges {$a, b$} and {$c, d$} in the procedure of Figure 2 is planar and has its terminals $u, u', v, v'$ on the outer face in the appropriate cyclic ordering. Since Lemma 16 shows that the replacement increases the size of a minimum dominating set by exactly 48, it follows that the structure serves as a useful crossover gadget for DOMINATING SET as per Definition 5.

◀

<figure><img src="image_30.png" /></figure>

Theorem 2 now follows by combining Lemma 17 with the planarization argument of
Theorem 6 and the lower bound for the nonplanar case given by Theorem 9.

► **Theorem 2.** *Assuming SETH, there is no* $\varepsilon > 0$ *such that* DOMINATING SET on a planar graph *G* given along with a linear layout of cutwidth *k* can be solved in time $O^*((3 - \varepsilon)^k)$.

**Proof.** Suppose DOMINATING SET on a planar graph with a given linear layout of cutwidth *k* can be solved in $O^*((3 - \varepsilon)^k)$ time for some $\varepsilon > 0$, by an algorithm called *A*. Then DOMINATING SET on a nonplanar graph with a given layout of cutwidth *k* can be solved in time $O^*((3 - \varepsilon)^k)$ by reducing it to a planar graph with a linear layout of cutwidth *k* + $O(1)$ (using Theorem 6 and the existence of a useful crossover gadget; this blows up the graph size by at most a polynomial factor) and then running *A*. By Theorem 9, this contradicts SETH.

◀

<figure><img src="image_31.png" /></figure>

5 Conclusion

In this work we have investigated whether SETH-based lower bounds for solving problems on graphs of bounded treewidth also apply for (1) planar graphs and (2) graphs of bounded cutwidth. To answer these questions, we showed that the graph parameter cutwidth can be preserved when reducing to a planar instance using suitably restricted crossover gadgets.

For both problems considered in this work, the runtime lower bound for solving the problem on graphs of bounded cutwidth continues to hold for *planar* graphs of bounded cutwidth. Hence planarity seems to offer no algorithmic advantage when working with graphs of bounded cutwidth. Moreover, for both INDEPENDENT SET and DOMINATING SET the runtime lower bound for the treewidth parameterization also applies for cutwidth.

Future work may explore other combinatorial problems on graphs of bounded cutwidth.
For example, what is the optimal running time for FEEDBACK VERTEX SET, ODD CYCLE
TRANSVERSAL, or HAMILTONIAN CYCLE on graphs of bounded cutwidth? What is the
complexity of the cutwidth parameterization of these problems on planar graphs? For the
GRAPH *q*-COLORING problem, these questions are answered in a recent manuscript by an
overlapping set of authors [21]: planarity offers no advantage, but the parameterization by
cutwidth *k* can be solved in time $O^*(2^k)$ for all *q*, sharply contrasting that the treewidth
parameterization cannot be solved in time $O^*((q - \varepsilon)^k)$ under SETH.

References

1 Julien Baste and Ignasi Sau. The role of planarity in connectivity problems parameterized by treewidth. *Theor. Comput. Sci.*, 570:1–14, 2015. doi:10.1016/j.tcs.2014.12.010.

2 Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: Fast subset convolution. In David S. Johnson and Uriel Feige, editors, *Proc. 39th STOC*, pages 67–74. ACM, 2007. doi:10.1145/1250790.1250801.
3 Hans L. Bodlaender. A Partial $k$-Arboretum of Graphs with Bounded Treewidth. *Theor. Comput. Sci.*, 209(1-2):1-45, 1998. doi:10.1016/S0304-3975(97)00228-4.

4 Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Inf. Comput.*, 243:86-111, 2015. doi:10.1016/j.ic.2014.12.008.

5 Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial Optimization on Graphs of Bounded Treewidth. *Comput. J.*, 51(3):255-269, 2008. doi:10.1093/comjnl/bxm037.

6 Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex Cover: Further Observations and Further Improvements. *J. Algorithms*, 41(2):280-301, 2001. doi:10.1006/jagm.2001.1186.

7 Bruno Courcelle. The Monadic Second-Order Logic of Graphs I: Recognizable Sets of Finite Graphs. *Inf. Comput.*, 85(1):12-75, 1990. doi:10.1016/0890-5401(90)90043-H.

8 Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, *Proc. 45th STOC*, pages 301-310. ACM, 2013. doi:10.1145/2488608.2488646.

9 Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In *Proc. 52nd FOCS*, pages 150-159, 2011. doi:10.1109/FOCS.2011.23.

10 Erik D. Demaine and MohammadTaghi Hajiaghayi. The Bidimensionality Theory and Its Algorithmic Applications. *Comput. J.*, 51(3):292-302, 2008. doi:10.1093/comjnl/bxm033.

11 Josep Díaz, Jordi Petit, and Maria J. Serna. A survey of graph layout problems. *ACM Comput. Surv.*, 34(3):313-356, 2002. doi:10.1145/568522.568523.

12 David Eppstein. Pathwidth of planarized drawing of $K_{3,n}$. TheoryCS StackExchange question, 2016. URL: http://csttheory.stackexchange.com/questions/35974/.

13 David Eppstein. The Effect of Planarization on Width. In *Proc. 25th GD*, volume 10692 of LNCS, pages 560-572, 2017. doi:10.1007/978-3-319-73915-1_43.

14 Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. *J. ACM*, 63(4):29:1-29:60, 2016. doi:10.1145/2886094.

15 M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. *Theoretical Computer Science*, 1(3):237-267, 1976. doi:10.1016/0304-3975(76)90059-1.

16 Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth. *CoRR*, abs/1806.10513, 2018. arXiv:1806.10513.

17 Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and Algorithmic Aspects. In *Proc. 11th IPEC*, volume 63 of LIPIcs, pages 15:1-15:13, 2016. doi:10.4230/LIPIcs.IPEC.2016.15.

18 Russel Impagliazzo and Ramamohan Paturi. On the Complexity of $k$-SAT. *J. Comput. Syst. Sci.*, 62(2):367-375, 2001. doi:10.1006/jcss.2000.1727.

19 Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? *J. Comput. Syst. Sci.*, 63(4):512-530, 2001. doi:10.1006/jcss.2001.1774.

20 Bart M. P. Jansen and Jules J. H. M. Wulms. Lower Bounds for Protrusion Replacement by Counting Equivalence Classes. In Jiong Guo and Danny Hermelin, editors, *Proc. 11th IPEC*, volume 63 of LIPIcs, pages 17:1-17:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.IPEC.2016.17.

21 Bart M.P. Jansen and Jesper Nederlof. Computing the Chromatic Number Using Graph Decompositions via Matrix Rank. In *Proc. 26th ESA*, 2018. In press.
3. Hans L. Bodlaender. A Partial $k$-Arboretum of Graphs with Bounded Treewidth. *Theor. Comput. Sci.*, 209(1-2):1-45, 1998. doi:10.1016/S0304-3975(97)00228-4.

4. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Inf. Comput.*, 243:86-111, 2015. doi:10.1016/j.ic.2014.12.008.

5. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial Optimization on Graphs of Bounded Treewidth. *Comput. J.*, 51(3):255-269, 2008. doi:10.1093/comjnl/bxm037.

6. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex Cover: Further Observations and Further Improvements. *J. Algorithms*, 41(2):280-301, 2001. doi:10.1006/jagm.2001.1186.

7. Bruno Courcelle. The Monadic Second-Order Logic of Graphs I: Recognizable Sets of Finite Graphs. *Inf. Comput.*, 85(1):12-75, 1990. doi:10.1016/0890-5401(90)90043-H.

8. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, *Proc. 45th STOC*, pages 301-310. ACM, 2013. doi:10.1145/2488608.2488646.

9. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In *Proc. 52nd FOCS*, pages 150-159, 2011. doi:10.1109/FOCS.2011.23.

10. Erik D. Demaine and MohammadTaghi Hajiaghayi. The Bidimensionality Theory and Its Algorithmic Applications. *Comput. J.*, 51(3):292-302, 2008. doi:10.1093/comjnl/bxm033.

11. Josep Díaz, Jordi Petit, and Maria J. Serna. A survey of graph layout problems. *ACM Comput. Surv.*, 34(3):313-356, 2002. doi:10.1145/568522.568523.

12. David Eppstein. Pathwidth of planarized drawing of $K_{3,n}$. TheoryCS StackExchange question, 2016. URL: http://csttheory stackexchange com/questions/35974/.

13. David Eppstein. The Effect of Planarization on Width. In *Proc. 25th GD*, volume 10692 of LNCS, pages 560-572, 2017. doi:10.1007/978-3-319-73915-1_43.

14. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. *J. ACM*, 63(4):29:1-29:60, 2016. doi:10.1145/2886094.

15. M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. *Theoretical Computer Science*, 1(3):237-267, 1976. doi:10.1016/0304-3975(76)90059-1.

16. Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth. *CoRR*, abs/1806.10513, 2018. arXiv:1806.10513.

17. Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and Algorithmic Aspects. In *Proc. 11th IPEC*, volume 63 of LIPIcs, pages 15:1-15:13, 2016. doi:10.4230/LIPIcs.IPEC.2016.15.

18. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of $k$-SAT. *J. Comput. Syst. Sci.*, 62(2):367-375, 2001. doi:10.1006/jcss.2000.1727.

19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? *J. Comput. Syst. Sci.*, 63(4):512-530, 2001. doi:10.1006/jcss.2001.1774.

20. Bart M. P. Jansen and Jules J. H. M. Wulms. Lower Bounds for Protrusion Replacement by Counting Equivalence Classes. In Jiong Guo and Danny Hermelin, editors, *Proc. 11th IPEC*, volume 63 of LIPIcs, pages 17:1-17:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.IPEC.2016.17.

21. Bart M.P. Jansen and Jesper Nederlof. Computing the Chromatic Number Using Graph Decompositions via Matrix Rank. In *Proc. 26th ESA*, 2018. In press.
3:14 Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

22 Ephraim Korach and Nir Solel. Tree-Width, Path-Width, and Cutwidth. *Discrete Applied Mathematics*, 43(1):97-101, 1993. doi:10.1016/0166-218X(93)90171-J.

23 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In *Proc. 22nd SODA*, pages 777–789, 2011. doi: 10.1137/1.9781611973082.61.

24 Dániel Marx. The Square Root Phenomenon in Planar Graphs. In Michael R. Fellows, Xuehou Tan, and Binhai Zhu, editors, *Proc. 3rd FAW-AAIM*, volume 7924 of *Lecture Notes in Computer Science*, page 1. Springer, 2013. doi:10.1007/978-3-642-38756-2_1.

25 Michal Pilipczuk. Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach. In *Proc. 36th MFCS*, pages 520–531, 2011. doi:10.1007/978-3-642-22993-0_47.

26 Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. *J. Algorithms*, 56(1):1–24, 2005. doi:10.1016/j.jalgor.2004.12.001.

27 Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth II: Algorithms for partial w-trees of bounded degree. *J. Algorithms*, 56(1):25–49, 2005. doi:10.1016/j.jalgor.2004.12.003.

28 Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In *Proc. 17th ESA*, pages 566–577, 2009. doi:10.1007/978-3-642-04128-0_51.
3:14 Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

22 Ephraim Korach and Nir Solel. Tree-Width, Path-Width, and Cutwidth. *Discrete Applied Mathematics*, 43(1):97-101, 1993. doi:10.1016/0166-218X(93)90171-J.

23 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In *Proc. 22nd SODA*, pages 777–789, 2011. doi: 10.1137/1.9781611973082.61.

24 Dániel Marx. The Square Root Phenomenon in Planar Graphs. In Michael R. Fellows, Xuehou Tan, and Binhai Zhu, editors, *Proc. 3rd FAW-AAIM*, volume 7924 of *Lecture Notes in Computer Science*, page 1. Springer, 2013. doi:10.1007/978-3-642-38756-2_1.

25 Michal Pilipczuk. Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach. In *Proc. 36th MFCS*, pages 520–531, 2011. doi:10.1007/978-3-642-22993-0_47.

26 Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm. *J. Algorithms*, 56(1):1–24, 2005. doi:10.1016/j.jalgor.2004.12.001.

27 Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender. Cutwidth II: Algorithms for partial w-trees of bounded degree. *J. Algorithms*, 56(1):25–49, 2005. doi:10.1016/j.jalgor.2004.12.003.

28 Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In *Proc. 17th ESA*, pages 566–577, 2009. doi:10.1007/978-3-642-04128-0_51.
# Multivariate Analysis of Orthogonal Range Searching and Graph Distances

**Karl Bringmann**

Max-Planck-Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
kbringma@mpi-inf.mpg.de

**Thore Husfeldt<fnref n="1" />**

BARC, IT University of Copenhagen, Denmark, and Lund University, Sweden
thore@itu.dk

https://orcid.org/0000-0001-9078-4512

**Måns Magnusson**

Department of Computer Science, Lund University, Sweden
mans.magnusson.888@student.lu.se

## Abstract

We show that the eccentricities, diameter, radius, and Wiener index of an undirected *n*-vertex graph with nonnegative edge lengths can be computed in time $O(n \cdot (\frac{k+\lfloor \log n \rfloor}{k}) \cdot 2^k k^2 \log n)$, where *k* is the treewidth of the graph. For every $\epsilon > 0$, this bound is $n^{1+\epsilon} \exp O(k)$, which matches a hardness result of Abboud, Vassilevska Williams, and Wang (SODA 2015) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comp. Geom., 2009) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form $\log^d n$ to $(\frac{d+\lfloor \log n \rfloor}{d})$, as originally observed by Monier (J. Alg. 1980).

We also investigate the parameterization by vertex cover number.

**2012 ACM Subject Classification** Theory of computation → Shortest paths, Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Computational geometry, Mathematics of computing → Paths and connectivity problems

**Keywords and phrases** Diameter, radius, Wiener index, orthogonal range searching, treewidth, vertex cover number

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.4

**Acknowledgements** We thank Amir Abboud and Rasmus Pagh for useful discussions.

## 1 Introduction

Pairwise distances in an undirected, unweighted graph can be computed by performing a graph exploration, such as breadth-first search, from every vertex. This straightforward procedure determines the diameter of a given graph with *n* vertices and *m* edges in time $O(nm)$. It is surprisingly difficult to improve upon this idea in general. In fact, Roditty and Vassilevska Williams [14] have shown that an algorithm that can distinguish between diameter 2 and 3 in an undirected sparse graph in subquadratic time refutes the Orthogonal Vectors conjecture.

<figure><img src="image_29.png" /></figure>

<footnote n="1">¹ Swedish Research Council grant VR-2016-03855 and Villum Foundation grant 16582.</footnote>
# Multivariate Analysis of Orthogonal Range Searching and Graph Distances

## Karl Bringmann

Max-Planck-Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
kbringma@mpi-inf.mpg.de

## Thore Husfeldt<fnref n="1" />

BARC, IT University of Copenhagen, Denmark, and Lund University, Sweden
thore@itu.dk

https://orcid.org/0000-0001-9078-4512

## Måns Magnusson

Department of Computer Science, Lund University, Sweden
mans.magnusson.888@student.lu.se

### Abstract

We show that the eccentricities, diameter, radius, and Wiener index of an undirected *n*-vertex graph with nonnegative edge lengths can be computed in time $O(n \cdot (k+\lceil\log n\rceil) \cdot 2^k k^2 \log n)$, where *k* is the treewidth of the graph. For every $\epsilon > 0$, this bound is $n^{1+\epsilon} \exp O(k)$, which matches a hardness result of Abboud, Vassilevska Williams, and Wang (SODA 2015) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comp. Geom., 2009) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form $\log^d n$ to $(d+\lceil\log n\rceil)$, as originally observed by Monier (J. Alg. 1980).

We also investigate the parameterization by vertex cover number.

**2012 ACM Subject Classification** Theory of computation → Shortest paths, Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Computational geometry, Mathematics of computing → Paths and connectivity problems

**Keywords and phrases** Diameter, radius, Wiener index, orthogonal range searching, treewidth, vertex cover number

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.4

**Acknowledgements** We thank Amir Abboud and Rasmus Pagh for useful discussions.

## 1 Introduction

Pairwise distances in an undirected, unweighted graph can be computed by performing a graph exploration, such as breadth-first search, from every vertex. This straightforward procedure determines the diameter of a given graph with *n* vertices and *m* edges in time $O(nm)$. It is surprisingly difficult to improve upon this idea in general. In fact, Roditty and Vassilevska Williams [14] have shown that an algorithm that can distinguish between diameter 2 and 3 in an undirected sparse graph in subquadratic time refutes the Orthogonal Vectors conjecture.

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<footnote n="1">¹ Swedish Research Council grant VR-2016-03855 and Villum Foundation grant 16582.</footnote>

<footnote>© Karl Bringmann, and Thore Husfeldt, and Måns Magnusson;</footnote>

<footnote>licensed under Creative Commons License CC-BY</footnote>

<footnote>13th International Symposium on Parameterized and Exact Computation (IPEC 2018).</footnote>

<footnote>Editors: Christophe Paul and Michal Pilipczuk; Article No. 4; pp. 4:1–4:13</footnote>

<footnote>LIPICS</footnote>

<footnote>Leibniz International Proceedings in Informatics</footnote>

<footnote>Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany</footnote>
## 4:2 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

However, for very sparse graphs, the running time becomes linear. In particular, the diameter of a tree can be computed in linear time $O(n)$ by a folklore result that traverses the graph twice. In fact, an algorithm by Cabello and Knauer shows that for constant treewidth $k \ge 3$, the diameter (and other distance parameters) can be computed in time $O(n \log^{k-1} n)$, where the Landau symbol absorbs the dependency on $k$ as well as the time required for computing a tree decomposition. The question raised in [1] is how the complexity of this problem grows with the treewidth of the graph. We show the following result:

**Theorem 1.** The eccentricities, diameter, radius, and Wiener index of a given undirected $n$-vertex graph $G$ of treewidth $\text{tw}(G)$ and nonnegative edge lengths can be computed in time linear in

$$n \cdot \binom{k + \lfloor \log n \rfloor}{k} \cdot 2^k k^2 \log n \quad (1)$$

where $k = 5 \text{tw}(G) + 4$.

For every $\epsilon > 0$, the bound (1) is $n^{1+\epsilon} \exp O(\text{tw}(G))$. This improves the dependency on the treewidth over the running time $n^{1+\epsilon} \exp O(\text{tw}(G) \log \text{tw}(G))$ of Abboud, Vassilevska Williams, and Wang [1]. Our improvement is tight in the following sense. Abboud et al. [1] also showed that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [10], there can be no algorithm that computes the diameter with running time

$$n^{2-\delta} \exp o(\text{tw}(G)) \quad \text{for any } \delta > 0. \quad (2)$$

In fact, this holds under the potentially weaker Orthogonal Vectors conjecture, see [17] for an introduction to these arguments. Thus, under this assumption, the dependency on $\text{tw}(G)$ in Theorem 1 cannot be significantly improved, even if the dependency on $n$ is relaxed from just above linear to just below quadratic. Our analysis encompasses the Wiener index, an important structural graph parameter left unexplored by [1].

Perhaps surprisingly, the main insight needed to establish Theorem 1 has nothing to do with graph distances or treewidth. Instead, we make – or re-discover – the following observation about the running time of $d$-dimensional range trees:

**Lemma 2 ([13]).** A $d$-dimensional range tree over $n$ points supporting orthogonal range queries for the aggregate value over a commutative monoid has query time $O(2^d \cdot B(n, d))$ and can be built in time $O(\text{nd} \cdot B(n, d))$, where

$$B(n, d) = \binom{d + \lfloor \log n \rfloor}{d}.$$

This is a more careful statement than the standard textbook analysis, which gives the query time as $O(\log^d n)$ and the construction time as $O(n \log^d n)$. For many values of $d$, the asymptotic complexities of these bounds agree – in particular, this is true for constant $d$ and for very large $d$, which are the main regimes of interest to computational geometers. But crucially, $B(n, d)$ is always $n^\epsilon \exp O(d)$ for any $\epsilon > 0$, while $\log^d n$ is not.

After Lemma 2 is realised, Theorem 1 follows via divide-and-conquer in decomposable graphs, closely following the idea of Cabello and Knauer [6] and augmented with known arguments [1, 5]. We choose to give a careful presentation of the entire construction, as some of the analysis is quite fragile.

Using known reductions, this implies that the following multivariate lower bound on orthogonal range searching is tight:
## 4:2 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

However, for very sparse graphs, the running time becomes linear. In particular, the diameter of a tree can be computed in linear time $O(n)$ by a folklore result that traverses the graph twice. In fact, an algorithm by Cabello and Knauer shows that for constant treewidth $k \ge 3$, the diameter (and other distance parameters) can be computed in time $O(n \log^{k-1} n)$, where the Landau symbol absorbs the dependency on $k$ as well as the time required for computing a tree decomposition. The question raised in [1] is how the complexity of this problem grows with the treewidth of the graph. We show the following result:

**Theorem 1.** The eccentricities, diameter, radius, and Wiener index of a given undirected $n$-vertex graph $G$ of treewidth $\text{tw}(G)$ and nonnegative edge lengths can be computed in time linear in

$$n \cdot \binom{k + \lfloor \log n \rfloor}{k} \cdot 2^k k^2 \log n \quad (1)$$

where $k = 5 \text{tw}(G) + 4$.

For every $\epsilon > 0$, the bound (1) is $n^{1+\epsilon} \exp O(\text{tw}(G))$. This improves the dependency on the treewidth over the running time $n^{1+\epsilon} \exp O(\text{tw}(G) \log \text{tw}(G))$ of Abboud, Vassilevska Williams, and Wang [1]. Our improvement is tight in the following sense. Abboud et al. [1] also showed that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [10], there can be no algorithm that computes the diameter with running time

$$n^{2-\delta} \exp o(\text{tw}(G)) \quad \text{for any } \delta > 0. \quad (2)$$

In fact, this holds under the potentially weaker Orthogonal Vectors conjecture, see [17] for an introduction to these arguments. Thus, under this assumption, the dependency on $\text{tw}(G)$ in Theorem 1 cannot be significantly improved, even if the dependency on $n$ is relaxed from just above linear to just below quadratic. Our analysis encompasses the Wiener index, an important structural graph parameter left unexplored by [1].

Perhaps surprisingly, the main insight needed to establish Theorem 1 has nothing to do with graph distances or treewidth. Instead, we make – or re-discover – the following observation about the running time of $d$-dimensional range trees:

**Lemma 2 ([13]).** A $d$-dimensional range tree over $n$ points supporting orthogonal range queries for the aggregate value over a commutative monoid has query time $O(2^d \cdot B(n, d))$ and can be built in time $O(n \cdot B(n, d))$, where

$$B(n, d) = \binom{d + \lfloor \log n \rfloor}{d}.$$

This is a more careful statement than the standard textbook analysis, which gives the query time as $O(\log^d n)$ and the construction time as $O(n \log^d n)$. For many values of $d$, the asymptotic complexities of these bounds agree – in particular, this is true for constant $d$ and for very large $d$, which are the main regimes of interest to computational geometers. But crucially, $B(n, d)$ is always $n^\epsilon \exp O(d)$ for any $\epsilon > 0$, while $\log^d n$ is not.

After Lemma 2 is realised, Theorem 1 follows via divide-and-conquer in decomposable graphs, closely following the idea of Cabello and Knauer [6] and augmented with known arguments [1, 5]. We choose to give a careful presentation of the entire construction, as some of the analysis is quite fragile.

Using known reductions, this implies that the following multivariate lower bound on orthogonal range searching is tight:
**Theorem 3** (Implicit in [1]). A data structure for the orthogonal range query problem for the monoid (Z, max) with construction time n · q'(n, d) and query time q'(n, d), where

$$q'(n, d) = n^{1-\epsilon} \exp o(d)$$

for some $\epsilon > 0$, refutes the Strong Exponential Time hypothesis.

We also investigate the same problems parameterized by vertex cover number:

**Theorem 4.** The eccentricities, diameter, and radius of a given undirected, unweighted n-vertex graph G with vertex cover number k can be computed in time $O(nk + 2^k k^2)$. The Wiener index can be computed in time $O(nk2^k)$.

Both of these bounds are $n \exp O(k)$. It follows from [1] that a lower bound of the form (2) holds for this parameter as well.

## 1.1 Related work

Abboud et al. [1] show that given a graph and an optimal tree decomposition, various graph distances can be computed in time $O(k^2 n \log^{k-1} n)$, where $k = \text{tw}(G)$. This bound is $n^{1+\epsilon} \exp O(k \log k)$ for any $\epsilon > 0$. This subsumes the running time for finding an approximate tree decomposition with $k = O(\text{tw}(G))$ from the input graph [5], which is $n \exp O(k)$. Their algorithm extends the construction of Cabello and Knauer [6] to superconstant treewidth. According to [6], the idea of expressing graph distances as coordinates was first mentioned by Shi [15].

If the diameter in the input graph is constant, the diameter can be computed in time $n \exp O(\text{tw}(G))$ [9]. This is tight in both parameters in the sense that [1] rules out the running time (2) even for distinguishing diameter 2 from 3, and every algorithm needs to inspect $\Omega(n)$ vertices even for treewidth 1. For non-constant diameter $\Delta$, the bound from [9] deteriorates as $n \exp O(\text{tw}(G) \log \Delta)$. However, the construction cannot be used to compute the Wiener index.

The literature on algorithms for graph distance parameters such as diameter or Wiener index is very rich, and we refer to the introduction of [1] for an overview of results directly relating to the present work. A recent paper by Bentert and Nichterlein [2] gives a comprehensive overview of many other parameterisations.

Orthogonal range searching using a multidimensional range tree was first described by Bentley [3], Lueker [12], Willard [16], and Lee and Wong [11], who showed that this data structure supports query time $O(\log^d n)$ and construction time $O(n \log^{d-1} n)$. Several papers have improved this in various ways by factors logarithmic in $n$; for instance, Chazelle's construction [8] achieves query time $O(\log^{d-1} n)$.

## 1.2 Discussion

In hindsight, the present result is a somewhat undramatic resolution of an open problem that has been viewed as potentially fruitful by many people [1], including the second author [9]. In particular, the resolution has led neither to an exciting new technique for showing conditional lower bounds of the form $n^{2-\epsilon} \exp \omega(k)$, nor a clever new algorithm for graph diameter. Instead, our solution follows the ideas of Cabello and Knauer [6] for constant treewidth, much like in [1]. All that was needed was a better understanding of the asymptotics of bivariate functions, rediscovering a 40-year old analysis of spatial data structures [13] (see the discussion in Sec. 3.3), and using a recent algorithm for approximate tree decompositions [5].
**Theorem 3** (Implicit in [1]). A data structure for the orthogonal range query problem for the monoid (Z, max) with construction time n · q'(n, d) and query time q'(n, d), where

$$q'(n, d) = n^{1-\epsilon} \exp o(d)$$

for some $\epsilon > 0$, refutes the Strong Exponential Time hypothesis.

We also investigate the same problems parameterized by vertex cover number:

**Theorem 4.** The eccentricities, diameter, and radius of a given undirected, unweighted n-vertex graph G with vertex cover number k can be computed in time $O(nk + 2^k k^2)$. The Wiener index can be computed in time $O(nk2^k)$.

Both of these bounds are $n \exp O(k)$. It follows from [1] that a lower bound of the form (2) holds for this parameter as well.

## 1.1 Related work

Abboud et al. [1] show that given a graph and an optimal tree decomposition, various graph distances can be computed in time $O(k^2 n \log^{k-1} n)$, where $k = \text{tw}(G)$. This bound is $n^{1+\epsilon} \exp O(k \log k)$ for any $\epsilon > 0$. This subsumes the running time for finding an approximate tree decomposition with $k = O(\text{tw}(G))$ from the input graph [5], which is $n \exp O(k)$. Their algorithm extends the construction of Cabello and Knauer [6] to superconstant treewidth. According to [6], the idea of expressing graph distances as coordinates was first mentioned by Shi [15].

If the diameter in the input graph is constant, the diameter can be computed in time $n \exp O(\text{tw}(G))$ [9]. This is tight in both parameters in the sense that [1] rules out the running time (2) even for distinguishing diameter 2 from 3, and every algorithm needs to inspect $\Omega(n)$ vertices even for treewidth 1. For non-constant diameter $\Delta$, the bound from [9] deteriorates as $n \exp O(\text{tw}(G) \log \Delta)$. However, the construction cannot be used to compute the Wiener index.

The literature on algorithms for graph distance parameters such as diameter or Wiener index is very rich, and we refer to the introduction of [1] for an overview of results directly relating to the present work. A recent paper by Bentert and Nichterlein [2] gives a comprehensive overview of many other parameterisations.

Orthogonal range searching using a multidimensional range tree was first described by Bentley [3], Lueker [12], Willard [16], and Lee and Wong [11], who showed that this data structure supports query time $O(\log^d n)$ and construction time $O(n \log^{d-1} n)$. Several papers have improved this in various ways by factors logarithmic in $n$; for instance, Chazelle's construction [8] achieves query time $O(\log^{d-1} n)$.

## 1.2 Discussion

In hindsight, the present result is a somewhat undramatic resolution of an open problem that has been viewed as potentially fruitful by many people [1], including the second author [9]. In particular, the resolution has led neither to an exciting new technique for showing conditional lower bounds of the form $n^{2-\epsilon} \exp \omega(k)$, nor a clever new algorithm for graph diameter. Instead, our solution follows the ideas of Cabello and Knauer [6] for constant treewidth, much like in [1]. All that was needed was a better understanding of the asymptotics of bivariate functions, rediscovering a 40-year old analysis of spatial data structures [13] (see the discussion in Sec. 3.3), and using a recent algorithm for approximate tree decompositions [5].
## 4:4 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Of course, we can derive some satisfaction from the presentation of asymptotically tight bounds for fundamental graph parameters under a well-studied parameterization. In particular, the surprisingly elegant reductions in [1] cannot be improved. However, as we show in the appendix, when we parameterize by vertex cover number instead of treewidth, we can establish even cleaner and tight bounds without much effort.

Instead, the conceptual value of the present work may be in applying the multivariate perspective on high-dimensional computational geometry, reviving an overlooked analysis for non-constant dimension. To see the difference in perspective, Chazelle's improvement [8] of d-dimensional range queries from $log^d n$ to $log^{d-1} n$ makes a lot of sense for small d, but from the multivariate point of view, both bounds are $n^\epsilon \exp \Omega(d \log d)$. The range of relationships between d and n where the multivariate perspective on range trees gives some new insight is when d is asymptotically just shy of $log n$, see Sec. 2.1.

It remains open to find an algorithm for diameter with running time $n \exp O(\text{tw}(G))$, or an argument that such an algorithm is unlikely to exist under standard hypotheses. This requires better understanding of the regime $d = o(\log n)$.

# 2 Preliminaries

## 2.1 Asymptotics

We summarise the asymptotic relationships between various functions appearing in the present paper:

### ▶ Lemma 5.

$$B(n, d) = O(\log^d n). \qquad (3)$$

For any $\epsilon > 0$,

$$B(n, d) = n^{\epsilon} \exp O(d), \qquad (4)$$

$$\log^d n = n^{\epsilon} \exp \Omega(d \log d), \qquad (5)$$

$$\log^d n = n^{\epsilon} \exp O(d \log d). \qquad (6)$$

The first expression shows that $B(n, d)$ is always at least as informative as $O(\log^d n)$. The next two expressions show that from the perspective of parameterised complexity, the two bounds differ asymptotically: $B(n, d)$ depends single-exponentially on $d$ (no matter how small $\epsilon > 0$ is chosen), while $\log^d n$ does not (no matter how large $\epsilon$ is chosen). Expression (6) just shows that (5) is maximally pessimistic.

**Proof.** Write $h = \lceil \log n \rceil$. To see (3), consider first the case where $d < h$. Using $\binom{a}{b} \le a^b/b!$ we see that

$$\binom{d+h}{d} \le \binom{2h}{d} \le \frac{(2h)^d}{d!} = \frac{2^d}{d!} h^d = O(\log^d n). \qquad (7)$$

Next, if $d \ge h$ then

$$\binom{d+h}{d} = \binom{d+h}{h} \le \binom{2d}{h} = \frac{2^h}{h!} d^h \le d^h,$$

provided $h \ge 4$. It remains to observe that $d^h \le h^d = O(\log^d n)$. Indeed, since the function $\alpha \mapsto \alpha/\ln \alpha$ is increasing for $\alpha \ge e$, we have $h/\ln h \le d/\ln d$, which implies $\exp(h \ln d) \le \exp(d \ln h)$ as needed.
## 4:4 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Of course, we can derive some satisfaction from the presentation of asymptotically tight bounds for fundamental graph parameters under a well-studied parameterization. In particular, the surprisingly elegant reductions in [1] cannot be improved. However, as we show in the appendix, when we parameterize by vertex cover number instead of treewidth, we can establish even cleaner and tight bounds without much effort.

Instead, the conceptual value of the present work may be in applying the multivariate perspective on high-dimensional computational geometry, reviving an overlooked analysis for non-constant dimension. To see the difference in perspective, Chazelle's improvement [8] of d-dimensional range queries from $log^d n$ to $log^{d-1} n$ makes a lot of sense for small d, but from the multivariate point of view, both bounds are $n^\epsilon \exp \Omega(d \log d)$. The range of relationships between d and n where the multivariate perspective on range trees gives some new insight is when d is asymptotically just shy of $log n$, see Sec. 2.1.

It remains open to find an algorithm for diameter with running time $n \exp O(\text{tw}(G))$, or an argument that such an algorithm is unlikely to exist under standard hypotheses. This requires better understanding of the regime $d = o(\log n)$.

# 2 Preliminaries

## 2.1 Asymptotics

We summarise the asymptotic relationships between various functions appearing in the present paper:

### ▶ Lemma 5.

$$B(n, d) = O(\log^d n). \qquad (3)$$

For any $\epsilon > 0$,

$$B(n, d) = n^{\epsilon} \exp O(d), \qquad (4)$$

$$\log^d n = n^{\epsilon} \exp \Omega(d \log d), \qquad (5)$$

$$\log^d n = n^{\epsilon} \exp O(d \log d). \qquad (6)$$

The first expression shows that $B(n, d)$ is always at least as informative as $O(\log^d n)$. The next two expressions show that from the perspective of parameterised complexity, the two bounds differ asymptotically: $B(n, d)$ depends single-exponentially on $d$ (no matter how small $\epsilon > 0$ is chosen), while $\log^d n$ does not (no matter how large $\epsilon$ is chosen). Expression (6) just shows that (5) is maximally pessimistic.

**Proof.** Write $h = \lceil \log n \rceil$. To see (3), consider first the case where $d < h$. Using $\binom{a}{b} \le a^b/b!$ we see that

$$\binom{d+h}{d} \le \binom{2h}{d} \le \frac{(2h)^d}{d!} = \frac{2^d}{d!} h^d = O(\log^d n). \qquad (7)$$

Next, if $d \ge h$ then

$$\binom{d+h}{d} = \binom{d+h}{h} \le \binom{2d}{h} = \frac{2^h}{h!} d^h \le d^h,$$

provided $h \ge 4$. It remains to observe that $d^h \le h^d = O(\log^d n)$. Indeed, since the function $\alpha \mapsto \alpha/\ln \alpha$ is increasing for $\alpha \ge e$, we have $h/\ln h \le d/\ln d$, which implies $\exp(h \ln d) \le \exp(d \ln h)$ as needed.
For (4), we let $\delta = d/h$ and consider two cases. First, from Stirling's formula we know
$$ \binom{a}{b} \le \left(\frac{ea}{b}\right)^b, \text{ so} $$

$$
\binom{d+h}{d} = \binom{(1+\delta)h}{\delta h} \le \left(\frac{e(1+\delta)h}{\delta h}\right)^{\delta h} \le \left(\frac{e(1+\delta)}{\delta}\right)^{2\delta \log n} = n^{2\delta \log(e(1+\delta)\delta^{-1})}.
$$

Using that $\delta \mapsto 2\delta \log(e(1+\delta)\delta^{-1})$ is a monotone increasing function in the interval $(0, \frac{1}{2}]$ that tends to 0 for $\delta \to 0$, we obtain $\binom{d+h}{d} \le n^\epsilon$ for any sufficiently small $\delta$.

It remains to consider the case that $\delta \ge c$ for some positive constant $c$ depending only on $\epsilon$. In this case, we have

$$
\binom{d+h}{d} \le \binom{(1+1/c)d}{d} < 2^{(1+1/c)d} = \exp O(d).
$$

We turn to (5). Assume that there is a function $g$ such that

$$
\log^d n = n^c g(d).
$$

Then choose $b > 1$ and consider $d$ such that $d = b^{-1} \log n$. Then

$$
g(d) \ge \frac{\log^d n}{n^c} = 2^{d \log \log n - c \log n} = 2^{d \log(bd) - cbd} = \exp \Omega(d \log d).
$$

Finally for (6), we repeat the argument from [1]. If $d \le \epsilon \log n / \log \log n$ then $\log^d n = 2^{d \log \log n} \le n^\epsilon$. In particular, if $d = o(\log n / \log \log n)$ then $\log^d n = n^{o(1)}$. Moreover, for $d \ge \log^{1/2} n$ we have $\log \log n \le 2 \log d$ and thus $\log^d n = 2^{d \log \log n} \le 4^{d \log d}$. $\blacksquare$

These calculations also show the regimes in which these considerations are at all interesting. For $d = o(\log n / \log \log n)$ then both functions are bounded by $n^{o(1)}$, and the multivariate perspective gives no insight. For $d \ge \log n$, both bounds exceed $n$, and we are better off running $n$ BFSs for computing diameters, or passing through the entire point set for range searching.

## 2.2 Model of computation

We operate in the word RAM, assuming constant-time arithmetic operations on coordinates and edge lengths, as well as constant-time operations in the monoid supported by our range queries. For ease of presentation, edge lengths are assumed to be nonnegative integers; we could work with abstract nonnegative weights instead [6].

# 3 Orthogonal Range Queries

## 3.1 Preliminaries

Let $P$ be a set of $d$-dimensional points. We will view $p \in P$ as a vector $p = (p_1, \dots, p_d)$.

A commutative *monoid* is a set *M* with an associative and commutative binary operator ⊕ with identity. The reader is invited to think of *M* as the integers with -∞ as identity and *a* ⊕ *b* = max{*a*, *b*}.

Let $f: P \to M$ be a function and define for each subset $Q \subseteq P$

$$
f(Q) = \bigoplus \{ f(q) : q \in Q \}
$$

with the understanding that $f(\emptyset)$ is the identity in $M$.
For (4), we let $\delta = d/h$ and consider two cases. First, from Stirling's formula we know $\binom{a}{b} \le \left(\frac{ea}{b}\right)^b$, so

$$ \binom{d+h}{d} = \binom{(1+\delta)h}{\delta h} \le \left(\frac{e(1+\delta)h}{\delta h}\right)^{\delta h} \le \left(\frac{e(1+\delta)}{\delta}\right)^{2\delta \log n} = n^{2\delta \log(e(1+\delta)\delta^{-1})}. $$

Using that $\delta \mapsto 2\delta \log(e(1+\delta)\delta^{-1})$ is a monotone increasing function in the interval $(0, \frac{1}{2}]$ that tends to 0 for $\delta \to 0$, we obtain $\binom{d+h}{d} \le n^\epsilon$ for any sufficiently small $\delta$.

It remains to consider the case that $\delta \ge c$ for some positive constant $c$ depending only on $\epsilon$. In this case, we have

$$ \binom{d+h}{d} \le \binom{(1+1/c)d}{d} < 2^{(1+1/c)d} = \exp O(d). $$

We turn to (5). Assume that there is a function $g$ such that

$$ \log^d n = n^c g(d). $$

Then choose $b > 1$ and consider $d$ such that $d = b^{-1} \log n$. Then

$$ g(d) \ge \frac{\log^d n}{n^c} = 2^{d \log \log n - c \log n} = 2^{d \log(bd) - cbd} = \exp \Omega(d \log d). $$

Finally for (6), we repeat the argument from [1]. If $d \le \epsilon \log n / \log \log n$ then $\log^d n = 2^{d \log \log n} \le n^\epsilon$. In particular, if $d = o(\log n / \log \log n)$ then $\log^d n = n^{o(1)}$. Moreover, for $d \ge \log^{1/2} n$ we have $\log \log n \le 2 \log d$ and thus $\log^d n = 2^{d \log \log n} \le 4^{d \log d}$. $\blacksquare$

These calculations also show the regimes in which these considerations are at all interesting. For $d = o(\log n / \log \log n)$ then both functions are bounded by $n^{o(1)}$, and the multivariate perspective gives no insight. For $d \ge \log n$, both bounds exceed $n$, and we are better off running $n$ BFSs for computing diameters, or passing through the entire point set for range searching.

## 2.2 Model of computation

We operate in the word RAM, assuming constant-time arithmetic operations on coordinates and edge lengths, as well as constant-time operations in the monoid supported by our range queries. For ease of presentation, edge lengths are assumed to be nonnegative integers; we could work with abstract nonnegative weights instead [6].

# 3 Orthogonal Range Queries

## 3.1 Preliminaries

Let $P$ be a set of $d$-dimensional points. We will view $p \in P$ as a vector $p = (p_1, \dots, p_d)$.

A commutative *monoid* is a set $M$ with an associative and commutative binary operator $\oplus$ with identity. The reader is invited to think of $M$ as the integers with $-\infty$ as identity and $a \oplus b = \max\{a, b\}$.

Let $f: P \to M$ be a function and define for each subset $Q \subseteq P$

$$ f(Q) = \bigoplus \{ f(q) : q \in Q \} $$

with the understanding that $f(\emptyset)$ is the identity in $M$.