text:
\section{Conclusion}
\label{sec:conclusion}

Our main results are the two lower bounds for \textsc{Deletion to $\ncols$-Colorable}\xspace, which apply also to parameterization by treewidth resp.\ cliquewidth but use much more restrictive structure; this greatly refines what was known for \textsc{Odd Cycle Transversal}\xspace, i.e.\ $r=2$, and gives new tight bounds for $r \geq 3$. In particular, beyond the above-mentioned examples, these are further natural problems where a small modulator to a simple graph class (of constant treewidth) is as hard as small treewidth. Surprisingly perhaps, something even stronger holds for clique-width: To get the tight lower bound, a modulator with few (true) twinclasses suffices, i.e., we need neither a sequence of disjoint separators nor complex dense structure. For \textsc{Dominating Set}\xspace, only the latter was established: twinclass-pathwidth rather than cliquewidth suffices to take us from base $3$ in the running time relative to pathwidth to base $4$ being optimal under SETH.

Such results bring several benefits: (1) Rather than e.g.\ getting only the isolated result of (conditional) complexity of a problem relative to treewidth, we get a much larger range of input structure that exhibits the same tight complexity (anything sandwiched between the lower bound structure and treewidth).
(2) At the same time, by aiming for maximally restricted lower bound structure, we get a much better understanding of what structure makes a given problem hard. This in turn helps to focus efforts at faster algorithms through (even) stronger structural restrictions on the input.

An immediate follow-up question is whether there are improved algorithms for \textsc{Deletion to $\ncols$-Colorable}\xspace when $G- X$ has treewidth less than $r$; so far, this is known only for \textsc{Odd Cycle Transversal}\xspace but we think that there are such algorithms in general. We observe that any construction relying on $(r + 1)$-critical graphs, such as we do, must have treewidth at least $r$, hence the treewidth of our construction cannot be improved without fundamentally changing the construction.

Similarly, is there a meaningful restriction of (linear) clique-width, for which Lampis'~\cite{Lampis20} lower bound for $r$-\textsc{Coloring}\xspace already holds? Much more broadly, what other classes of problems exhibit the same lower bound as for treewidth already relative to deletion distance to a sparse graph class? Are there problems where this jump in complexity happens later, say, for treedepth, for some elimination distance, or only for treewidth/pathwidth? E.g., what is the complexity of \textsc{Dominating Set}\xspace relative to deletion distances, and the complexity relative to treedepth may be an interesting stepping stone? Similarly, to what generality do we get the same lower bound as for clique-width already relative to, e.g., twinclass-pathwidth?
\section{Algorithm for Deletion to $r$-Colorable}
\label{sec:cw_algo}

In this section we describe how to solve \textsc{Deletion to $\ncols$-Colorable}\xspace in time $\Oh^*((2^r)^k)$ if we are given a $k$-expression $\mu$ for $G$. We perform bottom-up dynamic programming along the syntax tree $\mathcal{T}_\mu$. We again view \emph{solutions} to \textsc{Deletion to $\ncols$-Colorable}\xspace as functions $\varphi \colon V(G) \rightarrow [r] \cup \{\bot\}$ with the property discussed in the outline, cf.~\cref{sec:outline}.

\begin{thm}
 \label{thm:dtc_algo}
 Given a $k$-expression $\mu$ for $G$, \textsc{Deletion to $\ncols$-Colorable}\xspace on $G$ can be solved in time $\Oh^*((2^r)^k)$.
\end{thm}

\begin{proof}
 Let $(G,b)$ be a \textsc{Deletion to $\ncols$-Colorable}\xspace instance and $\mu$ a $k$-expression for $G$. We can without of loss of generality assume that $\mu$ consists of $\Oh(|V(G)|)$ union-operations and $\Oh(|V(G)|k^2)$ unary operations~\cite{CourcelleO00}. For every node $t \in V(\mathcal{T}_\mu)$ and label $i$, we store the set of colors used on $G^i_t$. After deleting the appropriate vertices, the remaining graph should be $r$-colorable, hence the possible color sets are precisely the subsets of $[r]$, where $\emptyset$ indicates that all vertices are deleted. Since we use at most $k$ labels at every node, this yields $(2^r)^k$ possible types of partial solutions at each node. If the work for each type is only polynomial, then the claimed running time immediately follows, since there are only a polynomial number of nodes in $V(\mathcal{T}_\mu)$.

For every $t \in V(\mathcal{T}_\mu)$ and $f \colon [k] \rightarrow \mathcal{P}([r])$, we consider the set of partial solutions
\begin{align*}
	\mathcal{Q}_t[f] = \{ \varphi \colon V(G_t) \rightarrow [r] \cup \{\bot\} : \,\,& \text{$\varphi$ induces an $r$-coloring of } G_t - {\coloring^{-1}(\del)} \text{ and} \\ & \varphi(V(G^i_t)) \setminus \{\bot\} = f(i) \text{ for all } i \in [k] \}
\end{align*}
and we want to compute the quantity $A_t[f] = \min \{|{\coloring^{-1}(\del)}| : \varphi \in \mathcal{Q}_t[f]\}$. Let $t_0$ be the root node of the $k$-expression $\mu$. We answer yes if there is an $f$ such that $A_{t_0}[f] \leq b$; otherwise we answer no.

The definition of $\mathcal{Q}_t[f]$ implies that $\mathcal{Q}_t[f] = \emptyset$ and $A_t[f] = \infty$ whenever $|f(i)| > |V(G^i_t)|$ for some $i \in [k]$, we will not explicitly mention this edge case again in what follows and assume that the considered $f$ satisfy $|f(i)| \leq |V(G^i_t)|$ for all $i \in [k]$. We proceed by presenting the recurrences to compute $A_t[f]$ for all $t$ and $f$ and afterwards show the correctness of these recurrences.

\paragraph*{Base case.}
If $t = \intro{i}(v)$ for some $i \in [k]$, then $A_t[f] = [f(i) = \emptyset]$.

\paragraph*{Relabel case.}
If $t = \relab{i}{j}{G_{t'}}$ for some $i \neq j \in [k]$ and where $t'$ is the child of $t$, then
\begin{equation*}
	A_t[f] = \min \{ A_{t'}[f'] : f'(a) = f(a) \text{ for all } a \in [k] \setminus \{i,j\} \text{ and } f'(i) \cup f'(j) = f(j) \}.
\end{equation*}
Observe that we are taking the minimum over at most $(2^r)^2 = \Oh(1)$ numbers on the right-hand side, hence this recurrence can be computed in polynomial time.

\paragraph*{Join case.}
If $t = \join{i}{j}{G_{t'}}$ for some $i \neq j \in [k]$, where $t'$ is the child of $t$, and assuming without loss of generality that $V(G^i_{t'}) \neq \emptyset$ and $V(G^j_{t'}) \neq \emptyset$, then
\begin{equation*}
	A_t[f] =
	\begin{cases} A_{t'}[f] & \text{if } f(i) \cap f(j) = \emptyset, \\
									  \infty & \text{else.}
	\end{cases}
\end{equation*}

\paragraph*{Union case.}
If $t = \union{G_{t_1}}{G_{t_2}}$ where $t_1$ and $t_2$ are the children of $t$, then
\begin{equation*}
	A_t[f] = \min \{A_{t_1}[f_1] + A_{t_2}[f_2] : f_1(a) \cup f_2(a) = f(a) \text{ for all } a \in [k]\}.
\end{equation*}
Here, we assume that $\infty + x = x + \infty = \infty + \infty = \infty$ for all $x \in \mathbb{N}$. This recurrence can be computed for all $f$ simultaneously in time $\Oh^*((2^r)^k)$ by turning it into an appropriate cover product in the min-sum semiring as follows. We interpret the functions of the form $f \colon [k] \rightarrow \mathcal{P}([r])$ as subsets of $[k] \times [r]$ in the following way: $S(f) = \{(i,c) : i \in [k], c \in f(i)\}$. Observe that $f_1(a) \cup f_2(a) = f(a) \text{ for all } a \in [k]$ is equivalent to $S(f_1) \cup S(f_2) = S(f)$. Now, $A_t$ can be considered as a function $\mathcal{P}([k] \times [r]) \rightarrow [n]$ and the recurrence of the union case is the $(\min, +)$-cover product of $A_{t_1}$ and $A_{t_2}$. By \cite[Theorem 10.17]{CyganFKLMPPS15} we can compute all values of $A_t$ in time $2^{kr} (kr)^{\Oh(1)} \cdot \Oh(n \log n \log \log n) = \Oh^*((2^r)^k)$.

\paragraph*{Correctness.}
We prove the correctness by bottom-up induction along the syntax tree $\mathcal{T}_\mu$. In the base case $G_t$ only consists of the single vertex $v$ and we can either delete $v$ or assign some color to $v$. Together with the edge case handling, this is implemented by the formula for the base case.

For the relabel case, notice that $G_t = G_{t'}$, $V(G^i_t) = \emptyset$, $V(G^j_t) = V(G^i_{t'}) \cup V(G^j_{t'})$, and $V(G^a_t) = V(G^a_{t'})$ for all $a \in [k] \setminus \{i,j\}$. Let $f'$ be a candidate in the recurrence of $A_t[f]$ and $\varphi' \in \mathcal{Q}_{t'}[f']$ be a minimizer in the definition of $A_{t'}[f']$, then we also have that $\varphi' \in \mathcal{Q}_t[f]$ since $\varphi'(V(G^j_t)) \setminus \{\bot\} = (\varphi'(V(G^i_{t'})) \setminus \{\bot\}) \cup (\varphi'(V(G^j_{t'})) \setminus \{\bot\}) = f'(i) \cup f'(j) = f(j)$. Hence, the recurrence is an upper bound on $A_t[f]$.

In the other direction, let $\varphi$ be a minimizer in the definition of $A_t[f]$ and consider $f'$ with $f'(a) = \varphi(V(G^a_{t'})) \setminus \{\bot\}$ for all $a \in [k]$. Then $f'$ satisfies $f'(i) \cup f'(j) = f(j)$ and $\varphi \in Q_{t'}[f']$, so $f'$ is also considered in the recurrence and the recurrence has to be a lower bound on $A_t[f]$.

For the join case, notice that for $\varphi' \in \mathcal{Q}_{t'}[f] \supseteq \mathcal{Q}_t[f]$ it holds that $\varphi' \in \mathcal{Q}_t[f]$ if and only if $\varphi'(V(G^i_{t'})) \cap \varphi'(V(G^j_{t'})) \subseteq \{\bot\}$.

For the union case, notice that a feasible solution $\varphi$ of $G_t$ induces feasible solutions $\varphi_1$ of $G_{t_1}$ and $\varphi_2$ of $G_{t_2}$ such that $\varphi_1(V(G^a_t)) \cup \varphi_2(V(G^a_t)) = \varphi(V(G^a_t))$ for all $a \in [k]$ and vice versa.
\end{proof}

\section{Lower Bound for Deletion to $r$-colorable}
\label{sec:dtc_lb}

In this section, we prove two tight parameterized lower bounds for \textsc{Deletion to $\ncols$-Colorable}\xspace. Compared to the outline, \cref{sec:outline}, we present the lower bounds in reverse order, i.e., we first present the dense setting in \cref{sec:dtc_lb_cw} and then the sparse setting in \cref{sec:dtc_lb_td}. Since the constructions are so similar, this allows us to give the more complicated proof for the dense setting in full detail, while only discussing the changes needed for the sparse setting. Before presenting the lower bounds, we construct a family of $(r + 1)$-critical graphs in \cref{sec:critical_graphs} that will serve as important gadgets in both lower bound constructions.

\subsection{Construction of Critical Graphs}
\label{sec:critical_graphs}

We say that a graph $G$ is \emph{$t$-critical} if $\chi(G) = t$ and $\chi(G - v) = t - 1$ for all $v \in V(G)$.  The odd cycles form a family of $3$-critical graphs of treewidth $2$ that contains graphs of arbitrarily large size. To obtain a lower bounds for \textsc{Deletion to $\ncols$-Colorable}\xspace with $r > 2$ instead of \textsc{Odd Cycle Transversal}\xspace, we construct a family of $(r + 1)$-critical graphs of treewidth $r$ that also contains graphs of arbitrarily large size.

\begin{thm}
  \label{thm:critical_family}
  Let $r \geq 2$. There exists a family $\mathcal{H}^r$ of graphs such that
  \begin{itemize}
    \item $H$ is $(r + 1)$-critical for all $H \in \mathcal{H}^r$,
    \item $\pw(H) = \tw(H) = r$ for all $H \in \mathcal{H}^r$,
    \item for every $s \in \mathbb{N}$, there exists a graph $H \in \mathcal{H}^r$ with $s \leq |V(H)| \leq s + r$.
  \end{itemize}
\end{thm}

\begin{dfn}[\cite{Diestel12, Hajos61}]
  Given two graphs $G$ and $H$ and edges $\{v,w\} \in E(G)$ and $\{x, y\} \in E(H)$. We obtain a graph $G' = (V', E')$ by applying \emph{Hajós' construction}, where $V' = (V(G) \cup V(H) \cup \{s\}) \setminus \{v, x\}$ and $E' = E(G - v) \cup E(H - x) \cup \{\{s,u\} : \{v,w\} \neq \{v,u\} \in E(G)\} \cup \{\{s,u\} : \{x,y\} \neq \{x,u\} \in E(H)\} \cup \{w, y\}$. That is, we remove the edges $\{v,w\}$ and $\{x,y\}$, identify $v$ and $x$ into a single vertex called $s$, and add the edge $\{w,y\}$.
\end{dfn}

\begin{dfn}[\cite{Diestel12, Hajos61}]
  Let $t \geq 3$. A graph $G = (V, E)$ is \emph{$t$-constructible} if it can be constructed from the following operations, starting with $K_t$:
  \begin{itemize}

    \item Let $G$ and $H$ be $t$-constructible graphs, then the graph obtained by applying Hajós' construction to $G$ and $H$ (wrt.\ edges $\{v,w\} \in E(G)$ and $\{x,y\} \in E(H)$) is $t$-constructible.
    \item Let $G$ be a $t$-constructible graph and $u$ and $v$ two non-adjacent vertices in $G$. The graph formed by adding the edge $\{u,v\}$ to $G$ and then contracting $\{u, v\}$ is $t$-constructible.
  \end{itemize}
\end{dfn}

\begin{lem}[\cite{Diestel12, Hajos61}]
  \label{thm:constructible_chromatic}
  Every $t$-constructible graph $G$ requires at least $t$ colors, i.e. $\chi(G) \geq t$.
\end{lem}

\begin{figure}[h]
  \centering
  \tikzfig{pictures/critical}
  \caption{The graphs $H^4_2, H^4_3, H^5_2, H^5_3$ and the vertex labels of $H^5_3$.}
  \label{fig:critical_graphs}
\end{figure}

We set $H_1^t = K_t$ with vertex labels $V(H_1^t) = \{a_1, a'_1, b_1, c_{1, 1}, c_{1, 2}, \ldots, c_{1, t - 3}\}$. For $\gamma \geq 2$, we obtain $H_\gamma^t$ by performing Hajós' construction on $H_{\gamma - 1}^t$ and $K_t$, where we label the vertices of $K_t$ by $a_\gamma, a'_\gamma, b_\gamma, c_{\gamma, 1}, c_{\gamma, 2}, \ldots, c_{\gamma, t - 3}$, with respect to the edges $\{b_{\gamma - 1}, a'_{\gamma - 1}\} \in E(H_{\gamma - 1}^t)$ and $\{a_\gamma, b_\gamma\} \in E(K_t)$ and identifying $a'_{\gamma - 1}$ with $a_\gamma$. Having finished the construction, we will not require the $a'$-labels anymore, in $H_\gamma^t$ we  set $a_{\gamma + 1} = a'_\gamma$, see \cref{fig:critical_graphs}.

We define $\mathcal{H}^{t - 1} = \{H^t_\gamma : \gamma \in \mathbb{N}\}$ for $t \geq 3$. Observe that for $t = 3$ we obtain exactly the odd cycles. We establish the following properties of the graphs $H^t_\gamma$ which directly implies \cref{thm:critical_family}.

\begin{lem}[]
  \label{thm:critical_properties}
  The graphs $H^t_\gamma$, $t \geq 3$, $\gamma \in \mathbb{N}$, have the following properties:
  \begin{align*}
    \textbf{1. } |V(H^t_\gamma)| = (t - 1) \gamma + 1. && \textbf{2. } H^t_\gamma \text{ is $t$-critical.} && \textbf{3. } \pw(H^t_\gamma) = \tw(H^t_\gamma) = t - 1.
  \end{align*}
\end{lem}

\begin{proof}
  Property 1 can be easily shown by induction over $\gamma$. Now, we can prove that $H^t_\gamma$ is $t$-critical. By \cref{thm:constructible_chromatic} we have that $\chi(H^t_\gamma) \geq t$. Let $v \in V(H^t_\gamma)$ be arbitrary. We have to show that $\chi(H^t_\gamma - v) \leq t - 1$. We distinguish whether $v$ is labeled by $a$, $b$, or $c$, see \cref{fig:critical_coloring}.

  \begin{figure}[h]
    \centering
    \tikzfig{pictures/critical_coloring}
    \caption{The three coloring cases in the proof of \cref{thm:critical_properties} for the graph $H^5_4$.}
    \label{fig:critical_coloring}
  \end{figure}

  \textbf{Case $v = a_i$, $i \in [\gamma + 1]$:} We construct a proper $(t-1)$-coloring $\varphi \colon V(H^t_\gamma - v) \rightarrow [t-1]$. For $\ell \in [\gamma]$, set $\varphi(b_\ell) = (\ell \mod 2) + 1$. For $\ell \in [\gamma + 1]$, set $\varphi(a_\ell) = (\ell + 1 \mod 2) + 1$ if $\ell < i$ and set $\varphi(a_\ell) = (\ell \mod 2) + 1$ if $\ell > i$. For $\ell \in [\gamma]$ and $k \in [t - 3]$, set $\varphi(c_{\ell,k}) = k + 2$. Now, for all $\ell \in [\gamma]$, the $(t-1)$-clique induced by $a_\ell, a_{\ell+1}, c_{\ell,1}, \ldots, c_{\ell,t-3}$ is colored properly and the graph induced by $N[b_\ell]$ is colored properly. Since these cover all edges, $\varphi$ must be a proper coloring.

  \textbf{Case $v = b_i$, $i \in [\gamma]$:} Again, we construct a proper $(t-1)$-coloring $\varphi$. For $\ell \in [\gamma]$, set $\varphi(b_\ell) = (\ell \mod 2) + 1$ if $\ell < i$ and set $\varphi(b_\ell) = (\ell + 1 \mod 2) + 1$ if $\ell > i$. For $\ell \in [\gamma + 1]$, set $\varphi(a_\ell) = (\ell + 1 \mod 2) + 1$. For $\ell \in [\gamma]$ and $k \in [t-3]$, set $\varphi(c_{\ell, k}) = k + 2$. Similarly to the previous case, $\varphi$ must be a proper coloring.

  \textbf{Case $v = c_{i,k}$, $i \in [\gamma]$, $k \in [t-3]$:} We construct a proper $(t-1)$-coloring $\varphi$ as follows. We set $\varphi(b_i) = k + 2$. For $\ell \in [\gamma] \setminus \{i\}$, set $\varphi(b_\ell) = (\ell \mod 2) + 1$ if $\ell < i$ and set $\varphi(b_\ell) = (\ell + 1 \mod 2) + 1$ if $\ell > i$. For $\ell \in [\gamma + 1]$, set $\varphi(a_\ell) = (\ell + 1 \mod 2) + 1$. For $(\ell, k') \in ([\gamma] \times [t - 3]) \setminus \{(i,k)\}$, set $\varphi(c_{\ell,k'}) = k' + 2$. Again, like in the previous cases, $\varphi$ must be a proper coloring.

  This shows that $H^t_\gamma$ is $t$-critical. We proceed by showing that $\pw(H^t_\gamma) = \tw(H^t_\gamma) = t - 1$. Note that by contracting all vertices in $V(H^t_\gamma) \setminus \{a_1, a_2, b_1, c_{1, 1}, \ldots, c_{1, t-3}\}$ into $b_1$, we obtain $K_t$ and hence $\pw(G) \geq \tw(G) \geq \tw(K_t) = t - 1$, as treewidth is a minor-monotone parameter. For the other direction, we construct a path decomposition $\TT$ of width $t - 1$. Let $\TT$ be the path on  $2\gamma - 1$ vertices denoted by $w_1, \ldots, w_{2\gamma - 1}$. For $\ell \in [\gamma]$, we define the bag $\mathbb{B}_{w_{2\ell - 1}} = \{a_\ell, a_{\ell + 1}, b_\ell, c_{\ell, 1}, c_{\ell, 2}, \ldots, c_{\ell, t - 3}\}$ and for $\ell \in [\gamma - 1]$, we define the bag $\mathbb{B}_{w_{2\ell}} = \{b_\ell, b_{\ell + 1}, a_{\ell + 1}\}$. This yields a path decomposition of width $t - 1$ and hence establishes property 3.
\end{proof}

\subsection{Dense Setting}
\label{sec:dtc_lb_cw}

We again view \emph{solutions} to \textsc{Deletion to $\ncols$-Colorable}\xspace as functions $\varphi \colon V(G) \rightarrow [r] \cup \{\bot\}$ with the property discussed in the outline, cf.~\cref{sec:outline}.

We will prove a lower bound for \textsc{Deletion to $\ncols$-Colorable}\xspace parameterized by the size of a twinclass-modulator (TCM) to treewidth $r$. This implies a lower bound for parameterization by twinclass-treedepth due to \cref{thm:tcm_tctd}. By \cref{thm:hierarchy_cliquewidth}, this further extends to lower bounds for parameterization by twinclass-pathwidth and clique-width. Hence, we will see that the running time of the algorithm from \cref{thm:dtc_algo} is tight, unless SETH\xspace is false.

\begin{thm}
  \label{thm:dtc_lower_bound}
  If \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((2^{r} - \varepsilon)^{|\mathcal{X}|})$ for some $r \geq 2$ and $\varepsilon > 0$, where $\mathcal{X}$ is a TCM to treewidth $r$, then SETH\xspace is false.
\end{thm}

Assume that we can solve \textsc{Deletion to $\ncols$-Colorable}\xspace in time $\Oh^*((2^r - \varepsilon)^{|\mathcal{X}|})$ for some $r \geq 2$ and $\varepsilon > 0$. For all clause sizes $q$, we provide a reduction from $q$-\textsc{Satisfiability}\xspace with $n$ variables to $\textsc{Deletion to $\ncols$-Colorable}\xspace$ with a TCM to treewidth $r$ of size approximately $n \log_{2^r}(2) = n / r$ to convert from base $2^r$ to base $2$. Combining this reduction with the assumed faster algorithm will imply a faster algorithm for $q$-\textsc{Satisfiability}\xspace, thus violating SETH\xspace. From now on, we consider $r$ to be fixed.

Before we begin with the actual construction, we describe several gadgets that will be important.

\begin{figure}
 \centering
 \tikzfig{pictures/dtc_deletion_edge}
 \caption{A deletion edge between $u$ and $v$ for $r = 2$ and $r = 3$.}
 \label{fig:dtc_del_edge}
\end{figure}

\subparagraph*{Deletion edges.} Let $u$ and $v$ be two vertices. By adding a \emph{deletion edge} between $u$ and $v$, we mean adding $r - 1$ vertices $w_1, \ldots, w_{r - 1}$ and edges so that $\{u,v,w_1,w_2, \ldots, w_{r - 1}\}$ is a clique of size $r - 1$, see \cref{fig:dtc_del_edge}. The vertices $w_1, \ldots, w_{r - 1}$ will not receive any further incident edges. Therefore, any solution to \textsc{Deletion to $\ncols$-Colorable}\xspace has to delete at least one vertex in this clique and we can assume that the deleted vertex is $u$ or $v$.

\subparagraph*{Arrows.} Our construction relies on being able to propagate deletions throughout the graph. This is done via so-called \emph{arrows}. We distinguish between two types of arrows, namely \emph{thin arrows} and \emph{thick arrows}. Thin arrows arise already in the sparse setting of the lower bound construction of Lokshtanov et al.~\cite{LokshtanovMS18} for the restricted case of $r = 2$, i.e., \textsc{Odd Cycle Transversal}\xspace parameterized by pathwidth. A thin arrow simply propagates a deletion from a single vertex to another vertex. Whereas the newly introduced thick arrows propagate a deletion to a single vertex only if sufficiently many vertices have been deleted in some true twinclass of size $r$. The construction of thick arrows is described in the proof of \cref{thm:arrow_behavior}.

Let us proceed with the construction of thin arrows. Given two single vertices $u$ and $v$, \emph{adding a thin arrow} from $u$ to $v$ means adding a new vertex $w$ and a deletion edge between $u$ and $w$ and a deletion edge between $w$ and $v$. We remark that, compared to the construction of Lokshtanov et al.~\cite{LokshtanovMS18}, we have shortened the thin arrows. The construction of thin arrows is symmetric, but the direction will be important later for the description of a packing that witnesses a lower bound on the required budget. The idea is that when $u$ is not deleted, we delete $w$ to resolve both deletion edges; when $u$ is deleted, the first deletion edge is resolved and we can afford to delete $v$ to resolve the second deletion edge. The former is called the \emph{passive} solution of the thin arrow and the latter is the \emph{active} solution. Using exchange arguments, one can see that it is sufficient to only consider solutions that on each thin arrow use either the passive solution or active solution.

\begin{lem}
  \label{thm:arrow_behavior}
  Let $U$ be a set of $r$ true twins and $v$ be a vertex that is not adjacent to $U$ and $\ell \in [r]$. There is a graph $A = A_\ell(U,v)$ with the following properties:
  \begin{itemize}
   \item Any solution $\varphi$ satisfies $|V(A - U) \cap {\coloring^{-1}(\del)}| \geq \ell$.
   \item If $|V(A - U) \cap {\coloring^{-1}(\del)}| = \ell$, then $\varphi(v) = \bot$ implies that $|U \cap {\coloring^{-1}(\del)}| \geq \ell$.
   \item Any solution $\tilde{\varphi}$ for $\tilde{G} = G[(V \setminus V(A)) \cup U \cup \{v\}]$ with $\tilde{\varphi}(v) \neq \bot$ or $|U \cap \tilde{\varphi}^{-1}(\bot)| \geq \ell$ can be extended to a solution $\varphi$ for $G$ with $|V(A - U) \cap {\coloring^{-1}(\del)}| = \ell$.
   \item $\tw(A - U) \leq r$ via a winning cops-and-robber-strategy starting with a cop on $v$.
  \end{itemize}
\end{lem}

\begin{figure}
 \centering
 \tikzfig{pictures/dtc_arrow}
 \caption{The construction of a thick $\ell$-arrow $A_\ell(U,v)$. The double-lined edges represent deletion edges. An edge attached to a circle or ellipse represents a \emph{join}, i.e., a bundle of edges.}
 \label{fig:dtc_arrow}
\end{figure}

\begin{proof}
  The graph $A = A_\ell(U,v)$ is constructed by adding a clique $K_\ell$ on $\ell$ vertices, a clique $K_{r - \ell}$ on $r - \ell$ vertices, an independent set $I_{\ell - 1}$ on $\ell - 1$ vertices and adding all edges between $U$ and $K_\ell$, all edges between $K_\ell$ and $K_{r - \ell}$, all edges between $K_\ell$ and $v$, and a deletion edge between each vertex of $K_\ell$ and each vertex of $I_{\ell - 1}$, cf.\ \cref{fig:dtc_arrow}. Observe that the $K_\ell$, $K_{r - \ell}$, and $v$ together form a clique of size $r + 1$. Only $U$ and $v$ can have further incident edges.

  We first show that any solution $\varphi$ has to delete at least $\ell$ vertices in $A - U$. Suppose that no deletion occurs in $K_\ell$, then $\ell - 1$ disjoint deletion edges between $K_\ell$ and $I_{\ell - 1}$ remain and at least one deletion has to occur in $K_{r - \ell} \cup \{v\}$. On the other hand, suppose that $1 \leq d \leq \ell$ deletions occur in $K_\ell$, then $\ell - d$ disjoint deletion edges between $K_\ell$ and $I_{\ell - 1}$ remain. In either case, we must delete at least $\ell$ vertices.

  Next, we argue that a solution $\varphi$ deleting exactly $\ell$ vertices in $A - U$ cannot delete $v$ if less than $\ell$ deletions occur in $U$. Suppose that $d < \ell$ deletions occur in $U$, then at least $\ell - d \geq 1$ deletions must occur in $K_\ell$, because $U$ and $K_\ell$ together form a clique of size $r + \ell$. Let $d' \geq 1$ be the number of deletions in $K_\ell$, then like in the previous paragraph $\ell - d'$ disjoint deletion edges between $K_\ell$ and $I_{\ell - 1}$ remain. Hence, we must already perform a total of $\ell$ deletions in $K_\ell$ and the deletion edges, so $v$ cannot be deleted.

  Consider any solution $\tilde{\varphi}$ for $\tilde{G}$. If $\tilde{\varphi}(v) \neq \bot$, then we can extend $\tilde{\varphi}$ to a solution $\varphi$ for $G$ by deleting $K_\ell$ completely. This deletes all edges between $U$ and $A$ and one endpoint of each deletion edge. The $K_{r - \ell}$ is only attached to $v$ and can always be properly colored. We give all vertices in $I_{\ell - 1}$ the same color and the cliques attached to $I_{\ell - 1}$ due to the deletion edges are all disjoint and of size $r - 1$ each, so they can be properly colored as well. Hence, $\varphi$ is a valid solution for $G$.

  If $|U \cap \tilde{\varphi}^{-1}(\bot)| \geq \ell$ and $\tilde{\varphi}(v) = \bot$, then we can extend $\tilde{\varphi}$ to a solution $\varphi$ for $G$ by deleting $I_{\ell - 1}$ completely. To $K_\ell$ we assign a subset of the colors $[r] \setminus \tilde{\varphi}(U)$, this is possible since at least $\ell$ deletions occur in $U$. The $K_\ell$ and $K_{r - \ell}$ together form a clique of size $r$ that we can properly color. The cliques of the deletion edges are all disjoint as before and only attached to $K_\ell$ and have size $r - 1$ each, hence they can also be properly colored. Hence, $\varphi$ is a valid solution for $G$.

  Finally, we argue that $\tw(A - U) \leq r$ using the omniscient cops-and-robber-game. We begin by placing $r + 1$ cops on $K_\ell \cup K_{r - \ell} \cup \{v\}$, then we remove the $r - \ell + 1$ cops on $K_{r - \ell} \cup \{v\}$. Now, all remaining connected components correspond to a vertex of $I_{\ell - 1}$. Fix the component the robber escaped to and place one cop on the corresponding vertex of $I_{\ell - 1}$. Now, the robber must have escaped to the inside of some deletion edge between $K_\ell$ and $I_{\ell - 1}$. We remove the $\ell - 1$ cops from $K_\ell$ that are not on the endpoint of this deletion edge. Finally, we place $r - 1$ cops on the remaining vertices of the deletion edge and capture the robber. Throughout the strategy, we have never placed more than $r + 1$ cops simultaneously and hence the claimed treewidth bound holds by \cref{thm:cops_robber}.
\end{proof}

Similarly to the thin arrows, we say that a thick $\ell$-arrow $A_\ell(U,v)$ is \emph{active} if the considered solution $\varphi$ satisfies $|U \cap {\coloring^{-1}(\del)}| \geq \ell$ and hence \cref{thm:arrow_behavior} allows us to assume that $\varphi(v) = \bot$; otherwise, we say that $A_\ell(U,v)$ is \emph{passive}.

\subparagraph*{Construction setup.} We will now begin with the construction of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance. Consider a $q$-\textsc{Satisfiability}\xspace instance $\sigma$ with $n$ variables and $m$ clauses. We enumerate the clauses and simply refer to them by their number. Depending only on $\varepsilon$ and $r$, we will choose an integer ${p_0}$; we will describe how to choose ${p_0}$ later. We partition the variables of $\sigma$ into groups of size at most ${p_0}$, resulting in $t = \lceil n / {p_0} \rceil$ groups which will be indexed by $i$. Next, we choose the smallest integer $p$ such that $p$ is divisible by $2^{r}$ and $(2^{r})^{p} \frac{(2^{r} - 1)!}{2^{(2^r)}} p^{-(2^r)} \geq 2^{p_0}$.

Usually, a simple base conversion from a base that is a power of $2$ to base $2$ allows for a construction where the handling of groups is a lot less technical. Unfortunately, since we require the trick of Cygan et al.~\cite{CyganDLMNOPSW16} that enlarges the groups, this is not possible here. We will now describe the construction of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $G = G(\sigma, r, {p_0})$.

\subparagraph*{Central twinclasses.} The central vertices of $G$ will form the TCM to treewidth $r$. For each variable group $i \in [t]$, we create a set $\mathcal{U}_i \subseteq \Pi_{tc}(G)$ consisting of $p$ true twinclasses of size $r$ each; there are no edges between the different twinclasses.  The partial solution induced by a solution $\varphi$ of \textsc{Deletion to $\ncols$-Colorable}\xspace on the twinclasses in $\mathcal{U}_i$ will correspond to a truth assignment for the $i$-th variable group.

\subparagraph*{Central clique.} We create a clique $F = \{f_1, \ldots, f_r\}$ on $r$ vertices. The clique $F$ also belongs to the central part. We remark that the vertices of $F$ will not be twins; each vertex of $F$ has its own twinclass.  This concludes the construction of the central part which will form the modulator $\mathcal{X}$.

Our construction will ensure that no vertex of $F$ can be deleted, but we will only be able to prove this later. This allows us to use $F$ to simulate \textsc{List Coloring}\xspace constraints, i.e., we can forbid specific colors at a vertex. To do so, we normalize the considered solutions by assuming that $\varphi(f_s) = s$ for all $s \in [r]$ and then no vertex $v$ adjacent to some $f_s$ can receive color $s$. We say that a solution $\varphi$ is \emph{normalized} if $F \cap {\coloring^{-1}(\del)} = \emptyset$ and $\varphi(f_s) = s$ for all $s \in [r]$.

We mention here that in principle a twinclass-modulator could contain arbitrarily large twinclasses. In our case, every twinclass has size at most $r = \Oh(1)$, so the number $|\bigcup(\mathcal{X})|$ of vertices in $\mathcal{X}$ is linear in the size $|\mathcal{X}|$ of $\mathcal{X}$.

\subparagraph*{Budget.} The budget $b = \mathrm{cost}_\mathcal{P} + t r p / 2$ for the \textsc{Deletion to $\ncols$-Colorable}\xspace instance is split into two parts. The first part $\mathrm{cost}_\mathcal{P}$ is due to a vertex-disjoint packing $\mathcal{P}$ of subgraphs that will be described later and the second part $t r p / 2$ is allocated to the vertices in the twinclass-modulator.

\subparagraph*{Partial solution structure.}
We want to ensure that under our budget restriction no vertex of $F$ can be deleted, as otherwise the simulation of \textsc{List Coloring}\xspace constraints will not work. This entails that all considered solutions should perform the same number of deletions. On the gadgets that will be attached to the central vertices, this does not pose a big issue. However, it does on the central vertices: to obtain the desired lower bound, for each true twinclass $U \in \mathcal{U}$ and solution $\varphi$, it should in principle be possible for $\varphi(U)$ to attain every subset of $[r]$, so that we have $2^r$ states per twinclass. However, the number of deletions in $U$ depends on $|\varphi(U)|$. We can partition the possible states into different \emph{levels} depending on the number $\ell$ of deletions they incur in the true twinclass. A state can incur any number of deletions between $0$ and $r$.

Using slightly larger groups like Cygan et al.~\cite{CyganDLMNOPSW16} allows us to overcome these issues. By using slightly more twinclasses per variable group $i \in [t]$ than necessitated by the base conversion, we can consider solutions with a special structure on the central vertices. It is designed in such a way that all solutions obeying this structure incur the same number of deletions on the central vertices while still allowing all states to appear the same number of times. Due to the slight increase in the number of twinclasses, we can still encode sufficiently many truth assignments into such structured solutions.

For every $i \in [t]$, $U \in \mathcal{U}_i$, $C \subseteq [r]$, we fix some representative solution $\varphi_{i,U,C} \colon U \rightarrow [r] \cup \{\bot\}$ to \textsc{Deletion to $\ncols$-Colorable}\xspace on $U$ with $\varphi_{i,U,C}(U) \setminus \{\bot\} = C$. The point of this is that we only distinguish between different solutions $\varphi$ based on the sets $\varphi(U)$, $U \in \mathcal{U}_i$, and not based on the actual mappings $\varphi\big|_U$, $U \in \mathcal{U}_i$. Since there are exactly $\binom{r}{r - \ell} = \binom{r}{\ell}$ states that incur exactly $\ell$ deletions each and we want to allow for the possibility of all states appearing the same number of times, we arrive at the following definition for each group $i \in [t]$:
\begin{align*}
  \Phi_i = \{\varphi \colon \bigcup(\mathcal{U}_i) \rightarrow [r] \cup \{\bot\} : \, \, & \varphi \text{ is a solution of \textsc{Deletion to $\ncols$-Colorable}\xspace on $\bigcup(\mathcal{U}_i)$} \\
& \text{ with } \varphi\big|_U \equiv \varphi_{i,U,\varphi(U) \setminus \{\bot\}} \text{ for all } U \in \mathcal{U}_i \text{ and } \\
& \left|\left\{U \in \mathcal{U}_i : \varphi(U) \setminus \{\bot\} \in \binom{[r]}{\ell}\right\}\right| = \binom{r}{\ell} \frac{p}{2^{r}} \text{ for all } \ell = 0, \ldots, r \}.
\end{align*}
Informally, this means that we only consider partial solutions that pick a representative solution on each twinclass in $\mathcal{U}_i$ and for every level $\ell \in \{0\} \cup [r]$, i.e., a possible number of deletions, there is a fixed number $\binom{r}{\ell} \frac{p}{2^r}$ of twinclasses in $\mathcal{U}_i$ where the partial solution attains a state of level $\ell$. \cref{thm:scoloring_deletions} gives the total number of deletions for a partial solution $\varphi_i \in \Phi_i$ and \cref{thm:scolorings_bound} studies the size of $\Phi_i$.

\begin{lem}
  \label{thm:scoloring_deletions}
  If $\varphi \in \Phi_i$, then $|{\coloring^{-1}(\del)}| = r p / 2$.
\end{lem}

\begin{proof}
  \begin{equation*}
    |{\coloring^{-1}(\del)}| = \sum_{\ell = 0}^r (r - \ell) \binom{r}{\ell} \frac{p}{2^r}
    = \frac{p}{2^r} r \sum_{\ell = 0}^{r - 1} \binom{r - 1}{\ell}
    = \frac{p}{2^r} r 2^{r - 1}
    = r p / 2. \qedhere
  \end{equation*}
\end{proof}

\begin{lem}
 \label{thm:scolorings_bound}
  If $p \geq 2^{r}$, then we have that $|\Phi_i| \geq (2^{r})^{p} \frac{(2^{r} - 1)!}{2^{(2^r)}} p^{-(2^r)}$.
\end{lem}

\begin{proof}
  Observe that $\left|\left\{\varphi \in \Phi_i : \left|\left\{U \in \mathcal{U}_i : \varphi(U) \setminus \{\bot\} = C\right\}\right| = \frac{p}{2^{r}} \text{ for all } C \subseteq [r]\right\}\right| = \binom{p}{\frac{p}{2^{r}}, \ldots, \frac{p}{2^{r}}} = x$, where $x$ is the central multinomial coefficient. The central multinomial coefficient $x$ is a maximum of the function $(c_1, \ldots, c_{2^{r}}) \mapsto \binom{p}{c_1, \ldots, c_{2^{r}}}$. Hence, $x$ is a maximum term in the sum of the multinomial theorem, i.e., $(2^r)^p = \sum_{c_1 + \cdots + c_{2^r} = p} \binom{p}{c_1, \ldots, c_r}$. The number of terms in the sum of the multinomial theorem is the number of weak compositions of $p$ into $2^{r}$ parts which is $\binom{p + 2^{r} - 1}{p}$. Bounding this term from above using $p \geq 2^{r}$, we obtain
  \begin{equation*}
    \binom{p + 2^{r} - 1}{p}
    = \frac{1}{(2^{r} - 1)!} (p + 1) \cdots (p + 2^{r} - 1)
    \leq \frac{1}{(2^{r} - 1)!} (2p)^{(2^{r})} = \frac{2^{2^r}}{(2^{r} - 1)!} p^{(2^r)}.
  \end{equation*}
By the multinomial theorem, we hence obtain that
  \begin{equation*}
    |\Phi_i| \geq x \geq (2^{r})^{p} \frac{(2^{r} - 1)!}{2^{(2^r)}} p^{-(2^r)}. \qedhere
  \end{equation*}
\end{proof}

Hence, if we choose $p$ as discussed previously, then we can pick for each group $i \in [t]$ an efficiently computable injective mapping $\kappa_i \colon \{0,1\}^{{p_0}} \rightarrow \Phi_i$ that maps truth assignments of the $i$-th variable group to partial solutions on $\mathcal{U}_i$ with the desired structure.

\subparagraph*{Structure gadgets.} We proceed by constructing the \emph{structure gadgets} which enforce that the partial solution on $\mathcal{U}_i$ belongs to $\Phi_i$. For every group $i \in [t]$, number of deletions $\ell \in [r]$, set of twinclasses $\mathcal{S} \subseteq \mathcal{U}_i$ with $|\mathcal{S}| = \binom{r}{\geq (r - \ell + 1)}\frac{p}{2^{r}} + 1$, we add an $(r + 1)$-critical graph $L_{i, \ell, \mathcal{S}} \in \mathcal{H}^r$ consisting of at least $|\mathcal{S}|$ vertices. For every $U \in \mathcal{S}$, we pick a private vertex $v$ in $L_{i, \ell, \mathcal{S}}$ and add the thick $\ell$-arrow $A_\ell(U,v)$. We create $1 + t r p / 2 = 1 + (b - \mathrm{cost}_\mathcal{P})$ copies of $L_{i, \ell, \mathcal{S}}$ and the incident thick arrows. This concludes the construction of the structure gadget.

Due to our budget constraint, no solution will be able to perform too many deletions in the central vertices. The idea of the structure gadget is that if a solution $\varphi$ performs too few deletions in the twinclasses of $\mathcal{U}_i$, then we can find an $\ell$ and an $\mathcal{S} \subseteq \mathcal{U}_i$ with $|\mathcal{S}| = \binom{r}{\geq (r - \ell + 1)}\frac{p}{2^{r}} + 1$ such that $\varphi$ deletes less than $\ell$ vertices in each $U \in \mathcal{S}$. Hence, all thick $\ell$-arrows leading to $L_{i, \ell, \mathcal{S}}$ and its copies have to be passive. To resolve all these $(r + 1)$-critical graphs, we have to spend one extra unit of budget per copy which is not accounted for by the packing. Due to the large number of copies, this implies that we must violate our budget constraint.

\subparagraph{Color-set-gadgets.} The next step is to construct gadgets that can distinguish between the different partial solutions in $\Phi_i$. To do so, these gadgets must be able to react not only based on the number of deletions inside a twinclass, but also based on the set of colors used for a twinclass. In \cref{thm:decode_behavior}, we construct \emph{color-set-gadgets} $B_C(U,v)$ using \textsc{List Coloring}\xspace constraints simulated by the central clique $F$. Given a solution $\varphi$ and a set of colors $C \subsetneq [r]$, the color-set-gadget $B_C(U,v)$ propagates a deletion to the vertex $v$ when the set of colors $\varphi(U) \setminus \{\bot\}$ used on a set of true twins $U$ is a subset of $C$, i.e., $\varphi(U) \setminus \{\bot\} \subseteq C$. Similar to the arrows, we say that $B_C(U,v)$ is \emph{active} if a deletion is propagated to $v$ and \emph{passive} otherwise.

\newcommand{{\overline{c}}}{{\overline{c}}}

\begin{figure}
 \centering
 \tikzfig{pictures/dtc_decode}
 \caption{The construction of a color-set-gadget $B_C(U,v)$ with $[r] \setminus C = \{{\overline{c}}_1, \ldots, {\overline{c}}_\ell\}$. The double-lined edges represent deletion edges. An edge attached to a circle or ellipse represents a \emph{join}, i.e., a bundle of edges. The sets depict the allowed states at a vertex.}
 \label{fig:dtc_color_set}
\end{figure}

\begin{lem}
  \label{thm:decode_behavior}
  Let $U$ be a set consisting of at most $r$ true twins and $v$ be a vertex that is not adjacent to $U$ and let $C \subsetneq [r]$ with $|C| \leq |U|$. There is a graph $B = B_C(U,v)$ with the following properties:
  \begin{itemize}
   \item Any solution $\varphi$, also unnormalized ones, satisfies $|V(B - U) \cap {\coloring^{-1}(\del)}| \geq (r - |C|) + 1$.
   \item If $\varphi$ is a normalized solution with $|V(B - U) \cap {\coloring^{-1}(\del)}| = (r - |C|) + 1$, then $\varphi(v) = \bot$ implies that $\varphi(U) \setminus \{\bot\} \subseteq C$.
   \item Any normalized solution $\tilde{\varphi}$ for $\tilde{G} = G[(V \setminus V(B)) \cup U \cup \{v\}]$ with $\tilde{\varphi}(v) \neq \bot$ or $\tilde{\varphi}(U) \setminus \{\bot\} \subseteq C$ can be extended to a normalized solution $\varphi$ for $G$ with $|V(B - U) \cap {\coloring^{-1}(\del)}| = (r - |C|) + 1$.
   \item $\tw(B - U) \leq r$ via a winning cops-and-robber-strategy starting with a cop on $v$.
  \end{itemize}
\end{lem}

\begin{proof}
  Let $[r] \setminus C = \{{\overline{c}}_1, \ldots, {\overline{c}}_\ell\}$. We add $2\ell + 1$ vertices $w_1, \ldots, w_{2\ell + 1}$ and add all edges between $w_{2i - 1}$, $i \in [\ell]$, and $U$, all edges between $w_{2i}$, $i \in [\ell]$, and $w_{2\ell + 1}$, a deletion edge between $w_{2\ell + 1}$ and $v$ and a deletion edge between each pair $w_{2i - 1}$ and $w_{2i}$ for $i \in [\ell]$. We also add all edges between $\{w_{2i} : i \in [\ell]\} \cup \{w_{2\ell + 1}\}$ and $F \setminus \{f_1\}$. Finally, for each $i \in [\ell]$, vertex $w_{2i - 1}$ is adjacent to all vertices in $F \setminus \{f_{{\overline{c}}_i}\}$. Hence, considering a normalized solution, the vertices in $\{w_{2i} : i \in [\ell]\} \cup \{w_{2\ell + 1}\}$ may only receive color $1$ or be deleted and vertex $w_{2i - 1}$, $i \in [\ell]$, may only receive color ${\overline{c}}_i$ or be deleted. See \cref{fig:dtc_color_set} for a depiction of the construction.

  The lower bound on the number of deletions for possibly unnormalized solutions follows by noticing that $B - U$ contains $\ell + 1 = (r - |C|) + 1$ disjoint deletion edges.

  Suppose that $\varphi$ is a normalized solution with $|V(B - U) \cap {\coloring^{-1}(\del)}| = \ell + 1$ and $\varphi(U) \setminus \{\bot\} \not\subseteq C$, then there exists some ${\overline{c}}_i \in ([r] \setminus C) \cap \varphi(U)$. Due to the constraints enforced by $F$, we must have that $\varphi(w_{2i - 1}) = \bot$ and $\varphi(w_{2i}) = 1$ by the bound on the number of deletions. This in turn forces $\varphi(w_{2\ell + 1}) = \bot$ and hence $v$ cannot be deleted without violating the deletion bound.

  Suppose that $\tilde{\varphi}$ is a normalized solution of $\tilde{G}$ with $\tilde{\varphi}(v) \neq \bot$, then we can extend to a normalized solution $\varphi$ of $G$ by deleting all vertices in $\{w_{2i - 1} : i \in [\ell]\} \cup \{w_{2\ell + 1}\}$. It is easy to see that the remainder can be colored correctly.

  Suppose that $\tilde{\varphi}$ is a normalized solution of $\tilde{G}$ with $\tilde{\varphi}(U) \setminus \{\bot\} \subseteq C$ and $\tilde{\varphi}(v) = \bot$. Since $([r] \setminus C) \cap \tilde{\varphi}(U) = \emptyset$, we can extend $\tilde{\varphi}$ to a normalized solution $\varphi$ of $G$ by setting $\varphi(w_{2i - 1}) = {\overline{c}}_i$, $\varphi(w_{2i}) = \bot$ for all $i \in [\ell]$, and $\varphi(w_{2\ell + 1}) = 1$. It is easy to see that the remainder can be colored correctly.

  We argue that $\tw(B - U) \leq r$ using the omniscient cops-and-robber-game. We begin by placing cops on $v$ and $w_{2\ell + 1}$. This splits the graph into $\ell + 1$ connected components, one per deletion edge. We place two cops on the endpoints of the deletion edge the robber escaped to. If $v$ or respectively $w_{2\ell + 1}$ is not an endpoint of the considered deletion edge, then we remove the cop from $v$ or respectively $w_{2\ell + 1}$. Finally, we place $r - 1$ cops on the vertices inside the deletion edge and capture the robber. This proves the treewidth bound by \cref{thm:cops_robber}.
\end{proof}

In the case of $C = \emptyset$ one could also use a thick $r$-arrow from \cref{thm:arrow_behavior} instead. We will only invoke \cref{thm:decode_behavior} with $|U| = r$ in the dense setting of the \textsc{Deletion to $\ncols$-Colorable}\xspace lower bound; we use the case $|U| = 1$ for the sparse version of the lower bound.

\begin{figure}[h]
 \centering
 \tikzfig{pictures/dtc_partite}
 \caption{The decoding gadget $Y^j_{i, \varphi_i}$: the left bubble represents a $K_r$ and the left bubble an independent set of size $(1 - 2^{-r})p$. The edge between the bubbles represents a join.}
 \label{fig:dtc_decode}
\end{figure}

\subparagraph*{Decoding gadgets.} The color-set-gadgets allow us to construct \emph{decoding gadgets} that can distinguish between the different partial solutions in $\Phi_i$. While the color-set-gadgets only check for inclusion and not equality, this is nonetheless sufficient to distinguish solutions in $\Phi_i$ due to their structure.

We begin with the construction now. For the $j$-th clause, group $i \in [t]$, solution $\varphi_i \in \Phi_i$, we construct a gadget $Y^j_{i, \varphi_i}$ as follows. The gadget $Y^j_{i, \varphi_i}$ consists of a large independent set joined to a $K_r$, i.e., adding all edges between both sets. In other words, $Y^j_{i, \varphi_i}$ is a complete $(r + 1)$-partite graph with one large independent set and all other independent sets in the partition are singletons. More precisely, the large independent set consists of $(1 - 2^{-r})p + 1$ vertices. One of these vertices is distinguished and denoted by $\hat{y}^j_{i, \varphi_i}$. This concludes the construction, see \cref{fig:dtc_decode} for a depiction of the construction.

In particular, the $K_r$ and $\hat{y}^j_{i, \varphi_i}$ induce a complete graph of size $r + 1$. Hence, any solution must delete at least one vertex in this complete graph and due to the budget constraint exactly one vertex has to be deleted. The distinguished vertex $\hat{y}^j_{i, \varphi_i}$ can only be deleted if also all other vertices in the large independent set are deleted. By appropriately adding color-set-gadgets, we will ensure that this can only be achieved if $\varphi_i$ is chosen on $\mathcal{U}_i$.

For the $j$-th clause, group $i \in [t]$, solution $\varphi_i \in \Phi_i$, twinclass $U \in \mathcal{U}_i$ with $\varphi_i(U) \neq [r]$, we pick a private vertex $v \neq \hat{y}^j_{i, \varphi_i}$ in the large independent set of $Y^j_{i, \varphi_i}$ and add the color-set-gadget $B_{\varphi_i(U) \setminus \{\bot\}}(U,v)$ and denote this instance of the color-set-gadget by $W^j_{i, \varphi_i, U}$. We will see, using the properties of solutions in $\Phi_i$, that if the solution on $\mathcal{U}_i$ diverges from $\varphi_i$, then at least one $W^j_{i,\varphi_i,v}$ will be passive. Otherwise, all $W^j_{i,\varphi_i,v}$ will be active, allowing us to delete the vertex $\hat{y}^j_{i, \varphi_i}$ in $Y^j_{i,\varphi_i}$.

\subparagraph{Clause gadgets.} For the $j$-th clause, we add an $(r + 1)$-critical graph, denoted $Z^j \in \mathcal{H}^r$, consisting of at least $q 2^{{p_0}}$ vertices. For every group $i \in [t]$ and solution $\varphi_i \in \Phi_i$ such that $\kappa_i^{-1}(\varphi_i)$ is a partial truth assignment satisfying the $j$-th clause, we pick a private vertex $v$ in $Z^j$ and add a thin arrow from $\hat{y}^j_{i, \varphi_i}$ to $v$. Since every clause consists of at most $q$ literals, at most $q$ groups can contain a literal of the $j$-th clause and every such group has at most $2^{{p_0}}$ assignments that satisfy the $j$-th clause, hence $Z^j$ contains enough vertices so that we can always pick a private one. This concludes the construction of the clause gadget.

The idea of the clause gadget is that we can only afford to delete a vertex in $Z^j$ if we have picked a partial solution on some $\mathcal{U}_i$ that corresponds to a satisfying truth assignment of the $j$-th clause, which will propagate a deletion to $Z^j$ via the decoding gadgets.

\subparagraph*{Packing.} We will now construct a packing $\mathcal{P}$ of vertex-disjoint graphs that will fully explain the budget outside of the central vertices. For every thin arrow from $u$ to $v$ in the construction, we add the $K_{r + 1}$ induced by the deletion edge incident to $v$ to the packing $\mathcal{P}$. For every thick $\ell$-arrow $A_\ell(U,v)$ in the construction, we add $A_\ell(U,v) - U$ to the packing $\mathcal{P}$ and by \cref{thm:arrow_behavior} these graphs require at least $\ell$ deletions each. For every color-set-gadget $B_{C}(U,v)$ in the construction, we add $B_{C}(U,v) - U$ to the packing $\mathcal{P}$ and by \cref{thm:decode_behavior} these graphs require at least $(r - |C|) + 1$ deletions each. Finally, for every $Y^j_{i, \varphi_i}$, we add the $K_{r + 1}$ induced by $\hat{y}^j_{i, \varphi_i}$ and the $K_r$ of $Y^j_{i, \varphi_i}$ to the packing $\mathcal{P}$. Let $\mathrm{cost}_\mathcal{P}$ denote the cost of the packing $\mathcal{P}$.

Observe that no vertex will be the head of several arrows or color-set-gadgets in our construction, hence the graphs in $\mathcal{P}$ are indeed vertex-disjoint. Furthermore, no graph in $\mathcal{P}$ intersects the central vertices and the cost of $\mathcal{P}$ is independent of the partial solution chosen on the central vertices. Finally, notice that the cost of $B_{C}(U,v) - U$ is fully explained by the $(r - |C|) + 1$ disjoint deletion edges and hence does not rely on any \textsc{List Coloring}\xspace constraints simulated by the central clique $F$.

This concludes the construction of $G = G(\sigma, r, {p_0})$. We proceed by showing the correctness of the reduction. From now on, we might omit the range of the indices for the sake of readability, but we keep the meaning of the indices consistent throughout. By $i$ we denote a group of variables, $\varphi_i$ denotes a partial solution in $\Phi_i$, and $U$ denotes a true twinclass in $\mathcal{U}_i$ with $\varphi_i(U) \neq [r]$.

\begin{thm}
 \label{thm:sat_to_dtc}
 Let $\sigma$ be a $q$-\textsc{Satisfiability}\xspace instance with $n$ variables and $m$ clauses. Let $G = G(\sigma, r, {p_0})$ and $\mathcal{P}$ be the graph and packing as constructed above and let $b = \mathrm{cost}_\mathcal{P} + t r p / 2$. If $\sigma$ has a satisfying assignment $\tau$, then there is a solution $\varphi$ of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $(G, b)$.
\end{thm}

\begin{proof}
  We start with the construction of $\varphi$ on the central vertices. We color the central clique $F$ with $\varphi(f_s) = s$ for $s \in [r]$, i.e., $\varphi$ will be a normalized solution. For each group $i$ of variables, let $\tau_i \in \{0,1\}^{p_0}$ be the partial truth assignment on group $i$ induced by $\tau$. For each group $i$, we set $\varphi\big|_{\bigcup(\mathcal{U}_i)} = \varphi_i := \kappa_i(\tau_i) \in \Phi_i$. By \cref{thm:scoloring_deletions}, this results in exactly $t r p / 2$ deletions. Hence, only the budget $\mathrm{cost}_\mathcal{P}$ for the packing $\mathcal{P}$ remains, so for every graph in $\mathcal{P}$ we have to match the lower bound on the number of deletions for this graph.

  Whenever we delete the tail $u$ or head $v$ of a thin arrow from $u$ to $v$, then we use the active solution on this arrow; otherwise, we use the passive solution. Either type of solution results in exactly one deletion in the deletion edge incident to $v$ which belongs to $\mathcal{P}$.

  Similarly, for any thick $\ell$-arrow $A_\ell(U,v)$, we extend to the solution with $|V(A_\ell(U,v) - U) \cap {\coloring^{-1}(\del)}| = \ell$ as given by \cref{thm:arrow_behavior}. If $|U \cap {\coloring^{-1}(\del)}| \geq \ell$, then this solution is active and satisfies $\varphi(v) = \bot$.

  For every color-set-gadget $B_C(U,v)$, we extend to the solution with $|V(B_C(U,v) - U) \cap {\coloring^{-1}(\del)}| = (r - |C|) + 1$ as given by \cref{thm:decode_behavior}. If $\varphi(U) \setminus \{\bot\} \subseteq C$, then this solution is active and satisfies $\varphi(v) = \bot$.

  For every decoding gadget $Y^j_{i, \varphi_i}$, we delete the distinguished vertex $\hat{y}^j_{i,\varphi_i}$. For every $j$-th clause, group $i$, and solution $\psi_i \in \Phi_i \setminus \{\varphi_i\}$, we pick one of the vertices in the $K_r$ of $Y^j_{i, \psi_i}$ and delete it. This deletes exactly one vertex in the $K_{r + 1}$ formed by $\hat{y}^j_{i, \varphi_i}$ or $\hat{y}^j_{i, \psi_i}$ and the $K_r$.

  This concludes the description of the deletions; for each graph in the packing $\mathcal{P}$, we match the lower bound on the number of deletions for this graph. It remains to show that the remainder of $G$ can be properly $r$-colored. This can be easily seen for the thin arrows. For thick $\ell$-arrows $A_\ell(U,v)$ it follows from \cref{thm:arrow_behavior}. For the color-set-gadgets $W^j_{i, \psi_i, U}$, where $\psi_i \in \Phi_i$, it follows from \cref{thm:decode_behavior}. It remains to handle the structure gadgets $L_{i,\ell,S}$, the decoding gadgets $Y^j_{i, \psi_i}$, $\psi_i \in \Phi_i$, and the clause gadgets $Z^j$.

  By \cref{thm:arrow_behavior} and \cref{thm:decode_behavior}, we can appropriately extend solutions to $A_\ell(U,v)$ and $B_C(U,v)$ for every color choice on the vertex $v$. Hence, when handling the aforementioned gadgets, it does not matter how we color the undeleted vertices. It is sufficient to verify that enough deletions occur and that the remainder of the gadget can be $r$-colored.

  Consider some group $i$, some $\ell \in [r]$, some $\mathcal{S} \subseteq \mathcal{U}_i$ with $|\mathcal{S}| = \binom{r}{\geq (r - \ell + 1)}\frac{p}{2^{r}} + 1$, and some copy of $L_{i, \ell, \mathcal{S}}$. Since $L_{i, \ell, \mathcal{S}}$ is an $(r + 1)$-critical graph that does not belong to $\mathcal{P}$, we must perform at least one deletion in $L_{i, \ell, \mathcal{S}}$ and this deletion has to be propagated to $L_{i, \ell, \mathcal{S}}$ by some thick $\ell$-arrow $A_\ell(U,v)$, $U \in \mathcal{U}_i$. Since $\varphi_i \in \Phi_i$, we have that $\left|\left\{U \in \mathcal{U}_i : \varphi_i(U) \setminus \{\bot\} \in \binom{[r]}{\leq (r - \ell)}\right\}\right| = \binom{r}{\leq (r - \ell)} \frac{p}{2^r}$, i.e., there are exactly $\binom{r}{\leq (r - \ell)} \frac{p}{2^r}$ twinclasses in $\mathcal{U}_i$ where $\varphi_i$ deletes at least $\ell$ vertices in each. Due to $\binom{r}{\leq (r - \ell)} \frac{p}{2^r} + |\mathcal{S}| = p + 1 > p = |\mathcal{U}_i|$, there must be at least one twinclass $U \in \mathcal{S}$ with $\varphi_i(U) \setminus \{\bot\} \in \binom{[r]}{\leq (r - \ell)}$, i.e., where $\varphi_i$ deletes at least $\ell$ vertices. Therefore, the thick $\ell$-arrow $A_\ell(U,v)$ leading to this copy of $L_{i,\ell,\mathcal{S}}$ propagates a deletion to $L_{i,\ell,\mathcal{S}}$ by \cref{thm:arrow_behavior} and thereby resolves this $(r + 1)$-critical graph.

  Consider some $Y^j_{i, \psi_i}$, where $\psi_i \in \Phi_i$, if $\psi_i \neq \varphi_i$, then one of the vertices in the $K_r$ is deleted and this $(r + 1)$-partite graph is resolved. If $\psi_i = \varphi_i$, then we claim that the large independent set is fully deleted. In the construction of $\varphi$, we distributed a deletion to $\hat{y}^j_{i, \varphi_i}$. All other vertices $v$ of the large independent set are hit by some $W^j_{i, \varphi_i, U}$, where $\varphi_i(U) \setminus \{\bot\} \neq [r]$. Since certainly $\varphi_i(U) \setminus \{\bot\} \subseteq \varphi_i(U) \setminus \{\bot\}$, we have that $W^j_{i, \varphi_i, U}  = B_{\varphi_i(U) \setminus \{\bot\}}(U,v)$ propagates a deletion to $v$ due to \cref{thm:decode_behavior}. Due to $\varphi_i \in \Phi_i$, there are $\binom{r}{\leq(r - 1)} \frac{p}{2^r} = (1 - 2^{-r})p$ twinclasses $U \in \mathcal{U}_i$ with $\varphi_i(U) \setminus \{\bot\} \neq [r]$, thus matching the size of the large independent set of $Y^j_{i, \varphi_i}$ with the exception of $\hat{y}^j_{i, \varphi_i}$. This shows that the large independent set is fully deleted and the $(r + 1)$-partite graph is resolved.

  Finally, consider some $Z^j$, then there is some group $i$ such that $\tau_i$ satisfies the $j$-th clause, because $\tau$ is a satisfying assignment of $\sigma$. By construction $\varphi_i = \kappa_i(\tau_i)$ and the vertex $\hat{y}^j_{i, \varphi_i}$ is deleted, so the thin arrow from $\hat{y}^j_{i, \varphi_i}$ to $Z^j$ is active and propagates a deletion to $Z^j$. Therefore, the $(r + 1)$-critical graph $Z^j$ is resolved as well.
\end{proof}

\begin{thm}
  \label{thm:enforced_structure}
  Let $\sigma$ be a $q$-\textsc{Satisfiability}\xspace instance with $n$ variables and $m$ clauses. Let $G = G(\sigma, r, {p_0})$ be the graph as constructed above and let $b = \mathrm{cost}_\mathcal{P} + t r p / 2$. If $\varphi$ is a solution of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $(G,b)$, then $|{\coloring^{-1}(\del)}| = b$. Furthermore, there is a normalized solution $\psi$ with $|\psi^{-1}(\bot)| = |{\coloring^{-1}(\del)}| = b$ and $\psi\big|_{\bigcup(\mathcal{U}_i)} \in \Phi_i$ for all $i \in [t]$.
\end{thm}

\begin{proof}
  As argued before, the packing $\mathcal{P}$ forces $\varphi$ to spend at least $\mathrm{cost}_\mathcal{P}$ units of budget outside of the central vertices. We claim that for any group $i \in [t]$ and number of deletions $\ell \in [r]$, there must be at least $\binom{r}{\leq (r - \ell)} \frac{p}{2^r}$ twinclasses $U \in \mathcal{U}_i$ such that $|U \cap {\coloring^{-1}(\del)}| \geq \ell$, i.e., $\varphi$ deletes at least $\ell$ vertices in each $U$. We first define $\mathcal{S}_i^\ell(\varphi) = \{U \in \mathcal{U}_i : |U \cap {\coloring^{-1}(\del)}| = \ell\}$ and $\mathcal{S}_i^{\geq \ell}(\varphi) = \mathcal{S}_i^\ell(\varphi) \cup \mathcal{S}_i^{\ell + 1}(\varphi) \cup \cdots \cup \mathcal{S}_i^r(\varphi)$ for all $i \in [t]$ and $\ell \in \{0\} \cup [r]$.

  Suppose that there is some group $i$ and some number of deletions $\ell \in [r]$ with $|\mathcal{S}_i^{\geq \ell}(\varphi)| < \binom{r}{\leq (r - \ell)} \frac{p}{2^r}$. Then there exists a family $\mathcal{S} \subseteq \mathcal{U}_i$ of twinclasses with $|\mathcal{S}| = \binom{r}{\geq (r - \ell + 1)} \frac{p}{2^r} + 1$ and $\mathcal{S}_i^{\geq \ell}(\varphi) \cap \mathcal{S} = \emptyset$. Consider any copy of $L_{i, \ell, \mathcal{S}}$ and the thick $\ell$-arrows $A_\ell(U,v)$ from $\mathcal{S} \subseteq \mathcal{U}_i$ to $L_{i, \ell, \mathcal{S}}$. Due to $\mathcal{S}_i^{\geq \ell}(\varphi) \cap \mathcal{S} = \emptyset$, the solution $\varphi$ deletes at most $\ell - 1$ vertices in each $U \in \mathcal{S}$, and by \cref{thm:arrow_behavior} this implies that no vertex in the copy of $L_{i, \ell, \mathcal{S}}$ is deleted, unless we pay for at least one extra deletion not accounted for by the packing $\mathcal{P}$ per copy of $L_{i, \ell, \mathcal{S}}$. Since $L_{i, \ell, \mathcal{S}}$ is an $(r + 1)$-critical graph, we must delete at least one vertex in each copy. This would exceed our remaining budget, because there are $1 + t r p / 2 > b - \mathrm{cost}_\mathcal{P}$ copies of $L_{i, \ell, \mathcal{S}}$. Hence, we must have that $|\mathcal{S}_i^{\geq \ell}(\varphi)| \geq \binom{r}{\leq(r - \ell)} \frac{p}{2^r}$ for all groups $i \in [t]$ and deletions $\ell \in [r]$.

  We will now argue that we must have $|\mathcal{S}_i^\ell(\varphi)| = \binom{r}{r - \ell} \frac{p}{2^r}$ for all $i \in [t]$ and $\ell \in [r]$ due to our budget constraint. Consider some group $i$, using the previous inequalities we can derive the following bound on the total number of deletions performed on $\mathcal{U}_i$ by $\varphi$:
  \begin{align*}
    \sum_{\ell = 1}^r \ell |\mathcal{S}_i^\ell(\varphi)| & = r |\mathcal{S}_i^{r}(\varphi)| + \sum_{\ell = 1}^{r - 1} \ell (|\mathcal{S}_i^{\geq \ell}(\varphi)| - |\mathcal{S}_i^{\geq (\ell + 1}(\varphi)|) = \sum_{\ell = 1}^{r} |\mathcal{S}_i^{\geq \ell}(\varphi)| \\
    & \geq \sum_{\ell = 1}^r \binom{r}{\leq(r - \ell)} \frac{p}{2^r} = \sum_{\ell = 0}^{r - 1} (r - \ell) \binom{r}{\ell} \frac{p}{2^r} = r p / 2,
  \end{align*}
  where the last inequality follows from the computation in the proof of \cref{thm:scoloring_deletions}. Summing over the lower bound for all groups, we see that this uses up the whole remaining budget and hence the inequality must be tight for every group. Therefore, also $|\mathcal{S}_i^{\geq \ell}(\varphi)| = \binom{r}{\leq(r - \ell)} \frac{p}{2^r}$ and $|\mathcal{S}_i^{\ell}(\varphi)| = \binom{r}{r - \ell} \frac{p}{2^r}$ for all $i \in [t]$ and $\ell \in [r]$. Since $\sum_{\ell = 0}^r |\mathcal{S}_i^{\ell}(\varphi)| = p$, this also implies that $|\mathcal{S}_i^0(\varphi)| = \binom{r}{r} \frac{p}{2^r} = \frac{p}{2^r}$ for all groups $i$.

  No vertex of the central clique $F$ can be deleted, because $\varphi$ spends its whole budget on the packing $\mathcal{P}$ and the families of twinclasses $\mathcal{U}_i$, $i \in [t]$. Hence, we can assume by permuting the colors that $\varphi(f_s)  = s$, $s \in [r]$, i.e., $\varphi$ is a normalized solution.

  Finally, the equations $|\mathcal{S}_i^{\ell}(\varphi)| = \binom{r}{r - \ell} \frac{p}{2^r} = \binom{r}{\ell} \frac{p}{2^r}$, $i \in [t]$, $\ell \in \{0\} \cup [r]$, imply that for every group $i$ there exists some $\psi_i \in \Phi_i$ with $\varphi(U) = \psi_i(U)$ for all $U \in \mathcal{U}_i$. Since all $U \in \mathcal{U}_i$ are twinclasses, exchanging $\varphi\big|_{\bigcup(\mathcal{U}_i)}$ with $\psi_i$ for every group $i$ still yields a solution $\psi$ for \textsc{Deletion to $\ncols$-Colorable}\xspace with the desired properties.
\end{proof}

\begin{thm}
 \label{thm:dtc_to_sat}
 Let $\sigma$ be a $q$-\textsc{Satisfiability}\xspace instance with $n$ variables and $m$ clauses. Let $G = G(\sigma, r, {p_0})$ be the graph as constructed above and let $b = \mathrm{cost}_\mathcal{P} + t r p / 2$. If the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $(G, b)$ has a solution $\varphi$, then $\sigma$ has a satisfying assignment $\tau$.
\end{thm}

\begin{proof}
 By \cref{thm:enforced_structure}, we know that $|{\coloring^{-1}(\del)}| = b$ and can assume that $\varphi$ is a normalized solution with $\varphi_i := \varphi\big|_{\bigcup(\mathcal{U}_i)} \in \Phi_i$ for all groups $i$. Hence, the deletions are fully explained by the packing $\mathcal{P}$ and the properties of solutions in $\Phi_i$.

 For every thin arrow from $u$ to $v$, thick $\ell$-arrow $A_\ell(U,v)$, color-set-gadget $B_C(U,v)$, by \cref{thm:arrow_behavior} and \cref{thm:decode_behavior}, we can assume that $\varphi$ chooses the active solution on this gadget if the appropriate condition at $u$ or $U$ is satisfied.

 Consider the $j$-th clause and some group $i$, we begin by arguing that $\varphi(\hat{y}^j_{i, \psi_i}) = \bot$ only if $\psi_i = \varphi_i$. First, observe that $\hat{y}^j_{i, \psi_i}$ may only be deleted if all other vertices of the large independent set in $Y^j_{i, \psi_i}$ are deleted, otherwise $Y^j_{i, \psi_i}$ as a complete $(r + 1)$-partite graph is not resolved or we exceed the packing budget on the complete graph induced by $\hat{y}^j_{i, \psi_i}$ and the $K_r$. Consider some $\psi_i \in \Phi_i \setminus \{\varphi_i\}$. We will distinguish three cases.
 \begin{enumerate}
  \item Suppose that there is some $U \in \mathcal{U}_i$ such that $|\psi_i(U) \setminus \{\bot\}| < |\varphi_i(U) \setminus \{\bot\}|$. This implies that $\psi_i(U) \setminus \{\bot\} \neq [r]$, hence the gadget $W^j_{i, \psi_i, U} = B_{\psi_i(U) \setminus \{\bot\}}(U,v)$, where $v$ is in the large independent set of $Y^j_{i, \psi_i}$, exists. The cardinality inequality also implies that $\varphi_i(U) \setminus \{\bot\} \not\subseteq \psi_i(U) \setminus \{\bot\}$, so by \cref{thm:decode_behavior} and the budget being tight on the graphs of the packing $\mathcal{P}$, we see that $v$ cannot be deleted. Hence, $\hat{y}^j_{i, \psi_i}$ cannot be deleted either.
  \item Suppose that there is some $U \in \mathcal{U}_i$ such that $|\psi_i(U) \setminus \{\bot\}| > |\varphi_i(U) \setminus \{\bot\}|$. The first case must also apply, otherwise $\psi_i \notin \Phi_i$ because $\psi_i$ would perform too few deletions then.
  \item Since the first two cases do not apply, it follows that $|\psi_i(U) \setminus \{\bot\}| = |\varphi_i(U) \setminus \{\bot\}|$ for all $U \in \mathcal{U}_i$. There must be some $U \in \mathcal{U}_i$ such that $\psi_i(U) \setminus \{\bot\} \neq \varphi_i(U) \setminus \{\bot\}$. This implies that $\psi_i(U) \setminus \{\bot\} \neq [r]$ and hence the gadget $W^j_{i, \psi_i, U} = B_{\psi_i(U) \setminus \{\bot\}}(U,v)$, where $v$ is in the large independent set of $Y^j_{i, \psi_i}$, exists. Since $|\psi_i(U) \setminus \{\bot\}| = |\varphi_i(U) \setminus \{\bot\}|$ and $\psi_i(U) \setminus \{\bot\} \neq \varphi_i(U) \setminus \{\bot\}$, we must have that $\varphi_i(U) \setminus \{\bot\} \not\subseteq \psi_i(U) \setminus \{\bot\}$, hence, as in the first case, $v$ cannot be deleted and neither can $\hat{y}^j_{i, \psi_i}$.
 \end{enumerate}
 This proves the claim regarding the deletion of $\hat{y}^j_{i, \psi_i}$.

 Now, consider the gadget $Z^j$. To resolve $Z^j$, there has to be a thin arrow from some $\hat{y}^j_{i, \psi_i}$ to $Z^j$ that is active. By the previous claim, this implies that $\psi_i = \varphi_i$. Furthermore, by construction of $G$ such a thin arrow only exists if the partial truth assignment $\tau_i = \kappa_i^{-1}(\varphi_i)$ satisfies the $j$-th clause. Note that the definition of $\tau_i$ is independent of the considered clause.

 For some groups $i$, the partial solution $\varphi_i$ might not be in the image of $\kappa_i$, in that case $\tau_i$ is an arbitrary partial truth assignment for the $i$-th variable group. By the previous argument, the truth assignment $\tau = \bigcup_{i = 1}^{t} \tau_i$ must satisfy all clauses of $\sigma$.
\end{proof}

\begin{figure}
 \centering
 \tikzfig{pictures/dtc_clause_component}
 \caption{A high-level overview of the component corresponding to the $j$-th clause after removing the TCM $\mathcal{X}$. The arrows leading to $Z^j$ denote thin arrows.}
 \label{fig:dtc_clause_component}
\end{figure}

\begin{thm}
 \label{thm:dtc_tw_bound}
 Let $G = G(\sigma, r, {p_0})$ be the graph as constructed above. The set $\mathcal{X} = (\bigcup_{i = 1}^t \mathcal{U}_i) \cup \{\{f_s\} : s \in [r]\}$ is a TCM for $G$ of size $t p + r$ to treewidth $r$, i.e., $|\mathcal{X}| =  t p + r$ and $\tw(G - \bigcup(\mathcal{X})) \leq r$.
\end{thm}

\begin{proof}
 It follows trivially from the construction of $G$ that $\mathcal{X}$ has size $\sum_{i = 1}^t |\mathcal{U}_i| + |F| = t p + r$ and only consists of twinclasses. It remains to argue that the treewidth of $G' := G - \bigcup(\mathcal{X})$ is at most $r$. We will show this by using the omniscient-cops-and-robber-game. The remaining graph $G'$ consists of several connected components, namely one connected component per copy of $L_{i, \ell, \mathcal{S}}$ and one connected component for every clause. Observe the heads of thick $\ell$-arrows $A_\ell(U,v)$, of color-set-gadgets $B_C(U,v)$, of thin arrows, and also the tails of thin arrows consist of only a single vertex. So, if the robber escapes through one of these gadgets and there is no other path back, then a single cop suffices to prevent the robber from going back.

 We begin by handling the connected components corresponding to a copy of $L_{i, \ell, \mathcal{S}}$. On a high level, these components look like stars; the center is $L_{i, \ell, \mathcal{S}}$ and for every $U \in \mathcal{S}$ there is an $A_\ell(U,v) - U$ attached to $L_{i, \ell, \mathcal{S}}$. By \cref{thm:critical_family}, $L_{i, \ell, \mathcal{S}}$ has pathwidth $r$. With $r + 1$ cops we sweep from left to right through the bags of the pathwidth decomposition of $L_{i, \ell, \mathcal{S}}$ until the robber escapes to one of the attached $A_\ell(U,v) - U$. When that happens we remove all cops, except the cop on the head $v$ of the considered thick $\ell$-arrow from $L_{i, \ell, \mathcal{S}}$. We can then capture the robber using the strategy given by \cref{thm:arrow_behavior}.

 Next, we handle the connected components corresponding to a clause. \cref{fig:dtc_clause_component} gives a high-level overview how these components look, notice that at this level there are no cycles. Our strategy makes use of this hierarchy, we start at $Z^j$ and chase the robber downwards, making sure that the robber cannot go back upwards. By \cref{thm:critical_family}, $Z^j$ has pathwidth $r$. Again, we sweep with $r + 1$ cops from left to right through the bags of the pathwidth decomposition of $Z^j$, until the robber escapes through some thin arrow coming from some $Y^j_{i, \varphi_i}$. Then, we remove all cops except the one on the head of the thin arrow and place one cop on the tail $\hat{y}^j_{i, \varphi_i}$ of the thin arrow. Either the robber escapes to the thin arrow, where we can capture it easily using $r - 1$ further cops or the robber escapes to $Y^j_{i, \varphi_i}$.

 If the robber escapes to $Y^j_{i, \varphi_i}$, then we remove the cop from the head of the thin arrow and place $r$ cops on the $K_r$ in $Y^j_{i, \varphi_i}$. This leaves us with one connected component $W^j_{i, \varphi_i, U} = B_{C}(U,v)$ for each $U \in \mathcal{U}_i$ with $\varphi_i(U) \neq [r]$. Consider the connected component the robber escaped to and move the cop from $\hat{y}^j_{i, \varphi_i}$ to $v$. Since there are still cops on the $K_r$ in $Y^j_{i, \varphi_i}$, the robber cannot go back. We can now remove these cops on $K_r$ and capture the robber using the strategy given by \cref{thm:decode_behavior}.

 This concludes the strategy. Since we have never placed more than $r + 1$ cops simultaneously, we see by \cref{thm:cops_robber} that $G'$ has treewidth at most $r$.
\end{proof}

\begin{proof}[Proof of \cref{thm:dtc_lower_bound}]
 Suppose there is some $r \geq 2$ and $\varepsilon > 0$ such that \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((2^r - \varepsilon)^{|\mathcal{X}|})$, where $\mathcal{X}$ is a TCM to treewidth $r$. We will show that there exists a $\delta < 1$ such that for any clause size $q$, we can solve $q$-\textsc{Satisfiability}\xspace in time $\Oh^*(2^{\delta n})$, where $n$ is the number of variables. This contradicts SETH\xspace by \cref{thm:seth_hitting_set} and hence implies the desired lower bound.

 Given a $q$-\textsc{Satisfiability}\xspace instance $\sigma$, we construct the graph $G = G(\sigma, r, {p_0})$, where ${p_0}$ depends only on $r$ and $\varepsilon$ and will be chosen later. We can consider $r$, $\varepsilon$, and $q$ as constants, hence also ${p_0} = {p_0}(r, \varepsilon)$ and $p = p({p_0})$ are constant. First, we will argue that $G$ has polynomial size. The number of vertices in the various gadgets can be estimated as follows, where we have an additional summand $r$ for the $(r + 1)$-critical graphs, since \cref{thm:critical_family} only constructs them in increments of $r$:
 \begin{itemize}
  \item $|V(G[\bigcup(\mathcal{X})])| = \sum_{i = 1}^t |\mathcal{U}_i|r + |F| = t p r + r = \lceil \frac{n}{{p_0}} \rceil p r + r = \Oh(n)$.
  \item $|V(L_{i, \ell, \mathcal{S}})| \leq |\mathcal{S}| + r \leq |\mathcal{U}_i| + r = p + r = \Oh(1)$.
  \item $|V(Z^j)| \leq q 2^{{p_0}} + r = \Oh(1)$.
  \item $|V(W^j_{i, \varphi_i, U})| \leq (r + 1)^2 = \Oh(1)$.
  \item $|V(A_\ell(U,v))| \leq r^3 + 3r + 1 = \Oh(1)$.
  \item Every thin arrow consists of $2r + 1$ vertices.
 \end{itemize}
 Next, we bound how often each gadget appears:
 \begin{itemize}
  \item $i$ can take on $t = \lceil \frac{n}{{p_0}} \rceil = \Oh(n)$ values.
  \item There are at most $\Oh(n^q)$ clauses, hence $j$ can take on $\Oh(n^q)$ values.
  \item $\ell$ can take on $r = \Oh(1)$ values.
  \item For fixed $i$, $\mathcal{S} \subseteq \mathcal{U}_i$, so $\mathcal{S}$ can take on $2^{|\mathcal{U}_i|} = 2^p = \Oh(1)$ values.
  \item We create $1 + t r p / 2 = \Oh(n)$ copies of each $L_{i, \ell, \mathcal{S}}$.
  \item For fixed $i$, $\varphi_i \in \Phi_i$ and $|\Phi_i| \leq (2^r)^p = \Oh(1)$.
  \item For fixed $i$, $U \in \mathcal{U}_i$, so $U$ can take on $|\mathcal{U}_i| = p = \Oh(1)$ values.
  \item We create at most one (thin or thick) arrow per vertex in some $Z^j$ or $L_{i, \ell, \mathcal{S}}$.
 \end{itemize}
 Together, all these bounds show that $G$ has polynomial size and following the construction of $G$, one can easily see that $G$ can also be constructed in polynomial time. Furthermore, from the proof of \cref{thm:dtc_tw_bound} we can obtain a tree decomposition of $G' := G - \bigcup(\mathcal{X})$ of width $r$ in polynomial time.

 We remark that this is the only step in the proof where we use that the clauses have size at most $q$. Without a bound on the clause size, the size of $Z^j$ could be exponential in the number of variables, thus breaking the proof.

 To analyze the running time resulting from applying the reduction and running the assumed algorithm for \textsc{Deletion to $\ncols$-Colorable}\xspace, we first bound $p$ as follows:
 \begin{equation}
  \label{eq:grpsize_bound}
  p \leq \frac{{p_0}}{r} + 2^{r + 1} \left\lceil \log_{2^r}\left({{p_0}}/{r}\right) \right\rceil + 2^r + 1.
 \end{equation}

 In the construction of $G = G(\sigma, r, {p_0})$, we chose $p$ as the smallest integer such that $p$ is divisible by $2^r$ and such that the quantity  from \cref{thm:scolorings_bound}, which we denote by $x$, is larger than $2^{p_0}$. The summand $2^r$ in \cref{eq:grpsize_bound} accounts for the divisibility. It remains to show that the second property is satisfied, for this we work with $p = \frac{{p_0}}{r} + 2^{r + 1} \lceil \log_{2^r}({{p_0}}/{r}) \rceil + 1$.

 We first observe that $(2^r - 1)! / 2^{(2^r)} \geq \frac{1}{4}$ for all $r \geq 2$. Hence, $x \geq (2^r)^p p^{-(2^r)} / 4 =: x'$. Furthermore, observe that we have $2 {{p_0}}/{r} \geq p$ for sufficiently large ${p_0}$. We proceed by showing that $x' \geq 2^{p_0}$:
 \begin{align*}
  x' & \geq (2^r)^{\frac{{p_0}}{r} + 2^{r + 1} \lceil \log_{2^r}({{p_0}}/{r}) \rceil} p^{-(2^r)}
   \geq 2^{p_0} \left({{p_0}}/{r}\right)^{(2^{r + 1})} p^{-(2^r)} \geq 2^{p_0} \left({{p_0}}/{r}\right)^{(2^{r + 1})} \left(2 {{p_0}}/{r}\right)^{-(2^r)} \\
   & \geq 2^{p_0} \left({{p_0}}/{r}\right)^{(2^{r})} 2^{-(2^r)} \geq 2^{p_0},
 \end{align*}
 where we use ${{p_0}}/{r} \geq 2$ for sufficiently large ${p_0}$ in the last inequality.

 Running the assumed algorithm for \textsc{Deletion to $\ncols$-Colorable}\xspace on $G$ decides, by \cref{thm:sat_to_dtc} and \cref{thm:dtc_to_sat}, the satisfiability of $\sigma$. Since $G$ can be constructed in polynomial time and has parameter value $|\mathcal{X}| = \lceil \frac{n}{{p_0}} \rceil p + r$ by \cref{thm:dtc_tw_bound}, we can solve $q$-\textsc{Satisfiability}\xspace in time
 \begin{align*}
  \Oh^*((2^r - \varepsilon)^{|\mathcal{X}|}) & = \Oh^*((2^r - \varepsilon)^{\lceil \frac{n}{{p_0}} \rceil p + r}) \leq \Oh^*((2^r - \varepsilon)^{\frac{n}{{p_0}} p}) \\
  & \leq \Oh^*((2^r - \varepsilon)^{\frac{n}{r}} (2^r - \varepsilon)^{\frac{n}{{p_0}}(2^{r + 1} \lceil \log_{2^r}({{p_0}}/{r}) \rceil + 2^r + 2)}).
 \end{align*}
 We have that $\Oh^*((2^r - \varepsilon)^{\frac{n}{r}}) \leq \Oh^*(2^{\delta_1 n})$ for some $\delta_1 < 1$. It remains to upper bound the second factor, we will again use that ${p_0}$ can be chosen sufficiently large:
 \begin{alignat*}{4}
  \phantom{\leq} \quad & \Oh^*\left((2^r - \varepsilon)^{\frac{n}{{p_0}}(2^{r + 1} \lceil \log_{2^r}({{p_0}}/{r}) \rceil + 2^r + 2)}\right) \quad & \leq\quad & \Oh^*\left((2^r - \varepsilon)^{2^{r + 2} \frac{n}{{p_0}} \log_{2^r}({{p_0}}/{r})}\right) \\
  \leq \quad & \Oh^*\left((2^r - \varepsilon)^{2^{r + 2} \frac{n}{{p_0}} \log_{2^r}({p_0})}\right)\quad  & \leq \quad & \Oh^*\left(\left(\left(2^r - \varepsilon\right)^{2^{r + 2} \frac{\log_{2^r}({p_0})}{{p_0}}}\right)^{n}\right) \\
  \leq \quad & \Oh^*\left(2^{\delta_2 n}\right), & &
 \end{alignat*}
 where $\delta_2$ can be chosen to be arbitrarily close to $0$ by making ${p_0}$ sufficiently large. By choosing $\delta_2$ small enough so that $\delta := \delta_1 + \delta_2 < 1$, we obtain that $q$-\textsc{Satisfiability}\xspace can be solved in time $\Oh^*(2^{\delta n})$. Since the choice of ${p_0}$ is independent of $q$, this running time holds for all $q$ and therefore SETH\xspace would be false.
\end{proof}

\begin{cor}
 If \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((2^r - \varepsilon)^{\tctd(G)})$ for some $r \geq 2$ and $\varepsilon > 0$, then SETH\xspace is false.
\end{cor}

\begin{proof}
 Follows from \cref{thm:dtc_lower_bound} and \cref{thm:tcm_tctd}.
\end{proof}

\section{Lower Bound for Dominating Set}
\label{sec:ds_lb}

Bodlaender el al.~\cite{BodlaenderLRV10} have shown that \textsc{Dominating Set}\xspace can be solved in time $\Oh^*(4^{\cw(G)})$. The corresponding tight lower bound, assuming that SETH\xspace holds, was provided by Katsikarelis et al.~\cite{KatsikarelisLP19} as a special case of a lower bound for $(b,r)$-\textsc{Center}, i.e., a $(b,1)$-center is a dominating set of size $b$. This lower bound, as is usual, already applies to linear-clique-width, but not to twinclass-pathwidth.

We provide a straightforward tight lower bound for \textsc{Dominating Set}\xspace parameterized by twinclass-pathwidth by observing that solving \textsc{Dominating Set}\xspace on $G$ essentially means solving \textsc{Total Dominating Set}\xspace on $G / \Pi_{tc}$ and providing a lower bound for \textsc{Total Dominating Set}\xspace parameterized by pathwidth based on the methods of Lokshtanov et al.~\cite{LokshtanovMS18}.

For the remainder of this section assume without loss of generality that $G$ is connected and consists of at least two vertices. We define the graph $G'$ by $V(G') = V(G) \cup \{v' : v \in V(G)\}$ and $E(G') = E(G) \cup \{\{u,v'\},\{u',v\},\{u',v'\} : \{u,v\} \in E(G)\}$, i.e., we obtain $G'$ from $G$ by creating a false twin of each vertex.

\begin{lem}
  \label{thm:twins_tcpw}
 It holds that $\tcpw(G') \leq \pw(G)$.
\end{lem}

\begin{proof}
  We begin by showing that $u \neq v \in V(G)$ are twins in $G'$ if and only if $u$ and $v$ are false twins in $G$. First, suppose that $\{u,v\} \in E(G)$. By construction of $G'$, this implies that $u' \in N_{G'}(v) \setminus N_{G'}(u)$ and hence $u$ and $v$ cannot be twins in $G'$ in this case. If $u$ and $v$ are false twins in $G'$, then $N_{G}(u) = N_{G'}(u) \cap V(G) = N_{G'}(v) \cap V(G) = N_{G}(v)$, so $u$ and $v$ are false twins in $G$ as well. If $u$ and $v$ are false twins in $G$, then $N_{G'}(u) = N_G(u) \cup \{w' : w \in N_G(u)\} = N_G(v) \cup \{w' : w \in N_G(v)\} = N_{G'}(v)$, so $u$ and $v$ are false twins in $G'$.

  By construction of $G'$, also the two vertices $v$ and $v'$ are false twins in $G'$ for all $v \in V(G)$. Together with the previous argument, this shows that every twinclass of $G'$ has the form $U \cup \{v' \in U : v \in U\}$, where $U$ is a false twinclass of $G$. Let $\Pi' = \{\{v,v'\} : v \in V(G)\}$, then $G' / \Pi' = G$ and from the structure of $\Pi_{tc}(G')$ it follows that $G' / \Pi_{tc}(G')$ has to be an induced subgraph of $G$. Hence, we obtain $\tcpw(G') = \pw(G' / \Pi_{tc}(G')) \leq \pw(G)$.
\end{proof}

\begin{lem}
  \label{thm:ds_iff_tds}
 $G'$ has a dominating set of size at most $b$ if and only if $G$ has a total dominating set of size at most $b$.
\end{lem}

\begin{proof}
  $\Rightarrow:$ Let $X'$ be a dominating set of $G'$. If $|X' \cap \{v, v'\}| = 1$ for some $v \in V(G)$, then we can assume without loss of generality that $v \in X'$. Suppose that $|X' \cap \{v,v'\}| = 2$ for some $v \in V(G)$. If $X' \cap N_{G'}(v) = X' \cap N_{G'}(v') = \emptyset$, then choose some $w \in N_{G'}(v) \cap V(G) = N_{G'}(v') \cap V(G)$, which exists due to our assumptions about $G$, and consider $X'' = (X' \setminus \{v'\}) \cup \{w\}$. Otherwise, consider $X'' = X' \setminus \{v'\}$. In either case, $|X''| \leq |X'|$ and we claim that $X''$ is still a dominating set of $G'$. Only vertices inside $N_{G'}[v']$ may not be dominated anymore. The vertex $v'$ is still dominated, because there is some $w \in X'' \cap N_{G'}(v) = X'' \cap N_{G'}(v')$. The vertices in $N_{G'}(v')$ are still dominated, because $v \in X''$ and $N_{G'}(v) = N_{G'}(v')$. Hence, $X''$ is a dominating set of $G'$.

  By repeating this argument, we obtain a dominating set $X$ of $G'$ with $|X| \leq |X'|$ and $X \subseteq V(G)$. For every $v \in V(G)$, we have that $v' \notin X$ and hence, there exists some $w \in X \cap N_{G'}(v') = X \cap N_{G'}(v) = X \cap N_G(v)$, where the last equality is due to $X \subseteq V(G)$. This shows that $X$ is a total dominating set of $G$.

  $\Leftarrow:$ Let $X$ be a total dominating set of $G$. We claim that $X$ is also a dominating set of $G'$. As $G'[V(G)] = G$, any vertex in $V(G)$ is still dominated by $X$ inside $G'$. Consider some vertex $v'$ for some $v \in V(G)$. Since $X$ is a total dominating set of $G$, there exists some $w \in X \cap N_G(v) = X \cap N_{G'}(v) = X \cap N_{G'}(v')$ and hence $v'$ is dominated by $X$ as well. So, $X$ must be a dominating set of $G'$.
\end{proof}

\begin{thm}
  If there is an algorithm $\mathcal{A}$ solving \textsc{Dominating Set}\xspace in time $\Oh^*((4 - \varepsilon)^{\tcpw(G)})$ for some $\varepsilon > 0$, then there is an algorithm $\mathcal{A}'$ solving \textsc{Total Dominating Set}\xspace in time $\Oh^*((4 - \varepsilon)^{\pw(G)})$.
\end{thm}

\begin{proof}
  Suppose $\mathcal{A}$ is such an algorithm. The algorithm $\mathcal{A}'$ first constructs $G'$ in polynomial time, then runs $\mathcal{A}$ on $G'$, which takes time $\Oh^*((4 - \varepsilon)^{\tcpw(G')}) \leq \Oh^*((4 - \varepsilon)^{\pw(G)})$ by \cref{thm:twins_tcpw}. Finally $\mathcal{A}'$ returns the same answer as $\mathcal{A}$. The correctness of $\mathcal{A}'$ follows from \cref{thm:ds_iff_tds} and the running time of $\mathcal{A}'$ is dominated by running $\mathcal{A}$ on $G'$.
\end{proof}

We remark that an $\Oh^*(4^{\tw(G)})$-time algorithm for \textsc{Total Dominating Set}\xspace is posed as an exercise in \cite{CyganFKLMPPS15}. It remains to show that \textsc{Total Dominating Set}\xspace cannot be solved in time $\Oh^*((4-\varepsilon)^{\pw(G)})$ for some $\varepsilon > 0$. We show this by adapting the lower bound construction for \textsc{Dominating Set}\xspace given by Lokshtanov et al.~\cite{LokshtanovMS18}. Since 4 is a power of two, some technicalities regarding the groups can be avoided, allowing for a simpler construction.

\begin{thm}
  \label{thm:tds_lb}
  There is no algorithm solving \textsc{Total Dominating Set}\xspace in time $\Oh^*((4 - \varepsilon)^{\pw(G)})$ for some $\varepsilon > 0$, unless SETH\xspace is false.
\end{thm}

\subparagraph*{Construction.} Let $\sigma$ be a \textsc{Satisfiability}\xspace instance with $n$ variables and $m$ clauses. We begin by describing how to construct a graph $G = G(\sigma)$ of pathwidth $n/2 + \Oh(1)$. We assume without loss of generality that $\sigma$ has an even number of variables and partition the variables into pairs, so that pair $i \in [n/2]$ consists of variables $x_{2i - 1}$ and $x_{2i}$.

\begin{figure}[h]
 \centering
 \tikzfig{pictures/tds_path}
 \caption{The path segment $P_i^\ell$ and guards $Q_i^\ell$.}
 \label{fig:tds_path}
\end{figure}

For every pair $i \in [n/2]$, we create a path $P_i$ consisting of $4 m (3 \frac{n}{2} + 1)$ vertices and partition the path into $m (3 \frac{n}{2} + 1)$ segments consisting of four vertices. Segment $\ell \in [m(3 \frac{n}{2} + 1)]$ consists of the vertices $P_i^\ell = \{p_{i,1}^\ell, p_{i,2}^\ell, p_{i,3}^\ell, p_{i,4}^\ell\}$. To each segment $\ell$, we attach four \emph{guard vertices} $Q_i^\ell = \{q_{i,1}^\ell, \ldots, q_{i,4}^\ell\}$ such that $N(q_{i,j}^\ell) = P_i^\ell \setminus \{p_{i,j}^\ell\}$ for all $j \in [4]$, i.e., for every vertex on $P_i^\ell$ there is one guard that avoids this vertex and is only adjacent to all other vertices on $P_i^\ell$, see \cref{fig:tds_path}.

\begin{figure}[h]
 \centering
 \tikzfig{pictures/tds_states}
 \caption{The four states $\mathbf{1}_i^\ell$, $\mathbf{2}_i^\ell$, $\mathbf{3}_i^\ell$, and $\mathbf{4}_i^\ell$ on the path segment $P_i^\ell$. The filled vertices belong to the corresponding set.}
 \label{fig:tds_states}
\end{figure}

Let $\mathbf{1}_i^\ell = \{p_{i,1}^\ell, p_{i,2}^\ell\}$, $\mathbf{2}_i^\ell = \{p_{i,1}^\ell, p_{i,4}^\ell\}$, $\mathbf{3}_i^\ell = \{p_{i,2}^\ell, p_{i,3}^\ell\}$, $\mathbf{4}_i^\ell = \{p_{i,3}^\ell, p_{i,4}^\ell\}$ and $\mathcal{S}_i^\ell = \{\mathbf{1}_i^\ell, \mathbf{2}_i^\ell, \mathbf{3}_i^\ell, \mathbf{4}_i^\ell\}$, see \cref{fig:tds_states} for a depiction of these sets. For each segment $P_i^\ell$, we introduce four \emph{connector vertices} $\hat{z}_{i,S}^\ell$, $S \in \mathcal{S}_i^\ell$ and four \emph{clique vertices} $z_{i,S}^\ell$, $S \in \mathcal{S}_i^\ell$, together with two \emph{clique guards} $y_{i,1}^\ell$ and $y_{i,2}^\ell$. The connector vertex $\hat{z}_{i,S}^\ell$ is adjacent to $P_i^\ell \setminus S$ and the clique vertex $z_{i,S}^\ell$. The clique guards $y_{i,1}^\ell$ and $y_{i,2}^\ell$ are adjacent and the clique vertices $z_{i,S}^\ell$, $S \in \mathcal{S}_i^\ell$, together with $y_{i,1}^\ell$ form a clique.

\begin{figure}[h]
 \centering
 \tikzfig{pictures/tds_block}
 \caption{The block gadget $B_i^\ell$. The vertices in the dashed ellipse form a clique. The vertex $\hat{z}_{i, \mathbf{3}_i^\ell}^\ell$ is adjacent to $P_i^\ell \setminus \mathbf{3}_i^\ell$.}
 \label{fig:tds_block}
\end{figure}

We define $Z_i^\ell = \{z_{i,S}^\ell, \hat{z}_{i,S}^\ell : S \in \mathcal{S}_i^\ell\} \cup \{y_{i,1}^\ell, y_{i,2}^\ell\}$, $B_i^\ell = P_i^\ell \cup Q_i^\ell \cup Z_i^\ell$, and $R^\gamma = \bigcup_{i = 1}^{n/2} \bigcup_{\ell = (\gamma - 1)m + 1}^{\gamma m} B_i^\ell$ for $\gamma \in [3 \frac{n}{2} + 1]$. The $B_i^\ell$ are called \emph{blocks}; the $R^\gamma$ are called \emph{regions}. See \cref{fig:tds_block} for a depiction of a single block. Each region can be visualized as a matrix of blocks with $n / 2$ rows and $m$ columns and we have $3 \frac{n}{2} + 1$ regions in total.

Let $\mathbf{states} = \{\mathbf{1}, \mathbf{2}, \mathbf{3}, \mathbf{4}\}$ and fix a bijection $\kappa \colon \{0,1\}^2 \rightarrow \mathbf{states}$ mapping truth assignments of a pair of variables to possible states on a path segment. For each clause $C_j$, $j \in [m]$, we introduce $3 \frac{n}{2} + 1$ \emph{clause vertices} $\hat{c}_j^\gamma$, $\gamma \in [3 \frac{n}{2} + 1]$, one per region. The vertex $\hat{c}_j^\gamma$ is adjacent to vertices in the blocks $B_i^{(\gamma - 1) m + j}$ for every $i \in [n / 2]$. Namely, for every variable pair $i$ consider the truth assignments that satisfy clause $C_j$ and consider the states corresponding, via $\kappa$, to these truth assignments. Each of these states corresponds to some vertex $z_{i,S}^{(\gamma - 1) m + j}$, $S \in \mathcal{S}_i^{(\gamma - 1) m + j}$, which we make adjacent to $\hat{c}_j^\gamma$.

Finally, we introduce four \emph{endpoint guards} $h_1$, $h_2$, $h'_1$, $h'_2$, together with the edges $\{h_1, h'_1\}$, $\{h_1, h_2\}$, $\{h'_1, h'_2\}$, and $h_1$ is made adjacent to $p_{i,1}^1$ for all $i \in [n / 2]$ and $h'_1$ is made adjacent to $p_{i,4}^{m (3 \frac{n}{2} + 1)}$ for all $i \in [n / 2]$. This concludes the construction of $G(\sigma)$. See \cref{fig:tds_blockmatrix} for a depiction of the graph $G$ as a matrix of blocks.

\begin{figure}
 \centering
 \tikzfig{pictures/tds_blockmatrix}
 \caption{$G$ viewed as a matrix of block gadgets. The dashed rectangles delineate different regions.}
 \label{fig:tds_blockmatrix}
\end{figure}

\begin{lem}
 \label{thm:sat_to_tds}
 If $\sigma$ is satisfiable, then $G(\sigma)$ has a total dominating set of size at most $4 m (3 \frac{n}{2} + 1) \frac{n}{2} + 2$.
\end{lem}

\begin{proof}
 Let $\tau$ be a satisfying truth assignment of $\sigma$. Let $\tau_i$ be the restriction of $\tau$ to the $i$-th variable pair. We construct a total dominating set $X$ of the desired size as follows. For every variable pair $i \in [\frac{n}{2}]$, we take in each block $B_i^\ell$ the vertices in $\kappa(\tau_i)_i^\ell \in \mathcal{S}_i^\ell$, the vertex $z_{i, \kappa(\tau_i)_i^\ell}^\ell$, and the clique guard $y_{i,1}^\ell$ for all $\ell \in [m (3 \frac{n}{2} + 1)]$. Additionally, we take the endpoint guards $h_1$ and $h'_1$. This concludes the description of $X$ and we see that $|X| = 4 m (3 \frac{n}{2} + 1) \frac{n}{2} + 2$.

 First, observe that $X$ dominates all the endpoint guards $h_1$, $h_2$, $h'_1$, $h'_2$, and the endpoints of all $P_i$ are dominated, since $h_1, h'_1 \in X$. Next, since $X$ contains two vertices from each path segment $P_i^\ell$, we see that $X$ intersects the neighborhoods of all vertices in $Q_i^\ell$ and hence dominates them. On each path $P_i$, we are repeatedly taking two consecutive vertices with a gap of two, except for possibly the ends of $P_i$. Hence, also all interior vertices of $P_i$ are dominated.

 Consider the vertices in the $Z_i^\ell$ next. Since $y_{i,1}^\ell \in X$, we see that $y_{i,2}^\ell$ and all $z_{i,S}^\ell$, $S \in \mathcal{S}_i^\ell$, are dominated. Additionally, since $z_{i,\kappa(\tau_i)_i^\ell}^\ell \in X$, also $y_{i,1}^\ell$ and $\hat{z}_{i,\kappa(\tau_i)_i^\ell}^\ell$ must be dominated. For $S \in \mathcal{S}_i^\ell \setminus \{\kappa(\tau_i)_i^\ell\}$, we see that $\hat{z}_{i,S}^\ell$ is dominated by some vertex on $P_i^\ell$, because $N(\hat{z}_{i,S}^\ell) \cap X = (P_i^\ell \setminus S) \cap \kappa(\tau_i)_i^\ell \neq \emptyset$ by construction.

 Finally, consider the clause vertices $\hat{c}_j^\gamma$. Since clause $C_j$ is satisfied by $\tau$, there is some variable pair $i$ so that $\tau_i$ satisfies $C_j$. By construction of $G(\sigma)$ and $X$, we have that $z_{i,\kappa(\tau_i)_i^\ell}^{(\gamma - 1)m + j} \in X$ and this vertex is adjacent to $\hat{c}_j^\gamma$, so it is dominated. This concludes the proof.
\end{proof}

For the reverse direction, we will prove some lemmas about the structure of total dominating sets in $G(\sigma)$ first.

\begin{lem}
  \label{thm:tds_structure}
  Let $X$ be a total dominating set of $G(\sigma)$, then for any block $B_i^\ell = P_i^\ell \cup Q_i^\ell \cup Z_i^\ell$, we have that $|X \cap P_i^\ell| \geq 2$, $|X \cap Z_i^\ell| \geq 2$, and $y_{i,1}^\ell \in X$. Moreover, if $|X \cap B_i^\ell| \leq 4$, then $X \cap P_i^\ell \in \mathcal{S}_i^\ell$ and $X \cap \{z_{i,S}^\ell : S \in \mathcal{S}_i^\ell\} = \{z_{i, X \cap P_i^\ell}^\ell\}$.
\end{lem}

\begin{proof}
  Suppose that $|X \cap P_i^\ell| \leq 1$, then there is some $j \in [4]$ so that $N(q_{i,j}^\ell) \cap X = \emptyset$, hence $X$ cannot be a total dominating set. Observe that $y_{i,2}^\ell$ is a degree-1 vertex, so $X$ must contain its neighbor $y_{i,1}^\ell$. To dominate $y_{i,1}^\ell \in Z_i^\ell$, $X$ must contain a vertex from $N(y_{i,1}^\ell) \subseteq Z_i^\ell$, recall that $Z_i^\ell$ also contains $y_{i,2}^\ell$.

  Now, suppose that the second condition holds. Due to the first part, we have that $|X \cap B_i^\ell| = 4$, in particular $|X \cap P_i^\ell| = 2$, $X \cap Q_i^\ell = \emptyset$, and $X \cap \{\hat{z}_{i,S}^\ell : S \in \mathcal{S}_i^\ell\} = \emptyset$, because $N(y_{i,1}^\ell) \subseteq Z_i^\ell \setminus \{\hat{z}_{i,S}^\ell : S \in \mathcal{S}_i^\ell\}$. Suppose that $X \cap P_i^\ell \notin \mathcal{S}_i^\ell$, then $X \cap P_i^\ell = \{p_{i,1}^\ell, p_{i,3}^\ell\}$ or $X \cap P_i^\ell = \{p_{i,2}^\ell, p_{i,4}^\ell\}$, but then $p_{i,3}^\ell$ or respectively $p_{i,2}^\ell$ is not dominated. To dominate $\hat{z}_{i, X \cap P_i^\ell}^\ell$, the total dominating set $X$ has to contain $z_{i, X \cap P_i^\ell}^\ell$, because all other neighbors of $\hat{z}_{i, X \cap P_i^\ell}^\ell$ are not in $X$. This concludes the proof.
\end{proof}

A total dominating set $X$ of $G(\sigma)$ does not necessarily repeat the same state on all segments $P_i^\ell$ of a path $P_i$. We need to study how $X$ transitions between different states on the same path. For this sake, we order the states according to their names, i.e.\ $\mathbf{1} < \mathbf{2} < \mathbf{3} < \mathbf{4}$, and every $\mathcal{S}_i^\ell$ inherits this ordering.

\begin{lem}
  \label{thm:tds_state_order}
  Suppose that $X$ is a total dominating set of $G(\sigma)$ with $|X \cap B_i^\ell| \leq 4$ for all $i$ and $\ell$. If $\mathbf{s}_i^\ell = X \cap P_i^\ell$ is the state of $X$ on $P_i^\ell$ and $\mathbf{\tilde{s}}_i^{\ell + 1} = X \cap P_i^{\ell + 1}$ is the state of $X$ on $P_i^{\ell + 1}$, then we must have that $\mathbf{\tilde{s}} \leq \mathbf{s}$.
\end{lem}

\begin{proof}
  Suppose that $\mathbf{\tilde{s}} > \mathbf{s}$. This implies that $\mathbf{s} \neq \mathbf{4}$. If $\mathbf{s} \leq \mathbf{2}$, then $p_{i,4}^\ell$ must be dominated by $p_{i,1}^{\ell + 1}$, so $\mathbf{\tilde{s}} \leq \mathbf{2}$ in this case, as the other states do not contain $p_{i,1}^{\ell + 1}$. If $(\mathbf{s, \tilde{s}}) = (\mathbf{1}, \mathbf{2})$ or $(\mathbf{s, \tilde{s}}) = (\mathbf{3}, \mathbf{4})$, then $p_{i,1}^{\ell + 1}$ is not dominated. This concludes the proof.
\end{proof}

\begin{lem}
 \label{thm:tds_to_sat}
 If $G(\sigma)$ has a total dominating size $X$ of size at most $4 m (3 \frac{n}{2} + 1) \frac{n}{2} + 2$, then $\sigma$ is satisfiable.
\end{lem}

\begin{proof}
 First, observe that $X$ must contain the vertices $h_1$ and $h'_1$ as both vertices have a degree-1 neighbor. There are in total $m (3 \frac{n}{2} + 1) \frac{n}{2}$ blocks $B_i^\ell$ and due to \cref{thm:tds_structure} $X$ has to contain at least four vertices in each. Thus, the budget for $X$ is fully allocated and we have that $|X \cap B_i^\ell| = 4$ for all $i$ and $\ell$. Also by \cref{thm:tds_structure}, we know that $X$ assumes one of our desired states on each $B_i^\ell$.

 Using the notation of \cref{thm:tds_state_order}, we say that a \emph{cheat} occurs if $\mathbf{\tilde{s}} < \mathbf{s}$. Due to \cref{thm:tds_state_order}, there can be at most $3$ cheats on each $P_i$. Since there are $\frac{n}{2}$ paths, at most $3 \frac{n}{2}$ regions can be spoiled by cheats. Hence, there is at least one $\gamma$ so that $R^\gamma$ does not contain a cheat.

 We will read off a satisfying truth assignment $\tau$ for $\sigma$ from region $R^\gamma$. The truth assignment for variable pair $i$ is given by $\tau_i = \kappa^{-1}(\mathbf{s})$, where $\mathbf{s}_i^{\gamma m} = X \cap P_i^{\gamma m} \in \mathcal{S}_i^{\gamma m}$. Since $R^\gamma$ does not contain any cheats, for a fixed $i$, the total dominating set $X$ will assume the same state on all blocks $B_i^{(\gamma - 1)m + j}$, $j \in [m]$. The desired truth assignment is given by $\tau = \tau_1 \cup \cdots \cup \tau_{n/2}$.

 Consider some clause $C_j$ and its associated clause vertex $\hat{c}_j^\gamma$ in region $R^\gamma$. Let $\ell = (\gamma - 1)m + j$. Since $X$ dominates the clause vertex, there is some $i$ so that $z_{i,X \cap P_i^\ell}^\ell \in X$. By construction, this means that the state of $X$ on $P_i^\ell$ corresponds to a satisfying truth assignment of clause $C_j$. By the previous paragraph this is the same state as the state of $X$ on $P_i^{\gamma m}$ which in turn corresponds to $\tau_i$, hence $\tau$ must satisfy clause $C_j$. Since the choice of $C_j$ was arbitrary, it follows that $\sigma$ is satisfiable.
\end{proof}

\begin{lem}
 \label{thm:tds_pw_bound}
 The pathwidth of $G(\sigma)$ is at most $n/2 + \Oh(1)$.
\end{lem}

\begin{proof}
  We prove this bound on the pathwidth by giving an appropriate strategy for the mixed-search-game, cf. \cref{thm:mixed_search}, on $G(\sigma)$ and we begin by placing four searchers on the endpoint guards $h_1, h_2, h'_1, h'_2$.

 We will sweep through the blocks from left to right in $m (3 \frac{n}{2} + 1)$ outer iterations. At the start of outer iteration $\ell$, there are searchers on all $p_{i,1}^\ell$. Let $\gamma$ and $j$ so that $\ell = (\gamma - 1)m + j$. We also place a searcher on $\hat{c}_j^\gamma$. Each outer iteration consists of $\frac{n}{2}$ inner iterations. In inner iteration $i$, we place searchers on all vertices of $B_i^\ell$ and afterwards remove all those searchers again except for the searcher on $p_{i,4}^\ell$. After all inner iterations have been performed, we remove the searcher on $\hat{c}_j^\gamma$ and slide all searchers on the $p_{i,4}^\ell$ to the $p_{i,1}^{\ell + 1}$ and proceed with the next outer iteration.

 Except for the $n / 2$ searchers on the $P_i$, at any point in the mixed-search-strategy we use at most a constant number of additional searchers. We are done by \cref{thm:mixed_search}.
\end{proof}

\begin{proof}[Proof of \cref{thm:tds_lb}]
 Suppose there is an algorithm $\mathcal{A}$ that solves \textsc{Total Dominating Set}\xspace in time $\Oh^*((4-\varepsilon)^{\pw(G)})$ for some $\varepsilon > 0$. Given a \textsc{Satisfiability}\xspace instance $\sigma$, we construct $G(\sigma)$ in polynomial time and then run $\mathcal{A}$ on $G(\sigma)$ and return its answer. This is correct by \cref{thm:sat_to_tds} and \cref{thm:tds_to_sat}. Due to \cref{thm:tds_pw_bound}, the running time is $\Oh^*((4-\varepsilon)^{\pw(G(\sigma))}) \leq \Oh^*((4-\varepsilon)^{n/2 + \Oh(1)}) \leq \Oh^*((4-\varepsilon)^{n/2}) \leq \Oh^*((2-\varepsilon')^n)$ for some $\varepsilon' > 0$. This running time contradicts SETH\xspace.
\end{proof}

\section{Introduction}

The goal of parameterized complexity is to leverage input structure to obtain faster algorithms than in the worst case and to identify types of algorithmically useful structure. The most prominent structural graph parameter is \emph{treewidth} which measures the size of \emph{separators} decomposing the graph. Many problems admit fast algorithms relative to treewidth and we are often able to certify their optimality assuming the \emph{Strong Exponential-Time Hypothesis} (SETH\xspace) \cite{CurticapeanLN18, CyganKN18, CyganNPPRW11, LokshtanovMS18}. Such (conditional) \emph{optimality results} allow us to conduct a precise study of the impact of structure on the running time, whereas otherwise the currently best running time might simply be an artifact due to the momentary lack of algorithmic tools and not inherent to the considered structure.

The structure captured by treewidth can be varied in several ways: In the \emph{sparse setting}, we may restrict the interplay of separators and/or allow additional connected components from some graph class $\mathcal{H}$; this yields notions such as treedepth as well as deletion resp.\ elimination distance to $\mathcal{H}$. In the \emph{dense setting}, we can additionally allow large and dense but structured separators; this yields e.g.\ clique-width and rank-width. Conceptually, the difference between these types of parameters is quite large: if the time complexity of the considered problem changes between these parameters, then identifying which structural feature caused this complexity jump is difficult.

In this work, we seek to delineate more exact structural thresholds between these parameters. This can be achieved by either designing algorithms relative to more permissible parameters or by establishing the same lower bounds relative to more restrictive parameters. We focus on the latter approach in a fine-grained setting, i.e., all considered problems can be solved in time $\Oh^*(c^k)$\footnote{The $\Oh^*$-notation suppresses factors that are polynomial in the input size.} for some constant $c$ and parameter value $k$ and we are concerned with the value of the base $c$.

For parameters other than treewidth far fewer optimality results are known. In particular, to the best of our knowledge, the only known fine-grained optimality results for \ensuremath{\textsf{NP}}\xspace-hard problems relative to a deletion distance are for $r$-\textsc{Coloring}\xspace~\cite{JaffkeJ17, LokshtanovMS18}, its generalization \textsc{List Homomorphism}\xspace~\cite{PiecykR21}, and an isolated result on \textsc{Connected Vertex Cover}\xspace~\cite{CyganDLMNOPSW16} which relies on connectivity and is conditioned on the \emph{Set Cover Conjecture}. The crux is that other lower bound proofs deal with more complex problems (involving e.g., deletion of vertices, packing of subgraphs etc.) by copying the same (type of) partial solution over a large number of \emph{noncrossing} separators; this addresses several obstacles but also makes the approach unsuitable for deletion distance parameters (or even for treedepth). We show that a much broader range of problems may admit such improved lower bounds by giving the first tight lower bounds for \emph{vertex selection problems} (other than \textsc{Connected Vertex Cover}\xspace) relative to deletion distance parameters, in both sparse and dense setting.

Our main problem of study is \textsc{Deletion to $\ncols$-Colorable}\xspace which specializes to \textsc{Vertex Cover}\xspace for $r = 1$ and to \textsc{Odd Cycle Transversal}\xspace for $r = 2$. The first parameterization which we study for \textsc{Deletion to $\ncols$-Colorable}\xspace, $r \geq 2$, is the size $|X|$ of a \emph{modulator} $X \subseteq V(G)$, or deletion distance, to treewidth $r$, i.e., $\tw(G - X) \leq r$. Our main result in the sparse setting is the following.
\begin{thm}
  \label{thm:intro_lb_sparse}
  If there are $r \geq 2$, $\varepsilon < 1$ such that \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((r + 1 - \varepsilon)^{|X|})$, where $X$ is a modulator to treewidth $r$, then SETH\xspace fails.\footnote{For our lower bounds, we assume that an appropriate decomposition is given, thus strengthening the lower bounds.}
\end{thm}
Via a simple ad-hoc construction, we obtain a specialized result for \textsc{Vertex Cover}\xspace.
\begin{thm}
  \label{thm:intro_lb_vc}
  If there is an $\varepsilon < 1$ such that \textsc{Vertex Cover}\xspace can be solved in time $\Oh^*(2^{|X|})$, where $X$ is a modulator to pathwidth 2, i.e., $\pw(G - X) \leq 2$, then SETH\xspace fails.
\end{thm}
These results improve on the known lower bounds for \textsc{Vertex Cover}\xspace and \textsc{Odd Cycle Transversal}\xspace parameterized by pathwidth and provide new tight lower bounds for $r \geq 3$ as a matching upper bound can be easily obtained by generalizing the known algorithm for \textsc{Odd Cycle Transversal}\xspace parameterized by treewidth. Both the pathwidth bound for \textsc{Vertex Cover}\xspace and the treewidth bound for \textsc{Odd Cycle Transversal}\xspace, i.e., $r = 2$, cannot be improved, because Lokshtanov et al.~\cite{LokshtanovNRRS14} have shown that \textsc{Vertex Cover}\xspace and \textsc{Odd Cycle Transversal}\xspace parameterized by odd cycle transversal can be solved in time $\Oh^*(1.5214^k)$ and $\Oh^*(2.3146^k)$ respectively and any \emph{feedback vertex set}, i.e., a modulator to treewidth 1, is also an odd cycle transversal. Lokshtanov et al.~\cite{LokshtanovMS18} asked if the complexity of problems, other than $r$-\textsc{Coloring}\xspace (where a modulator to a single path is already sufficient~\cite{JaffkeJ17}), relative to treewidth could already be explained with parameterization by feedback vertex set. As argued, this cannot be true for \textsc{Vertex Cover}\xspace and \textsc{Odd Cycle Transversal}\xspace, so our results are essentially the next best explanation.

Furthermore, the previous two theorems also imply the same lower bound for parameterization by \emph{treedepth} which decomposes the graph into a hierarchy of nested separators.\footnote{\label{footnote:mod_tw_td}If $\tw(G - X) \leq t$, then $\td(G) \leq |X| + (t + 1) \log_2 |V|$ and $\Oh^*(c^{\td(G)}) = \Oh^*(c^{|X|}|V|^{(t+1)\log_2 c}) = \Oh^*(c^{|X|})$.} Thus yielding the first tight lower bounds relative to treedepth for vertex selection problems and partially resolving a question of Jaffke and Jansen~\cite{JaffkeJ17} regarding the complexity relative to treedepth for problems studied by Lokshtanov et al.~\cite{LokshtanovMS18}.
\begin{cor}
  \label{thm:intro_lb_td}
  If there is an $r \geq 1$ and an $\varepsilon < 1$ such that \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((r + 1 - \varepsilon)^{\td(G)})$, then SETH\xspace fails.
\end{cor}

Moving on to clique-width, our results on deletion distances can actually be lifted to the \emph{dense setting}. We do so by considering \emph{twinclasses}, which are arguably the simplest form of dense structure. A twinclass is an equivalence class of the \emph{twin}-relation, which says that two vertices $u$ and $v$ are twins if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$, i.e., $u$ and $v$ have the same neighborhood outside of $\{u,v\}$. Given two distinct twinclasses, either all edges between them exist or none of them do. Contracting each twinclass yields the \emph{quotient graph} $G^q$ and we obtain \emph{twinclass-variants} of the usual graph parameters treedepth, pathwidth, and treewidth by measuring these parameters on the quotient graph $G^q$, e.g., the \emph{twinclass-pathwidth} of $G$ is $\tcpw(G) = \pw(G^q)$. The parameters twinclass-pathwidth and twinclass-treewidth have been studied before under the name \emph{modular pathwidth} and \emph{modular treewidth}~\cite{Lampis20, Mengel16, PaulusmaSS16}. Furthermore, we remark that the previously studied parameter \emph{neighborhood diversity} satisfies $\nd(G) = |V(G^q)|$ \cite{Lampis12}. Relationships between parameters transfer to their twinclass-variants and twinclass-pathwidth is more restrictive than \emph{linear-clique-width}. Similarly, we obtain \emph{twinclass-modulators}, but we measure the complexity of the remaining components on the level of the original graph, i.e., a twinclass-modulator $\mathcal{X}$ to treewidth $r$ is a family $\mathcal{X}$ of twinclasses such that $\tw(G - \bigcup_{X \in \mathcal{X}} X) \leq r$. We can now state our second main result.
\begin{thm}
 \label{thm:intro_lb_dense}
 If there are $r \geq 2$, $\varepsilon < 1$ such that \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((2^r - \varepsilon)^{|\mathcal{X}|})$, where $\mathcal{X}$ is a twinclass-modulator to treewidth $r$, then SETH\xspace fails.
\end{thm}
We complement this result by a tight algorithmic upper bound which relies on standard techniques for dynamic programming on graph decompositions such as the $(\min,+)$-\emph{cover product}.
\begin{thm}
 \label{thm:intro_algo_dense}
 Given an $k$-expression $\mu$ for $G$, \textsc{Deletion to $\ncols$-Colorable}\xspace on $G$ can be solved in time $\Oh^*((2^r)^k)$.\footnote{Jacob et al.~\cite{JacobBDP21} have simultaneously proven this upper and lower bound for the special case of \textsc{Odd Cycle Transversal}\xspace, $r = 2$, parameterized by clique-width. Their construction also proves the lower bound for linear-clique-width, but not for the more restrictive twinclass-treedepth or twinclass-modulator like our construction.}
\end{thm}
Note that there is no further lower bound result for \textsc{Vertex Cover}\xspace, this is due to the fact that $r + 1 = 2^r$ for $r = 1$ and hence \cref{thm:intro_lb_vc} already yields a tight lower bound for the clique-width-parameterization. Again, \cref{thm:intro_lb_dense} implies the same lower bound for twinclass-treedepth.
\begin{cor}
 \label{thm:intro_lb_tctd}
 If there are $r \geq 2$, $\varepsilon < 1$ such that \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((2^r - \varepsilon)^{\tctd(G)})$, then SETH\xspace fails.
\end{cor}

Going into more detail, the twinclasses of the modulator in the construction for \cref{thm:intro_lb_dense} are \emph{true twinclasses}, i.e., each twinclass induces a clique, and moreover they are of size $r$ (with a small exception). Intuitively, allowing for deletions, there are $2^r$ possible sets of at most $r$ colors that can be assigned to a clique of size $r$, e.g., the empty set $\emptyset$ corresponds to fully deleting the clique. Intuitively, our results show that it is necessary and optimal to go through all of these color sets.

In contrast, consider the situation for $r$-\textsc{Coloring}\xspace. Lampis~\cite{Lampis20} has shown that $r$-\textsc{Coloring}\xspace can be solved in time $\Oh^*\left(\binom{r}{\lfloor r / 2 \rfloor}^{\tctw(G)}\right)$ when parameterized by twinclass-treewidth and in time $\Oh^*((2^r - 2)^{\cw(G)})$ when parameterized by clique-width and corresponding tight lower bounds for parameterization by twinclass-pathwidth and linear-clique-width. First of all, for $r$-\textsc{Coloring}\xspace the complexity when parameterized by clique-width is not already explained by the twinclass-setting. This complexity jump does not exist for \textsc{Deletion to $\ncols$-Colorable}\xspace. Secondly, let us discuss the different bases. The base $\binom{r}{\lfloor r / 2 \rfloor}$ in the twinclass-case is due to the fact that without deletions we can only attain color sets of the same size as the considered twinclass and the number of such sets is maximized when the size is $\lfloor r / 2 \rfloor$ or $\lceil r / 2 \rceil$. For clique-width, a \emph{label class} may induce more complicated graphs than just cliques and independent sets and the edge structure between two label classes can be more intricate as well. Lampis~\cite{Lampis20} shows that the extremal cases of color sets $\emptyset$ and $[r] = \{1, \ldots, r\}$ can be handled separately, thus yielding the base $2^r - 2$ for clique-width.

As a separate result, we improve the parameterization of the tight lower bound for \textsc{Dominating Set}\xspace obtained by Katsikarelis et al.~\cite{KatsikarelisLP19} from linear-clique-width to twinclass-pathwidth. To do so, we show that \textsc{Total Dominating Set}\xspace parameterized by pathwidth can be reduced to \textsc{Dominating Set}\xspace parameterized by twinclass-pathwidth. Using the standard approach of Lokshtanov et al.~\cite{LokshtanovMS18}, we obtain a lower bound for \textsc{Total Dominating Set}\xspace parameterized by pathwidth which implies the same lower bound for \textsc{Dominating Set}\xspace parameterized by twinclass-pathwidth. To be precise, we obtain the following results.
\begin{thm}
 If there is any $\varepsilon < 1$ such that \textsc{Total Dominating Set}\xspace can be solved in time $\Oh^*((4 - \varepsilon)^{\pw(G)})$, then SETH\xspace fails.
\end{thm}
\begin{thm}
 If there is any $\varepsilon < 1$ such that \textsc{Dominating Set}\xspace can be solved in time $\Oh^*((4 - \varepsilon)^{\tcpw(G)})$, then SETH\xspace fails.
\end{thm}

Lastly, as further consequences of the lower bound for \textsc{Vertex Cover}\xspace, \cref{thm:intro_lb_vc}, we also obtain the following tight lower bounds for \textsc{Maximum Cut}\xspace and \textsc{$K_\ncols$-free Deletion}\xspace, which again imply the same lower bounds parameterized by treedepth. Like the main result, the lower bound for \textsc{Maximum Cut}\xspace parameterized by treedepth also partially answers a question of Jaffke and Jansen~\cite{JaffkeJ17}.
\begin{cor}
  If \textsc{Maximum Cut}\xspace can be solved in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to treewidth at most 2, then SETH\xspace is false.
\end{cor}
\begin{cor}
  Let $r \geq 3$. If \textsc{$K_\ncols$-free Deletion}\xspace can be solved in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to treewidth at most $r - 1$, then SETH\xspace is false.
\end{cor}

\subparagraph*{Technical contribution.}
Let us describe which technical hurdles we have to overcome in proving our main results and how we do so. We start by recalling the standard approach of Lokshtanov et al.~\cite{LokshtanovMS18} to proving tight lower bounds for problems parameterized by pathwidth at a high level. Given a \textsc{Satisfiability}\xspace instance $\sigma$, the variables are partitioned into $t$ groups of constant size. For each variable group, a \emph{group gadget} is constructed that can encode all assignments of this variable group into partial solutions of the considered target problem. The group gadget usually consists of a bundle of long path-like gadgets inducing a sequence of \emph{disjoint} separators. Further gadgets attached to these separators decode the partial solutions and check whether the corresponding assignment satisfies some clause. Ideally, the path gadgets are designed so that a partial solution transitions through a well-defined sequence of states when viewed at consecutive separators. For most problems, the gadgets do not behave this nicely though. For example, in \textsc{Odd Cycle Transversal}\xspace it is locally always preferable to delete a vertex instead of not deleting it. Such behavior leads to undesired state changes called \emph{cheats}, but for appropriate path gadgets there can only be a constant number of cheats on each path. By making the path gadgets long enough, one can then find a region containing no cheats where we can safely decode the partial solutions.

For problems such as $r$-\textsc{Coloring}\xspace, all states are equally constraining and such cheats do not occur, hence enabling us to prove the same lower bounds under more restrictive parameters such as feedback vertex set in this case. But for \emph{vertex-deletion problems} like the mentioned \textsc{Odd Cycle Transversal}\xspace, these cheats do occur and pose a big issue when trying to compress the path gadgets into a single separator $X$. On a single separator $X$ such behavior means that one partial solution is \emph{dominating} another and if we cannot control this behavior, then we lose the dominated partial solution for the purpose of encoding group assignments. Concretely, for \textsc{Odd Cycle Transversal}\xspace we obtain dominating partial solutions by deleting further vertices in the single separator $X$. The number of deletions is bounded from above by the \emph{budget constraint}, but if we limit the number of deletions in $X$, then we do not have $3^{|X|}$ partial solutions anymore and the construction may not be able to attain the desired base in the running time.

To resolve this issue we expand upon a technique of Cygan et al.~\cite{CyganDLMNOPSW16} and construct an instance with a slightly large parameter value, i.e., a slightly larger single separator $X$. Thus, we can consider only a restricted family of partial solutions on $X$ and the restricted family is still able to encode sufficiently many group assignments. We restrict the partial solutions so that only pairwise non-dominating partial solutions remain, for \textsc{Odd Cycle Transversal}\xspace we achieve this by only considering partial solutions with the same number of deletions in $X$. To enforce this restriction, we construct a \emph{structure gadget} providing a lower bound on the number of deletions in $X$. A positive side effect is that the remaining gadgets can also leverage the structure of the partial solutions.

In the dense setting and especially for a higher number $r$ of colors, this issue is amplified. Here, we consider the states of twinclasses in a partial solution and not of single vertices. Whereas we had one dominating vertex state in the sparse setting, there is now a hierarchy of dominating states: any state that does not delete all vertices in the twinclass is dominated by a state that deletes further vertices in the twinclass. For \textsc{Deletion to $\ncols$-Colorable}\xspace, the maximum number of states is achieved on a true twinclass of size $r$ and we can partition the states into levels based on the number of deletions they induce. Within each level, the states are pairwise non-dominating. Consequently, we restrict the family of partial solutions so that for every level the number of twinclasses with that level is fixed. This requires a more involved construction of the structure gadget which now has to distinguish states based on their level.

\subparagraph*{Related work.}
We begin by surveying the literature on SETH\xspace-based parameterized lower bounds for \ensuremath{\textsf{NP}}\xspace-hard problems. As mentioned, there is a long line of work relative to treewidth~\cite{BorradaileL16, CurticapeanLN18, CyganKN18, CyganNPPRW11, DubloisLP21a, DubloisLP21b, EgriMR18, KatsikarelisLP18, LokshtanovMS18, OkrasaPR20, OkrasaR20} and all of these lower bounds, except for the result by Egri et al.~\cite{EgriMR18}, already apply to pathwidth.
In the sparse setting, there is further work on the two incomparable, but more restrictive than pathwidth, parameterizations by \emph{cutwidth}~\cite{CurticapeanM16, JansenN19, PiecykR21, GeffenJKM20} and by feedback vertex set~\cite{LokshtanovMS18, PiecykR21}. We remark that the works of van Geffen et al.~\cite{GeffenJKM20} and Piecyk and Rz{\k a}\.{z}ewski~\cite{PiecykR21} also show that previous lower bounds relative to pathwidth already hold for more restrictive parameterizations.
In the dense setting, there are some results~\cite{IwataY15, JacobBDP21, KatsikarelisLP19, Lampis20} on parameterization by clique-width and these lower bounds already apply to linear-clique-width, but not to the more restrictive parameters that we consider. The work by Iwata and Yoshida~\cite{IwataY15} also provides equivalences between different lower bounds  and works under a weaker assumption than SETH\xspace, unfortunately their techniques would blow up the size of the modulator by too much and are therefore not applicable in our case.
Finally, the complexity of $r$-\textsc{Coloring}\xspace and the more general homomorphism problems has been extensively studied~\cite{EgriMR18, JaffkeJ17, Lampis20, OkrasaPR20, OkrasaR20, PiecykR21}, with the exception of Lampis' results~\cite{Lampis20} on $r$-\textsc{Coloring}\xspace these results only concern the sparse setting. In particular, Jaffke and Jansen~\cite{JaffkeJ17} closely study the complexity of $r$-\textsc{Coloring}\xspace parameterized by the deletion distance to various graph classes $\mathcal{F}$; they also show that $r$-\textsc{Coloring}\xspace parameterized by the deletion distance to a single path has the same complexity as when parameterized by treewidth.

On the algorithmic side, the study of heterogeneous parameterizations has been gaining traction~\cite{BulianD16, BulianD17, EibenGHK21, EibenGS18a, EibenGS18b, HolsKP20, JansenKW21}, yielding the notions of $\mathcal{H}$-treewidth and $\mathcal{H}$-\emph{elimination distance}, which is a generalization of treedepth, where $\mathcal{H}$ is a class of graphs. In particular, the problem of computing $\mathcal{H}$-elimination distance is receiving considerable attention~\cite{AgrawalKLPRS21, AgrawalKPRS21, AgrawalR20, FominGT21, JansenK21}. At the moment of writing, only few of these of these works~\cite{EibenGHK21, JansenKW21} contain algorithmic results that are sufficiently optimized to apply to our fine-grained setting. Jansen et al.~\cite{JansenKW21} show that \textsc{Vertex Cover}\xspace can be solved in time $\Oh^*(2^k)$ and \textsc{Odd Cycle Transversal}\xspace in time $\Oh^*(3^k)$ when parameterized by the bipartite-treewidth. Eiben et al.~\cite{EibenGHK21} show that \textsc{Maximum Cut}\xspace can be solved in time $\Oh^*(2^k)$ when parameterized by $\mathcal{R}_w$-treewidth, where $\mathcal{R}_w$ denotes the graphs of \emph{rank-width} at most $w$.

Another line of work is on depth-parameters in the dense setting~\cite{ChenF20, DeVosKO20, GajarskyK20, GajarskyLO13, GanianHNOM19, HlinenyKOO16, KwonMOW21} such as \emph{shrub-depth} and \emph{sc-depth}. The algorithmic results relative to these parameters are largely concerned with meta-results so far~\cite{ChenF20, GanianHNOM19} and their relation to clique-width is not strong enough to preserve the complexity in our fine-grained setting.

\subparagraph*{Organization.}
We discuss the preliminaries and basic notation in \cref{sec:prelims}. In \cref{sec:outline}, we give an outline of our two main results: the lower bound for \textsc{Deletion to $\ncols$-Colorable}\xspace in the sparse setting and the dense setting. \cref{sec:parameters} discusses the relationships between the considered parameters in more detail. The algorithm for \textsc{Deletion to $\ncols$-Colorable}\xspace parameterized by clique-width is given in \cref{sec:cw_algo}. We present the proofs of the main results in \cref{sec:dtc_lb}. The specialized lower bound for \textsc{Vertex Cover}\xspace and its consequences can be found in \cref{sec:vc}. Lastly, \cref{sec:ds_lb} contains the lower bound for \textsc{Dominating Set}\xspace and in \cref{sec:problems} we give the formal definitions of all considered problems. We conclude in \cref{sec:conclusion}.

\section{Outline of Main Result}
\label{sec:outline}
In this section, we present an outline of our two main results, i.e., tight lower bounds for \textsc{Deletion to $\ncols$-Colorable}\xspace parameterized by a modulator to treewidth $r$ or parameterized by a twinclass-modulator to treewidth $r$. We begin with some general statements regarding \textsc{Deletion to $\ncols$-Colorable}\xspace, then discuss the lower bound for the sparse setting, and finally discuss the lower bound for the dense setting. We consider the number of colors $r \geq 2$ to be fixed for the remainder of this section.

We view \emph{solutions} to \textsc{Deletion to $\ncols$-Colorable}\xspace as functions $\varphi \colon V(G) \rightarrow [r] \cup \{\bot\}$ with the property that for every edge $\{u,v\} \in E(G)$ either $\varphi(u) = \bot$ or $\varphi(v) = \bot$ or $\varphi(u) \neq \varphi(v)$. Hence, ${\coloring^{-1}(\del)}$ is the set of deleted vertices and the cost of a solution is $|{\coloring^{-1}(\del)}|$, whereas $\varphi\big|_{V(G) \setminus {\coloring^{-1}(\del)}}$ is an $r$-coloring of the remaining graph.

Conceptually, the constructions for the sparse setting and for the dense setting are similar. the most significant change is in the so-called \emph{structure gadget}, since the structure we enforce in the dense setting is considerably more involved than in the sparse setting, whereas the other gadgets only change to a much lesser degree.

In both settings, we want a gadget that simulates a \emph{logical OR} constraint. For \textsc{Odd Cycle Transversal}\xspace, i.e.\ $r = 2$, this is achieved by simply using \emph{odd cycles}: odd cycles are only $3$-colorable, but deleting any vertex results in a $2$-colorable graph, thus implementing an OR over all vertices in the odd cycles. For $r \geq 3$, we construct an infinite family $\mathcal{H}^r$ containing graphs of treewidth $r$ that are $(r + 1)$-\emph{critical}, i.e., $\chi(H) = r + 1$ and $\chi(H - v) = r$ for all $H \in \mathcal{H}^r$ and $v \in V(H)$.

Given a $q$-\textsc{Satisfiability}\xspace instance $\sigma$ with $n$ variables and $m$ clauses, the constructions begin with the following standard step~\cite{LokshtanovMS18}: we partition the variables into $t = \lceil n / {p_0} \rceil$ groups of size ${p_0}$, where ${p_0}$ only depends on the running time base that we want to rule out. Furthermore, we pick an integer $p$ depending on ${p_0}$ that represents the corresponding size of groups in the graph.

\subsection{Sparse Setting}

We construct a graph $G$ so that $G$ has a solution $\varphi$ for \textsc{Deletion to $\ncols$-Colorable}\xspace with cost $|{\coloring^{-1}(\del)}| \leq b$ if and only if $\sigma$ is satisfiable. To convert from base $r + 1$ to base $2$ means that $G$ should admit a modulator $X$ to treewidth $r$ of size roughly $n \log_{r + 1}(2)$. Like Cygan et al.~\cite{CyganDLMNOPSW16}, we make the modulator slightly larger, thus picking a larger $p$. The modulator $X $ consists of $t + 1$ vertex groups: the first $t$ groups $U_i$, $i \in [t]$, are independent sets of size $p$ each and correspond to the variable groups; the last group $F$ is a clique of size $r$ which simulates \textsc{List Coloring}\xspace constraints.

On each group $U_i$, we consider the set of partial solutions $\Phi_i = \{\varphi \colon U_i \rightarrow [r] \cup \{\bot\} : |{\coloring^{-1}(\del)}| = p / (r + 1) \}$. Due to picking $p$ large enough, $\Phi_i$ is sufficiently large to encode all truth assignments for the $i$-th variable group. Defining $\Phi_i$ in this way achieves two things: first, as mentioned in the introduction, these partial solutions are pairwise non-dominating; secondly, this fixes the budget used on the modulator. The second point is important, because by also fixing the budget on the remaining graph via a vertex-disjoint packing $\mathcal{P}$ of $(r + 1)$-critical graphs, we can then ensure that no vertex of $F$ can be deleted. Otherwise, we would not be able to simulate \textsc{List Coloring}\xspace constraints with $F$ and, unlike for the treewidth-parameterization, we cannot afford to copy $F$ over and over again.

The next step is to enforce that the solutions in $\Phi_i$ are indeed the only partial solutions that can be attained on group $U_i$. By choosing the budget $b$ appropriately, we obtain an upper bound on the number of deletions. To obtain a lower bound, we construct the \emph{structure gadget}. This can be achieved by combining $(r + 1)$-critical graphs with the \emph{arrow} gadget of Lokshtanov et al.~\cite{LokshtanovMS18}. An arrow simply propagates a deletion from one vertex $u$ to another vertex $v$ for free; if $u$ is not deleted, then $v$ is not deleted and the arrow does not affect the remaining graph.

The structure gadget works as follows: suppose $\varphi$ deletes less than $p / (r + 1)$ vertices in group $U_i$, then there is a subset $S \subseteq U_i$ of size $|S| = (|U_i| - p / (r + 1)) + 1$ that avoids all deletions in $U_i$. For every subset of this size, $G$ contains a $(r + 1)$-critical graph $L_{i,S}$ with an arrow from every $u \in S$ to a private vertex $v$ in $L_{i,S}$, hence simulating an OR on the vertices in $S$. Since $S$ avoids all deletions of $\varphi$, no deletion is propagated to $L_{i,S}$ and $\varphi$ must pay extra to resolve $L_{i,S}$. By copying each $L_{i,S}$ sufficiently often (which is possible since $L_{i,S}$ does not belong to the modulator), we can ensure that the existence of a deletion-avoiding $S$ implies that $\varphi$ must exceed our budget constraint.

The remaining part of the construction decodes the partial solution on the modulator $X$ and verifies whether the corresponding truth assignment satisfies all clauses of $\sigma$. In principle, one could generalize the gadgets of Lokshtanov et al.~\cite{LokshtanovMS18} to higher $r$ and design an interfacing gadget transferring the states from the modulator to achieve this. The result is a more involved construction though with a worse bound on the treewidth of the remainder: for \textsc{Odd Cycle Transversal}\xspace the construction of the decoding gadget of Lokshtanov et al.\ has treewidth 4, whereas the simpler present construction has treewidth 2, which is optimal as mentioned in the introduction.

We proceed by giving a high-level explanation of the simpler construction. First, we can simulate a logical AND by using a complete $(r + 1)$-partite graph with all sets of the partition being singletons except for one large set. In addition to the arrows, we design gadgets that also propagate a deletion to a vertex $v$ if the color at a vertex $u$ matches a specified color. By connecting a group $U_i$ to \emph{AND-gadgets} via these \emph{color-gadgets} and arrows, we can decode the partial solution at $U_i$, meaning that an AND-gadget corresponding to this partial solution is satisfied.

Finally, we construct the \emph{clause gadgets}. We create an $(r + 1)$-critical graph $Z^j$ for the $j$-th clause and add arrows from appropriate AND-gadgets to $Z^j$, so that a deletion is only propagated to $Z^j$ if the corresponding truth assignment satisfies the $j$-th clause.

\subsection{Dense Setting}

We now move on to the dense setting, where we have a twinclass-modulator $\mathcal{X}$ to treewidth $r$ instead of a basic modulator. First of all, consider the impact of this change on the possible states. Whereas $\varphi$ could assume $r + 1$ different states on a single vertex $u$, i.e., one of the $r$ colors or deleting the vertex, there are $2^{r}$ possible states on a true twinclass $U$ of size $r$; each state corresponds to a possible value of $\varphi(U) \setminus \{\bot\} \subseteq [r]$. Since $U$ is a true twinclass, no color can be used several times and it does not matter how the colors are assigned to the vertices in $U$; a vertex that is not assigned a color is simply deleted.

While we need to choose ${p_0}$ and $p$ differently compared to the sparse setting due to the different base and more involved structure, they essentially play the same role as before. The twinclass-modulator $\mathcal{X}$ of the constructed graph $G$ again consists of $t + 1$ groups, but each group is a family of twinclasses now. The first $t$ groups $\mathcal{U}_i$, $i \in [t]$, correspond to the variable groups and each group consists of $p$ true twinclasses of size $r$ that are pairwise non-adjacent. The last group only contains the clique $F$.

Our family $\Phi_i$ of considered partial solutions on group $\mathcal{U}_i$ should achieve the same two things as before. Let us first consider the structure of states of $\varphi$ on a twinclass $U \in \mathcal{U}_i$ more precisely: fix a state $C = \varphi(U) \setminus \{\bot\}$ and notice that all states $C' \subsetneq C$ \emph{dominate} $C$ if we disregard the budget constraint, i.e., $\varphi$ remains a solution if we replace $C$ by $C'$. If we arrange the possible states into \emph{levels} according to the number of used colors, or dually the number $\ell$ of deleted vertices, then there is no domination between states on the same level. Motivated by this behavior, we define $\Phi_i$ so that for every level $\ell \in \{0\} \cup [r]$ there are exactly $c_\ell$ twinclasses with a state of level $\ell$ in $\mathcal{U}_i$. The $c_\ell$ are chosen in such a way that partial solutions where all states appear the same number of times are still possible. Essentially, we are only restricting how a solution may distribute the deletions inside the modulator; there are no restrictions on the used colors. We omit the technical definition of $\Phi_i$ here and note that this fixes the budget used on the modulator again, allowing us to safely simulate \textsc{List Coloring}\xspace constraints with the clique $F$.

Enforcing the structure of $\Phi_i$ is more involved this time and requires a new ingredient: we need a gadget that can distinguish different number of deletions inside a twinclass. We are able to construct a gadget $A_\ell(U,v)$, $\ell \in [r]$, that propagates a deletion to the vertex $v$ if at least $\ell$ deletions occur in the true twinclass $U$, hence $A_\ell(U,v)$ behaves similarly to an arrow and is accordingly called a \emph{thick $\ell$-arrow}. Observe that we need a new type of arrow whenever we increment the number $r$ of colors. Starting at $\ell = r$, we can ensure that there are at least $c_r$ twinclasses in group $\mathcal{U}_i$ where all vertices are deleted by an analogous construction to the sparse setting with thick $r$-arrows instead of arrows. More generally, for any $\ell \in [r]$, we can ensure that there are at least $c_{\ell} + c_{\ell + 1} + \cdots + c_r$ twinclasses in group $\mathcal{U}_i$ where at least $\ell$ vertices are deleted by using thick $\ell$-arrows. By setting the budget $b$ appropriately, these lower bounds must be tight and it follows that the deletions inside $\mathcal{U}_i$ follow the distribution imposed by $\Phi_i$.

Finally, it remains to discuss the decoding part of the construction. Structurally it is very similar to the sparse setting, but we need a generalization of the color-gadgets to handle the twinclasses in the modulator. Given a set of colors $C \subsetneq [r]$, we design a \emph{color-set-gadget} that propagates a deletion to a vertex $v$ only if $\varphi(U) \setminus \{\bot\} \subseteq C$ at a true twinclass $U$. Using the structure of solutions in $\Phi_i$, the color-set-gadgets are sufficient to distinguish the solutions in $\Phi_i$. Since the color-set-gadgets can only check for inclusion and not equality, they would not be sufficient if there was a pair of solutions in $\Phi_i$ with one dominating the other.
\section{Relations between Parameters}
\label{sec:parameters}

We first discuss the relationships between the considered parameters and then provide equivalent definitions for treewidth and pathwidth via \emph{search games}.

\begin{lem}[Chapter 6 of \cite{NesetrilO12}]
  \label{thm:td_tw}
  For any graph $G$, we have that $\tw(G) \leq \pw(G) \leq \td(G) - 1$ and $\td(G) \leq (\tw(G) + 1) \log_2 |V(G)|$. These inequalities come with algorithms that can transform the appropriate decomposition in polynomial time.
\end{lem}

\begin{cor}
  \label{thm:mod_to_tw_implies_td}
  For any graph $G = (V, E)$ and $c, r \in \mathbb{N}$, if there is a modulator $X \subseteq V$ to treewidth $r$, i.e., $\tw(G - X) \leq r$, then we have that $\td(G) \leq |X| + (r + 1) \log_2 |V|$. In particular, we have that $\Oh^*(c^{\td(G)}) \leq \Oh^*(c^{|X|})$ for all $c \geq 1$. The decompositions can be transformed in polynomial time.
\end{cor}

\begin{proof}
  Let $X$ be a modulator to treewidth $r$ for $G$. By \cref{thm:td_tw}, there is an elimination forest $\EF$ of depth at most $(r + 1) \log_2 |V|$ for $G - X$. We can construct an elimination forest $\EF'$ of depth at most $|X| + (r + 1) \log_2 |V|$ for $G$ by creating a single path that contains the vertices in $X$ and attaching $\EF$ below this path.
  To see the claim regarding the $\Oh^*$-notation, see \cref{footnote:mod_tw_td}.
\end{proof}

\begin{thm}
  \label{thm:hierarchy_cliquewidth}
  Let $G = (V, E)$ be a graph. We have that
  \begin{equation*}
    \cw(G) \leq \lcw(G) \leq \tcpw(G) + 3 \leq \tctd(G) + 2 \leq \td(G) + 2.
  \end{equation*}
\end{thm}

\begin{proof}
  Follows from \cite[Lemma 2.1]{Lampis20}, \cref{thm:td_tw} and the last inequality follows from the fact that $G / \Pi_{tc}(G)$ is a subgraph of $G$ and that treedepth is subgraph-monotone.
\end{proof}

\begin{lem}
  \label{thm:tcm_tctd}
  Suppose that $G$ admits a TCM $\mathcal{X}$ to treewidth $r$, then $\tctd(G) \leq |\mathcal{X}| + (r + 1) \log_2 |V(G/\Pi_{tc}(G))|$. In particular, we have for any $c \geq 1$ that $\Oh^*(c^{\tctd(G)}) \leq \Oh^*(c^{|\mathcal{X}|})$. The decompositions can be transformed in polynomial time.
\end{lem}

\begin{proof}
  Since $G/\Pi_{tc}(G) - \mathcal{X}$ is an induced subgraph of $G - \bigcup(\mathcal{X})$, we see that $\tw(G/\Pi_{tc}(G) - \mathcal{X}) \leq \tw(G - \bigcup(\mathcal{X})) \leq r$. By \cref{thm:td_tw}, we construct an elimination forest $\TT$ for $G/\Pi_{tc}(G) - \mathcal{X}$ of depth at most $(r + 1) \log_2 |V(G/\Pi_{tc}(G))|$ in polynomial time. To obtain an elimination forest $\TT'$ for $G/\Pi_{tc}(G)$ of depth at most $|\mathcal{X}| + (r + 1) \log_2 |V(G/\Pi_{tc}(G))|$, we arrange the vertices of $G/\Pi_{tc}(G)$ corresponding to the twinclasses in $\mathcal{X}$ in a path and attach $\TT$ below this path. The inequality follows analogously to \cref{footnote:mod_tw_td}.
\end{proof}

\subsection*{Search Games}

To prove that the graphs in our lower bound constructions have small treewidth or pathwidth, it is easier to use \emph{search game} characterizations instead of directly constructing a tree or path decomposition.

\subparagraph*{Cops and Robbers.} The search game corresponding to treewidth is the \emph{omniscient-cops-and-robber-game}. In this game $k + 1$ cops try to capture a robber on a graph $G$. The cops can occupy vertices of $G$ and the robber can run at infinite speed along edges through vertices that are not occupied by cops. The cops and the robber are omniscient in that they know each others position at all times. At the start, the cops are placed on some vertices and the robber chooses a starting vertex for the escape. In every round some cops get into their helicopters and declare where they will land next. Before these cops land again, the robber may move to any other vertex that is reachable by a path that does not contain any non-airborne cop. Afterwards the cops land and the next round begins. The cops \emph{win} if they have a \emph{strategy} to capture the robber by landing on the robber's location after a finite number of rounds; otherwise the robber wins.

\begin{thm}[\cite{SeymourT93}]
  \label{thm:cops_robber}
  A graph $G$ has treewidth at most $k$ if and only if $k + 1$ cops can win the omniscient-cops-and-robber-game on $G$.
\end{thm}

\subparagraph*{Mixed-search.} The search game corresponding to pathwidth is the \emph{mixed-search-game}. In such a game, the graph $G$ represents a system of tunnels where all edges are contaminated by a gas. The objective is to clear all edges of this gas. An edge can be cleared by either placing searchers at both of its endpoints or by moving a searcher along the edge. If there is a path from an uncleared edge to a cleared edge without any searchers on the vertices or edges of the path, then the cleared edge is recontaminated. A \emph{search strategy} is a sequence of operations of the following types: a searcher can be placed on or removed from a vertex, and a searcher on a vertex can be moved along an incident edge and placed on the other endpoint. We say that a search strategy is \emph{winning} if after its termination all edges are cleared. The \emph{mixed-search-number} of a graph $G$, denoted $\ms(G)$, is the minimum number of searchers required for a winning strategy of the mixed-search-game on $G$.

\begin{lem}[\cite{TakahashiUK95}]
  \label{thm:mixed_search}
  We have that $\pw(G) \leq \ms(G) \leq \pw(G) + 1$.
\end{lem}

\section{Preliminaries}
\label{sec:prelims}

If $n$ is a number, we define $[n] = \{1, \ldots, n\}$. Let $S$ be a set, we define $\mathcal{P}(S) = \{T \subseteq S\}$ and if $0 \leq k \leq |S|$, we define $\binom{S}{k} = \{T \subseteq S : |T| = k\}$ and $\binom{S}{\leq k} = \{T \subseteq S : |T| \leq k\}$ and $\binom{S}{\geq k}$ analogously. If $0 \leq k \leq n$, we define $\binom{n}{\leq k} = |\binom{[n]}{\leq k}|$ and similarly $\binom{n}{\geq k}$. If $\mathcal{S}$ is a set family, we define $\bigcup(\mathcal{S}) = \bigcup_{S \in \mathcal{S}} S$. If $f \colon A \rightarrow C$ is a function and $B \subseteq A$, then $f\big|_B$ denotes the \emph{restriction} of $f$ to $B$. If $f,g\colon A \rightarrow B$ are two functions, we write $f \equiv g$ if $f(a) = g(a)$ for all $a \in A$. If $p$ is a boolean predicate, we let $[p]$ denote the \emph{Iverson bracket} of $p$, which is $1$ if $p$ is true and $0$ if $p$ is false.

We use common graph-theoretic notation and assume that the reader knows the essentials of parameterized complexity. Let $G = (V, E)$ be an undirected graph. For a vertex set $X \subseteq V$, we denote by $G[X]$ the subgraph of $G$ that is induced by $X$. The \emph{open neighborhood} of a vertex $v$ is given by $N(v) = \{u \in V : \{u,v\} \in E\}$, whereas the \emph{closed neighborhood} is given by $N[v] = N(v) \cup \{v\}$. For sets $X \subseteq V$ we define $N[X] = \bigcup_{v \in X} N[v]$ and $N(X) = N[X] \setminus X$. For two disjoint vertex subsets $A, B \subseteq V$, adding a \emph{join} between $A$ and $B$ means adding all edges between $A$ and $B$. For a vertex set $X \subseteq V$, we define $\delta(X) = \{ \{x, y\} \in E : x \in X, y \notin X\}$.

An \emph{$r$-coloring} of a graph $G = (V,E)$ is a function $\varphi \colon V \rightarrow [r]$ such that $\varphi(u) \neq \varphi(v)$ for all $\{u,v\} \in E$. We say that $G$ is \emph{$r$-colorable} if there is an $r$-coloring of $G$. The \emph{chromatic number} of $G$, denoted by $\chi(G)$, is the minimum $r$ such that $G$ is $r$-colorable.

\subparagraph*{Quotients and twins.} Let $\Pi$ be a partition of $V(G)$. The \emph{quotient graph} $G / \Pi$ is given by $V(G / \Pi) = \Pi$ and $E(G / \Pi) = \{\{B_1, B_2\} : \exists u \in B_1, v \in B_2 \colon \{u,v\} \in E(G)\}$. We say that two vertices $u, v$ are \emph{twins} if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$. The equivalence classes of this relation are called \emph{twinclasses}. More specifically, if $N(u) = N(v)$, then $u$ and $v$ are \emph{false twins} and if $N[u] = N[v]$, then $u$ and $v$ are \emph{true twins}. Every twinclass of size at least 2 consists of only false twins or only true twins. Let $\Pi_{tc}(G)$ be the partition of $V(G)$ into twinclasses.

\subsection{Graph Parameters}

\begin{dfn}
 A \emph{tree/path decomposition} of a graph $G$ consists of a tree/path $\TT$ and bags $\mathbb{B}_t \subseteq V(G)$ for all $t \in V(\TT)$, such that:
 \begin{itemize}
  \item $V(G) = \bigcup_{t \in V(\TT)} \mathbb{B}_t$.
  \item For every edge $\{u, v\} \in E(G)$, there is a node $t \in V(\TT)$ such that $\{u, v\} \subseteq \mathbb{B}_t$.
  \item For every $v \in V(G)$, the set $\{t \in V(\TT) : v \in \mathbb{B}_t\}$ induces a connected subgraph of $\TT$.
 \end{itemize}
 The \emph{width} of a tree/path decomposition is equal to $\max_{t \in V(\TT)} |\mathbb{B}_t| - 1$. The \emph{treewidth} of $G$, denoted $\tw(G)$, is the minimum possible width of a tree decomposition of $G$. The \emph{pathwidth} of $G$, denoted $\pw(G)$, is the minimum possible width of a path decomposition of $G$.
\end{dfn}

\paragraph*{Clique-Width.}

A \emph{labeled graph} is a graph $G = (V,E)$ together with a label function $\ell \colon V \rightarrow \mathbb{N} = \{1, 2, 3, \ldots\}$. We say that a labeled graph is \emph{$k$-labeled} if $\ell(v) \leq k$ for all $v \in V$. For a label $i$, we denote by $G^i$ the subgraph induced by the vertices with label $i$, i.e.\ $G^i = G[\ell^{-1}(i)]$. We consider the following three operations on labeled graphs: the \emph{union}-operation $\union{G_1}{G_2}$ constructs the disjoint union of two labeled graphs $G_1$ and $G_2$; the \emph{relabel}-operation $\relab{i}{j}{G}$ changes the label of all vertices in $G$ with label $i$ to label $j$; the \emph{join}-operation $\join{i}{j}{G}$, $i \neq j$, adds all possible edges between vertices in $G$ with label $i$ and vertices in $G$ with label $j$.
As a base case, we have the \emph{introduce}-operation $\intro{i}(v)$ which constructs a single-vertex graph whose unique vertex $v$ has label $i$. A valid expression that only consists of introduce-, union-, relabel-, and join-operations is called a \emph{clique-expression}. The labeled graph constructed by a clique-expression $\mu$ is denoted $G(\mu)$. To a clique-expression $\mu$ we associate a syntax tree $\mathcal{T}_\mu$ in the natural way and to each node $t \in V(\mathcal{T}_\mu)$ the corresponding operation. For any node $t \in V(\mathcal{T}_\mu)$, the subtree rooted at $t$ induces a subexpression $\mu_t$ and we define $G_t = G(\mu_t)$ as the labeled graph constructed by $\mu_t$.

We say that a clique-expression $\sigma$ is a \emph{$k$-clique-expression} or just \emph{$k$-expression} if $G_t$ is $k$-labeled for all $t \in V(\mathcal{T}_\mu)$. The \emph{clique-width} of a graph $G$, denoted by $\cw(G)$, is the minimum $k$ such that there exists a $k$-expression $\mu$ such that $G$ is isomorphic to $G(\mu)$ after forgetting the labels. A clique-expression $\mu$ is \emph{linear} if in every union-operation the second graph consists only of a single node. Accordingly, we also define the \emph{linear-clique-width} of a graph $G$, denoted $\lcw(G)$, by only considering linear clique-expressions.

\paragraph*{Treedepth and Modulators.}

 We will construct graphs that have small treewidth except for one central part. This structure is captured by the concept of a \emph{modulator}. We say that $X \subseteq V(G)$ is a \emph{modulator to treewidth/pathwidth $r$} for $G$ if $\tw(G - X) \leq r$ or $\pw(G - X) \leq r$, respectively.

\begin{dfn}
 An \emph{elimination forest} of an undirected graph $G = (V, E)$ is a rooted forest $\EF = (V, E_\EF)$ so that for every edge $\{u, v\} \in E$ either $u$ is an ancestor or descendant of $v$ in $\EF$. The \emph{depth} of a rooted forest is the largest number of nodes on a path from a root to a leaf. The \emph{treedepth} of $G$, denoted $\td(G)$, is the minimum depth over all elimination forests of $G$.
\end{dfn}

\paragraph*{Lifting to Twinclasses.}

 We define the \emph{twinclass-treewidth}, \emph{twinclass-pathwidth}, and \emph{twinclass-treedepth} of $G$ is defined respectively by $\tctw(G) = \tw(G/\Pi_{tc}(G))$, $\tcpw(G) = \pw(G/\Pi_{tc}(G))$, and $\tctd(G) = \td(G/\Pi_{tc}(G))$. The parameters twinclass-treewidth and twinclass-pathwidth have been considered before under the name modular treewidth and modular pathwidth~\cite{Lampis20, Mengel16, PaulusmaSS16}.

\begin{dfn}
  Let $G = (V,E)$ be a graph. A \emph{twinclass-modulator (TCM)} $\mathcal{X} \subseteq \Pi_{tc}(G)$ of $G$ to treewidth $r$ is a set of twinclasses of $G$ such that $\tw(G - \bigcup(\mathcal{X})) \leq r$. The \emph{size} of a twinclass-modulator $\mathcal{X}$ is $|\mathcal{X}|$, i.e., the number of twinclasses $\mathcal{X}$ contains.
\end{dfn}

\subsection{Strong Exponential-Time Hypothesis}

We base our lower bounds on the \emph{Strong Exponential-Time Hypothesis} (SETH\xspace) \cite{ImpagliazzoPZ01} which concerns the complexity of $q$-\textsc{Satisfiability}\xspace, i.e., \textsc{Satisfiability}\xspace where all clauses contain at most $q$ literals. For all $q \geq 3$, we define $c_q = \inf \{\delta : q\text{-\textsc{Satisfiability}\xspace can be solved in time } \Oh(2^{\delta n}) \}$. The weaker \emph{Exponential-Time Hypothesis} (ETH) of Impagliazzo and Paturi~\cite{ImpagliazzoP01} posits that $c_3 > 0$, whereas the Strong Exponential-Time Hypothesis states that $\lim_{q \rightarrow \infty} c_q = 1$.
When proving lower bounds based on SETH\xspace, we make use of the following equivalent formulations.

\begin{thm}[\cite{CyganDLMNOPSW16}]
 \label{thm:seth_hitting_set}
 The following statements are equivalent to SETH\xspace:
 \begin{enumerate}
  \item For all $\delta < 1$, there is a $q$ such that $q$-\textsc{Satisfiability}\xspace cannot be solved in time $\Oh(2^{\delta n})$, where $n$ is the number of variables.
  \item For all $\delta < 1$, there is a $q$ such that $q$-\textsc{Hitting Set}, i.e., all sets contain at most $q$ elements, cannot be solved in time $\Oh(2^{\delta n})$, where $n$ is the universe size.
 \end{enumerate}
\end{thm}

\section{Problem Definitions}
\label{sec:problems}

\makeatletter
\newcolumntype{\expand}{}
\long\@namedef{NC@rewrite@\string\expand}{\expandafter\NC@find}

\NewEnviron{problem}[2][]{%
  \def\problem@arg{#1}%
  \def\problem@framed{framed}%
  \def\problem@lined{lined}%
  \def\problem@doublelined{doublelined}%
  \ifx\problem@arg\@empty%
    \def\problem@hline{}%
  \else%
    \ifx\problem@arg\problem@doublelined%
      \def\problem@hline{\hline\hline}%
    \else%
      \def\problem@hline{\hline}%
    \fi%
  \fi%
  \ifx\problem@arg\problem@framed%
    \def\problem@tablelayout{|>{\bfseries}lX|c}%
    \def\problem@title{\multicolumn{2}{|l|}{%
        \raisebox{-\fboxsep}{\textsc{\Large #2}}%
      }}%
  \else
    \def\problem@tablelayout{>{\bfseries}lXc}%
    \def\problem@title{\multicolumn{2}{l}{%
        \raisebox{-\fboxsep}{\textsc{\Large #2}}%
      }}%
  \fi%
  \bigskip\par\noindent%
  \renewcommand{\arraystretch}{1.2}%
  \begin{tabularx}{\textwidth}{\expand\problem@tablelayout}%
    \problem@hline%
    \problem@title\\[2\fboxsep]%
    \BODY\\\problem@hline%
  \end{tabularx}%
  \medskip\par%
}
\makeatother

\begin{problem}[doublelined]{Vertex Cover}
 Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $Y \subseteq V$, $|Y| \leq b$, such that $G - Y$ contains no edges, i.e., $\chi(G - Y) \leq 1$?
\end{problem}

\begin{problem}[doublelined]{Odd Cycle Transversal}
 Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $Y \subseteq V$, $|Y| \leq b$, such that $G - Y$ is bipartite, i.e., $\chi(G - Y) \leq 2$?
\end{problem}

\begin{problem}[doublelined]{Deletion to $r$-Colorable}
 Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $Y \subseteq V$, $|Y| \leq b$, such that $\chi(G - Y) \leq r$?
\end{problem}

\begin{problem}[doublelined]{Satisfiability}
 Input: & A boolean formula $\sigma$ in conjunctive normal form.
 \\
 Question: & Is there a satisfying assignment $\tau$ for $\sigma$?
\end{problem}

\begin{problem}[doublelined]{$q$-Satisfiability}
 Input: & A boolean formula $\sigma$ in conjunctive normal form with clauses of size at most $q$.
 \\
 Question: & Is there a satisfying assignment $\tau$ for $\sigma$?
\end{problem}

\begin{problem}[doublelined]{$q$-Hitting Set}
 Input: & An universe $U$ and a set family $\mathcal{F}$ over $U$ of sets of size at most $q$ and an integer $t$.
 \\
 Question: & Is there a set $H \subseteq U$, $|H| \leq t$, such that $H \cap S \neq \emptyset$ for all $S \in \mathcal{F}$?
\end{problem}

\begin{problem}[doublelined]{$r$-Coloring}
 Input: & An undirected graph $G = (V, E)$.
 \\
 Question: & Is $\chi(G) \leq r$?
\end{problem}

\begin{problem}[doublelined]{List $r$-Coloring}
 Input: & An undirected graph $G = (V, E)$, lists $L(v) \subseteq [r]$ for all $v \in V$.
 \\
 Question: & Is there an $r$-Coloring $\varphi \colon V \rightarrow [r]$ of $G$ such that $\varphi(v) \in L(v)$ for all $v \in V$?
\end{problem}

\begin{problem}[doublelined]{Maximum Cut}
 Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $Y \subseteq V$, such that $|\delta(Y)| \geq b$?
\end{problem}

\begin{problem}[doublelined]{$H$-free Deletion}
 Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $Y \subseteq V$, $|Y| \leq b$, such that $G - Y$ is $H$-free?
\end{problem}

\begin{problem}[doublelined]{Dominating Set}
 Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $X \subseteq V$, $|X| \leq b$, such that $N[X] = V$?
\end{problem}

\begin{problem}[doublelined]{Total Dominating Set} Input: & An undirected graph $G = (V, E)$ and an integer $b$.
 \\
 Question: & Is there a set $X \subseteq V$, $|X| \leq b$, such that $\bigcup_{v \in X} N(v) = V$?
\end{problem}

\begin{problem}[doublelined]{$(b, r)$-center}
 Input: & An undirected graph $G = (V, E)$ and an integers $b$ and $r$.
 \\
 Question: & Is there a set $X \subseteq V$, $|X| \leq b$, such that every vertex $v \in V$ is at most at distance $r$ to $X$?
\end{problem}

\subsection{Sparse Setting}
\label{sec:dtc_lb_td}

We again view \emph{solutions} to \textsc{Deletion to $\ncols$-Colorable}\xspace as functions $\varphi \colon V(G) \rightarrow [r] \cup \{\bot\}$ with the property discussed in the outline, cf.~\cref{sec:outline}.

In this subsection, we show how to adapt the lower bound for the dense setting to the sparse setting. We will give the construction in full detail again, but since the principle of constructions is so similar we will only explain how to adapt the previous proofs. One can see that the lower bound is tight by a routine application of dynamic programming on tree decompositions.

\begin{thm}
 \label{thm:dtc_lower_bound_td}
 If \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((r + 1 - \varepsilon)^{|X|})$ for some $r \geq 2$ and $\varepsilon > 0$, where $X$ is a modulator to treewidth $r$, then SETH\xspace is false.
\end{thm}

The remainder of this section is devoted to proving \cref{thm:dtc_lower_bound_td}. Assume that we can solve \textsc{Deletion to $\ncols$-Colorable}\xspace in time $\Oh^*((r + 1 - \varepsilon)^{|X|})$ for some $r \geq 2$ and $\varepsilon > 0$. We provide for all clause sizes $q$, a reduction from $q$-\textsc{Satisfiability}\xspace with $n$ variables to \textsc{Deletion to $\ncols$-Colorable}\xspace with a modulator to treewidth $r$ of size approximately $n \log_{r + 1}(2)$. Together with the assumed faster algorithm, this implies a faster algorithm for $q$-\textsc{Satisfiability}\xspace, thus violating SETH\xspace. We will consider $r$ to be fixed from now on.

\paragraph*{Construction.} Consider a $q$-\textsc{Satisfiability}\xspace instance $\sigma$ with $n$ variables and $m$ clauses. We enumerate the clauses and refer to them by their number. We pick an integer ${p_0}$ which only depends on $\varepsilon$ and $r$; we will describe how to choose ${p_0}$ later. We partition the variables of $\sigma$ into groups of size at most ${p_0}$, resulting in $t = \lceil n / {p_0} \rceil$ groups which will be indexed by $i$. Next, we choose the smallest integer $p$ such that $p$ is divisible by $r + 1$ and $(r + 1)^p / (p + 1) \geq 2^{p_0}$. We will now describe the construction of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $G = G(\sigma, r, {p_0})$.

\subparagraph*{Comparison to dense setting.}
The principle behind construction is essentially the same as for the dense setting, cf. \cref{sec:dtc_lb_cw}, but the gadgets can be simplified. The central twinclasses will simply be single vertices now. Hence, we will not have to distinguish between different numbers of deletions in a twinclass, instead we simply distinguish between whether a vertex is deleted or not. Most notably, this allows us to use thin arrows instead of thick $\ell$-arrows and the structure of the considered partial solutions on the central vertices simplifies significantly. The remaining gadgets structurally stay the same, but their size may change.

\subparagraph*{Construction of central vertices.} The central vertices of $G$ form the modulator to treewidth $r$. For each variable group $i \in [t]$, we create an independent set $U_i$ consisting of $p$ vertices. Furthermore, we again have a central clique $F = \{f_s : s \in [r]\}$ consisting of $r$ vertices that is used to simulate \textsc{List Coloring}\xspace constraints. A solution $\varphi \colon V \rightarrow [r] \cup \{\bot\}$ satisfying ${\coloring^{-1}(\del)} \cap F = \emptyset$ and $\varphi(f_s) = s$ for all $s \in [r]$ is called a \emph{normalized solution}.

As described in the outline, we only want to consider solutions that delete a fixed number of vertices per group $U_i$. By using slightly more vertices $p$ than enforced by the base conversion, sufficiently many solutions remain if we define $\Phi_i$ as follows:
\begin{equation*}
 \Phi_i = \{\varphi \colon U_i \rightarrow [r] \cup \{\bot\} : |{\coloring^{-1}(\del)}| = p / (r + 1) \}
\end{equation*}

\begin{lem}
 If $p \geq r + 1$, then we have that $|\Phi_i| \geq (r + 1)^p / (p + 1)$.
\end{lem}

\begin{proof}
 First, notice that $|\Phi_i| = \sum_{c_1 + \cdots + c_r = \frac{r}{r + 1}p} \binom{p}{c_1, \ldots, c_r, \frac{p}{r + 1}}$.
 The function mapping the number $c_{r + 1}$ to  $\sum_{c_1 + \cdots + c_r = p - c_{r + 1}} \binom{p}{c_1, \ldots, c_{r + 1}}$ is maximized by setting $c_{r + 1} = p / (r + 1)$. Hence, $(r + 1)^p = \sum_{c_1 + \cdots + c_{r + 1} = p} \binom{p}{c_1, \ldots, c_{r + 1}} = \sum_{c_{r + 1} = 0}^p \sum_{c_1 + \cdots + c_r = p - c_{r + 1}} \binom{p}{c_1, \ldots, c_{r + 1}}$ must imply that $|\Phi_i| = \sum_{c_1 + \cdots + c_r = \frac{r}{r + 1}p} \binom{p}{c_1, \ldots, c_r, \frac{p}{r + 1}} \geq (r + 1)^p / (p + 1)$.
\end{proof}

Hence, by the choice of $p$, we can pick for each group $i \in [t]$ an efficiently computable injective mapping $\kappa_i \colon \{0,1\}^{p_0} \rightarrow \Phi_i$ that maps truth assignments of the $i$-th variable group to partial solutions on $U_i$ with the desired structure.

\subparagraph*{Budget.} The budget $b = |\mathcal{P}| + t p / (r + 1)$ consists of two parts again. The first part $|\mathcal{P}|$ is allocated to a vertex-disjoint packing $\mathcal{P}$ of $(r + 1)$-critical graphs and the second part $t p / (r + 1)$ is allocated to the central vertices.

\subparagraph*{Enforcing structure on central vertices.} For every group $i \in [t]$ and subset $S \subseteq U_i$ with $|S| = \frac{r}{r + 1} p + 1$, we add an $(r + 1)$-critical graph, denoted $L_{i,S}$, consisting of at least $|S|$ vertices. For every $u \in S$, we pick a private vertex $v$ in $L_{i,S}$ and add a thin arrow from $u$ to $v$. We create $1 + t p / (r + 1) = 1 + (b - |\mathcal{P}|)$ copies of $L_{i,S}$ and the incident arrows. This concludes the construction of the structure gadget.

\subparagraph*{Decoding gadgets.} For the $j$-th clause, group $i \in [t]$, partial solution $\varphi_i \in \Phi_i$, we construct a decoding gadget $Y^j_{i, \varphi_i}$ as follows. The gadget $Y^j_{i, \varphi_i}$ consists of a large independent set joined to a $K_r$, i.e., adding all edges between both sets. In other words, $Y^j_{i, \varphi_i}$ is a complete $(r + 1)$-partite graph with one large independent set and all other independent sets in the partition are singletons. The large independent set consists of $p + 1$ vertices, where one of these vertices is distinguished and denoted by $\hat{y}^j_{i, \varphi_i}$. This concludes the construction of $Y^j_{i, \varphi_i}$.

For the $j$-th clause, group $i \in [t]$, partial solution $\varphi_i \in \Phi_i$, vertex $u \in U_i$, we pick a private vertex $v \neq \hat{y}^j_{i, \varphi_i}$ in the large independent set of $Y^j_{i, \varphi_i}$ and add the decoding gadget $B_{\{\varphi_i(u)\} \setminus \{\bot\}}(\{u\},v)$ and denote this instance of the decoding gadget by $W^j_{i, \varphi_i, u}$.

\subparagraph*{Clause gadgets.} For the $j$-th clause, we add an $(r + 1)$-critical graph, denoted $Z^j$, consisting of at least $q 2^{p_0}$ vertices. For every group $i \in [t]$ and partial solution $\varphi_i \in \Phi_i$ such that $\kappa^{-1}(\varphi_i)$ is a partial truth assignment satisfying the $j$-th clause, we pick a private vertex $v$ in $Z^j$ and add a thin arrow from $\hat{y}^j_{i, \varphi_i}$ to $v$. We ensured that $Z^j$ is large enough so that we can always pick such a private vertex. This concludes the construction of $G(\sigma, r, {p_0})$.

\subparagraph*{Packing.} We construct a vertex-disjoint packing $\mathcal{P}$ of $(r + 1)$-critical graphs that fully explains the budget outside of the central vertices. For every thin arrow from $u$ to $v$ in the construction, we add the $K_{r + 1}$ induced by the deletion edge incident to $v$ to the packing $\mathcal{P}$. Every $B_{\{\varphi_i(u)\} \setminus \{\bot\}}(\{u\},v)$ contains, depending on whether $\varphi_i(u) \neq \bot$ or not, $r$ or $r + 1$ disjoint $K_{r + 1}$ corresponding to deletion edges, one of them being incident to $v$, and we add all these $K_{r + 1}$ to the packing $\mathcal{P}$. Finally, for every $Y^j_{i, \varphi_i}$, we add the $K_{r + 1}$ induced by $\hat{y}^j_{i, \varphi_i}$ and the $K_r$ of $Y^j_{i, \varphi_i}$ to the packing $\mathcal{P}$. Since, we have added only $(r + 1)$-critical graphs to $\mathcal{P}$, the cost of $\mathcal{P}$ is simply $|\mathcal{P}|$.

\begin{thm}
 Let $\sigma$ be a $q$-\textsc{Satisfiability}\xspace instance with $n$ variables and $m$ clauses. Let $G = G(\sigma, r, {p_0})$ and $\mathcal{P}$ be the graph and packing as constructed above and let $b = |\mathcal{P}| + t p / (r + 1)$. If $\sigma$ has a satisfying truth assignment $\tau$, then there is a solution $\varphi$ of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $(G, b)$.
\end{thm}

\begin{proof}[Proof sketch]
 The proof is very similar to the proof of \cref{thm:sat_to_dtc}. Let $\tau_i$ be the partial truth assignment of variable group $i$ induced by $\tau$. We set $\varphi\big|_{U_i} = \kappa_i(\tau_i) \in \Phi_i$ for all $i$ and $\varphi(f_s) = s$ for all $s \in [r]$. By definition of $\Phi_i$, only the budget $|\mathcal{P}|$ for the packing $\mathcal{P}$ remains, hence on every graph in $\mathcal{P}$, we can perform exactly one deletion and nowhere else.

 We propagate deletions along thin arrows and extend the solution across decoding gadgets $B_{\{\varphi_i(u)\} \setminus \{\bot\}}(\{u\},v)$ as before. For every $Y^j_{i, \varphi_i}$, we delete the distinguished vertex $\hat{y}^j_{i, \varphi_i}$ and for every $j$-th clause, group $i$, and solution $\varphi_i \neq \psi_i \in \Phi_i$, we pick one of the vertices in the $K_r$ of $Y^j_{i, \varphi_i}$ and delete it. This concludes the description of the deletions.

 It remains to show that the remaining graph can be properly $r$-colored. Comparing to the proof of \cref{thm:sat_to_dtc}, the arguments change slightly for $L_{i,S}$ and $Y^j_{i, \psi_i}$. Consider some copy of some $L_{i,S}$, due to $|S| + |{\coloring^{-1}(\del)} \cap U_i| = (\frac{r}{r + 1} p + 1) + p / (r + 1) = p + 1 > |U_i|$ there is a least one $u \in S$ with $\varphi(u) = \bot$. Therefore, the thin arrow from $u$ to $L_{i,S}$ propagates a deletion to $L_{i,S}$ and this $(r + 1)$-critical graph is resolved.

 Consider some $Y^j_{i, \psi_i}$ with $\psi_i \in \Phi_i$. If $\psi_i \neq \varphi_i$, the arguments works as in the proof of \cref{thm:sat_to_dtc}. If $\psi_i = \varphi_i$, then we claim that the large independent set of $Y^j_{i, \varphi_i}$ is fully deleted. The large independent set has size $p + 1 = |U_i| + 1$. We distributed one deletion to $\hat{y}^j_{i, \varphi_i}$ and all other vertices $v$ in the large independent set are hit by some $W^j_{i, \varphi_i, u}$, $u \in U_i$. Since $\varphi_i(u) \in \{\varphi_i(u)\}$, we see that $W^j_{i, \varphi_i, u} = B_{\{\varphi_i(u)\} \setminus \{\bot\}}(\{u\},v)$ propagates a deletion to $v$ due to \cref{thm:decode_behavior}. So, the large independent set is indeed fully deleted and thereby the complete $(r + 1)$-partite graph is resolved.
\end{proof}

\begin{thm}
 \label{thm:enforced_structure_td}
 Let $\sigma$ be a $q$-\textsc{Satisfiability}\xspace instance with $n$ and $m$ clauses. Let $G = G(\sigma, r, {p_0})$ and $\mathcal{P}$ be the graph and packing as constructed above and let $b = |\mathcal{P}| + t p / (r + 1)$. If $\varphi$ is a solution of the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $(G, b)$, then $|{\coloring^{-1}(\del)}| = b$. Furthermore, there is a normalized solution $\psi$ with $|\psi^{-1}(\bot)| = |{\coloring^{-1}(\del)}| = b$ and $\psi\big|_{U_i} \in \Phi_i$ for all $i \in [t]$.
\end{thm}

\begin{proof}
 Since the packing $\mathcal{P}$ consists only of $(r + 1)$-critical graphs, at least $|\mathcal{P}|$ deletions must be performed by $\varphi$ on these graphs. The remainder of the deletions is performed on the central vertices. Suppose that there is some group $i \in [t]$ such that $|{\coloring^{-1}(\del)} \cap U_i| < p / (r + 1)$, then there exists an $S \subseteq U_i$ with $|S| = \frac{r}{r + 1} p + 1$ and $S \cap {\coloring^{-1}(\del)} = \emptyset$. Consider some copy of the corresponding $L_{i,S}$ and notice that all thin arrows leading to $L_{i,S}$ are passive unless we pay for extra deletions. Since $L_{i,S}$ is an $(r + 1)$-critical graph that does not belong to $\mathcal{P}$, we must perform one additional deletion per copy of $L_{i,S}$. There are $1 + t p/(r + 1) > b - |\mathcal{P}|$ copies of $L_{i,S}$, hence this would exceed the available budget. So, we can conclude that $|{\coloring^{-1}(\del)} \cap U_i | \geq p / (r + 1)$ for all groups $i \in [t]$.

 Together with $|{\coloring^{-1}(\del)}| \leq b = |\mathcal{P}| + t p / (r + 1)$, we see that $|{\coloring^{-1}(\del)}| = b$ and $|{\coloring^{-1}(\del)} \cap U_i | = p / (r + 1)$ for all $i \in [t]$. Hence, $\varphi$ cannot delete any vertex of the central clique $F$ and by permuting the colors, we obtain the desired normalized solution $\psi$ with $\psi\big|_{U_i} \in \Phi_i$.
\end{proof}

\begin{thm}
 Let $\sigma$ be a $q$-\textsc{Satisfiability}\xspace instance with $n$ variables and $m$ clauses. Let $G = G(\sigma, r, {p_0})$ and $\mathcal{P}$ be the graph and packing as constructed above and let $b = |\mathcal{P}| + t p / (r + 1)$. If the \textsc{Deletion to $\ncols$-Colorable}\xspace instance $(G, b)$ has a solution $\varphi$, then $\sigma$ has a satisfying truth assignment $\tau$.
\end{thm}

\begin{proof}[Proof sketch]
 This proof is very similar to the proof of \cref{thm:dtc_to_sat}. We first invoke \cref{thm:enforced_structure_td}, which implies that $|{\coloring^{-1}(\del)}| = b$ and allows us to assume that $\varphi$ is a normalized solution with $\varphi_i := \varphi\big|_{U_i} \in \Phi_i$. We only diverge from the proof of \cref{thm:dtc_to_sat} when proving that $\varphi(\hat{y}^j_{i, \psi_i}) = \bot$ only if $\psi_i = \varphi_i$.

 As before, $\hat{y}^j_{i, \psi_i}$ may only be deleted if the large independent set of $Y^j_{i, \psi_i}$ is fully deleted. Now, consider some $\psi_i \in \Phi_i \setminus \{\varphi_i\}$. We will distinguish two cases.
 \begin{enumerate}
  \item Suppose that $\psi_i^{-1}(\bot) \neq \varphi_i^{-1}(\bot)$. Due to $\varphi_i, \psi_i \in \Phi_i$, there exists some $u \in U_i$ with $\psi_i(u) = \bot$ and $\varphi_i(u) \neq \bot$. The associated $W^j_{i, \psi_i, u} = B_{\emptyset}(\{u\},v)$ cannot propagate a deletion to $v$ in this case by \cref{thm:decode_behavior}.
  \item Suppose that $\psi_i^{-1}(\bot) = \varphi_i^{-1}(\bot)$, then $\psi_i \neq \varphi_i$ implies that there exists some $u \in U_i \setminus \psi_i^{-1}(\bot) = U_i \setminus \varphi_i^{-1}(\bot)$ with $\psi_i(u) \neq \varphi_i(u)$. Again, the associated $W^j_{i, \psi_i, u} = B_{\{\psi_i(u)\}}(\{u\},v)$ cannot propagate a deletion to $v$ in this case by \cref{thm:decode_behavior}.
 \end{enumerate}
 This proves the claim regarding the deletion of $\hat{y}^j_{i, \psi_i}$.
\end{proof}

\begin{thm}
 \label{thm:dtc_tw_bound_td}
 Let $G = G(\sigma, r, {p_0})$ be the graph as constructed above. The set $X = \left(\bigcup_{i = 1}^t U_i\right) \cup \{f_s : s \in [r]\}$ is a modulator for $G$ of size $t p + r$ to treewidth $r$, i.e., $|X| = t p + r$ and $\tw(G - X) \leq r$.
\end{thm}

\begin{proof}[Proof sketch]
 The proof is very similar to the proof of \cref{thm:dtc_tw_bound}. The notable difference is that all thick arrows are replaced by thin arrows, but this does not affect the treewidth. The connected components corresponding to a clause have for the sake of the  omniscient cops-and-robber-game the same structure as before, only the number of $W^j_{i, \varphi_i, u}$ incident to some $Y^j_{i, \varphi_i}$ changes.
\end{proof}

\begin{proof}[Proof of \cref{thm:dtc_lower_bound_td}]
 Suppose there is some $r \geq 2$ and $\varepsilon > 0$ such that \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((r + 1 - \varepsilon)^{|X|})$, where $X$ is a modulator to treewidth $r$. We will show that there exists a $\delta < 1$, such that for any $q$, we can solve $q$-\textsc{Satisfiability}\xspace in time $\Oh^*(2^{\delta n})$ where $n$ is the number of variables. This contradicts SETH\xspace and hence implies the desired lower bound.

  Given a $q$-\textsc{Satisfiability}\xspace instance $\sigma$, we construct the graph $G = G(\sigma, r, {p_0})$, where ${p_0}$ depends only on $r$ and $\varepsilon$ and will be chosen later. We can consider $r$, $\varepsilon$, and $q$ as constants, hence also ${p_0} = {p_0}(r, \varepsilon)$ and $p = p({p_0})$ are constant. As in the proof of \cref{thm:dtc_lower_bound}, we can again see that $G$ has polynomial size and can be constructed in polynomial time. Furthermore, we can also obtain a tree decomposition of $G' := G - X$ from the proof of \cref{thm:dtc_tw_bound_td} in polynomial time.

  In the construction of $G(\sigma, r, {p_0})$, we chose $p$ as the smallest integer that is divisible by $(r + 1)$ and satisfies $(r + 1)^p / (p + 1) \geq 2^{p_0}$. We let $\gamma = \lceil \log_{r + 1}(2^{p_0}) \rceil$ and show that $p \leq \gamma + 4 \lceil \log_{r + 1}(\gamma) \rceil + (r + 1)$. The summand $(r + 1)$ accounts for the divisibility and will be disregarded from now on. We compute that
  \begin{equation*}
   \frac{(r + 1)^p}{p + 1} \geq \frac{(r + 1)^\gamma \gamma^4}{\gamma + 4 \lceil \log_{r + 1} \gamma \rceil + 1} \geq (r + 1)^\gamma \frac{\gamma^4}{6 \gamma} = (r + 1)^\gamma \frac{\gamma^{3}}{6} \geq (r + 1)^\gamma \frac{2^3}{6} \geq (r + 1)^\gamma \geq 2^{p_0},
  \end{equation*}
  where we use throughout that ${p_0}$ and hence $\gamma$ is sufficiently large.

  Running the assumed algorithm for \textsc{Deletion to $\ncols$-Colorable}\xspace on $G$ decides, by \cref{thm:sat_to_dtc} and \cref{thm:dtc_to_sat}, the satisfiability of $\sigma$. Since $G$ can be constructed in polynomial time, we can solve $q$-\textsc{Satisfiability}\xspace in time
  \begin{align*}
   \Oh^*((r + 1 - \varepsilon)^{|X|}) & = \Oh^*((r + 1 - \varepsilon)^{r + \lceil \frac{n}{{p_0}} \rceil p}) \leq \Oh^*((r + 1 - \varepsilon)^{\frac{n}{{p_0}} p}) \\
   & \leq \Oh^*((r + 1 - \varepsilon)^{\frac{n}{{p_0}} \log_{r + 1}(2^{p_0})} (r + 1 - \varepsilon)^{\frac{n}{{p_0}}(4 \lceil \log_{r + 1}(\gamma) \rceil + r + 2)}).
  \end{align*}
  For the first factor, we see that
  \begin{equation*}
   \Oh^*((r + 1 - \varepsilon)^{\frac{n}{{p_0}} \log_{r + 1}(2^{p_0})}) = \Oh^*((r + 1 - \varepsilon)^{n \log_{r + 1}(2)}) \leq \Oh^*(2^{\delta_1 n}),
  \end{equation*}
  where $\delta_1 < 1$. For the second factor, we obtain the bound
  \begin{alignat*}{4}
   \phantom{\leq} \quad & \Oh^*\left(\left(r + 1 - \varepsilon\right)^{\frac{n}{{p_0}}(4 \lceil \log_{r + 1}(\gamma) \rceil + r + 2)}\right)\quad & \leq \quad & \Oh^*\left(\left(r + 1 - \varepsilon\right)^{\frac{n}{{p_0}}(10 \log_{r + 1}(\gamma))}\right) \\
      = \quad & \Oh^*\left(\left(r + 1 - \varepsilon\right)^{\frac{n}{{p_0}}(10 \log_{r + 1}(\lceil \log_{r + 1}(2^{p_0}) \rceil))}\right) \quad & \leq \quad & \Oh^*\left(\left(r + 1 - \varepsilon\right)^{\frac{n}{{p_0}}(20 \log_{r + 1}{p_0})}\right) \\
   = \quad & \Oh^*\left(\left(r + 1 - \varepsilon\right)^{20n\frac{\log_{r + 1}{p_0}}{{p_0}}}\right) & = \quad & \Oh^*\left(\left(\left(r + 1 - \varepsilon\right)^{20\frac{\log_{r + 1}{p_0}}{{p_0}}}\right)^n\right) \\
   \leq \quad & \Oh^*\left(2^{\delta_2 n}\right),
  \end{alignat*}
  where $\delta_2$ can be made arbitrarily close to $0$ by choosing ${p_0}$ sufficiently large. By choosing $\delta_2$ so that $\delta := \delta_1 + \delta_2 < 1$, we obtain that $q$-\textsc{Satisfiability}\xspace can be solved in time $\Oh^*\left(2^{\delta n}\right)$. Since the choice of ${p_0}$ is independent of $q$, we obtain this running time for all $q$ and hence SETH\xspace has to be false.
\end{proof}

\begin{cor}
 If \textsc{Deletion to $\ncols$-Colorable}\xspace can be solved in time $\Oh^*((r + 1 - \varepsilon)^{\td(G)})$ for some $r \geq 2$ and $\varepsilon > 0$, then SETH\xspace is false.
\end{cor}

\begin{proof}
 Follows from \cref{thm:dtc_lower_bound_td} and \cref{thm:mod_to_tw_implies_td}.
\end{proof}

\section{Lower Bound for Vertex Cover}
\label{sec:vc}

In \cref{sec:vc_lb} we prove the lower bound for \textsc{Vertex Cover}\xspace parameterized by a modulator to pathwidth 2 and in \cref{sec:further_consequences} we show that this lower bound also implies lower bounds for \textsc{Maximum Cut}\xspace and \textsc{$K_\ncols$-free Deletion}\xspace.

\subsection{Lower Bound}
\label{sec:vc_lb}

This section is devoted to establishing the lower bound for \textsc{Vertex Cover}\xspace when parameterized by a modulator to pathwidth 2, i.e., \cref{thm:vc_lb}. For \textsc{Vertex Cover}\xspace, we do not need to convert between different bases in the running time. By additionally reducing from $q$-\textsc{Hitting Set}\xspace instead of $q$-\textsc{Satisfiability}\xspace, we obtain a significantly simplified reduction that does not require the trick of Cygan et al.~\cite{CyganDLMNOPSW16}. We construct a graph so that each vertex in the modulator corresponds to an element in the universe of the $q$-\textsc{Hitting Set}\xspace instance. We construct gadgets of pathwidth at most 2 that simulate the $q$-\textsc{Hitting Set}\xspace constraints on the modulator. Using \cref{thm:seth_hitting_set}, this implies the desired lower bound for \textsc{Vertex Cover}\xspace if SETH\xspace is true. \textsc{Vertex Cover}\xspace can be solved in time $\Oh^*(2^{\cw(G)})$ by an algorithm of Courcelle et al.~\cite{CourcelleMR00} and by \cref{thm:mod_to_tw_implies_td} and \cref{thm:hierarchy_cliquewidth} this implies that the obtained lower bound is tight. So, in the exceptional case of \textsc{Vertex Cover}\xspace, the complexity when parameterized by clique-width is already explained by the sparse setting and we do not need to consider twinclasses.

\begin{thm}
 \label{thm:vc_lb}
 If \textsc{Vertex Cover}\xspace can be solved in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to pathwidth at most 2, then SETH\xspace is false.
\end{thm}

\newcommand{W}{W}
\newcommand{\PP}[1]{{P}^{#1}}

 Suppose that we can solve \textsc{Vertex Cover}\xspace in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$. Fix an integer $q$ and let $(U = \{u_1, \ldots, u_n\}, \mathcal{F})$ be a $q$-\textsc{Hitting Set}\xspace instance with $|\mathcal{F}| = m$ sets of size at most $q$ each, and budget $t$. The elements of the $j$-th set in $\mathcal{F}$, $j \in [m]$, are denoted by $\{u^j_1, u^j_2, \ldots, u^j_{p_j}\}$, $p_j \leq q$. We will reduce $(U, \mathcal{F})$ to a \textsc{Vertex Cover}\xspace instance $G = G(U, \mathcal{F})$ with budget $b$, which will be defined later, and which admits  a modulator to pathwidth $2$ of size $n$.

\subparagraph*{Construction.}
 We create an independent set of $n$ central vertices $W = \{w_1, \ldots, w_n\}$. The vertices in $W$ that are chosen by a vertex cover will correspond to the hitting set. For the $j$-th set $\{u^j_1, u^j_2, \ldots, u^j_{p_j}\} \in \mathcal{F}$, $p_j \leq q$, we create a triangle path, denoted by $\PP{j}$: The triangle path $\PP{j}$ consists of $p_j$ vertices $a_{s}^j$, where $s \in [p_j]$, and $2p_j + 2$ vertices $b_{s}^j$, where $s \in [2p_j + 2]$, such that $a_{s}^j, b_{2s}^j, b_{2s + 1}^j$ form a triangle for all $s \in [p_j]$ and $b_1^j, b_2^j \ldots, b_{2p_j + 2}^j$ form a path, see \cref{fig:vertex_cover}. We connect $\PP{j}$ to $W$ by adding, for all $s \in [p_j]$, an edge between $a_{s}^j$ and $w_{s'}$, where $s' \in [n]$ so that $u_{s'} = u^j_s$. The key property of the triangle path $\PP{j}$ is that it costs more to cover $\PP{j}$ if no vertex in $N(\PP{j}) \subseteq W$ is inside the vertex cover. Since the budget constraint will be tight, this implies that a vertex cover has to take at least one vertex in each $N(\PP{j})$.

 \begin{figure}[h]
  \centering
  \tikzfig{pictures/vertexcover}
  \caption{The triangle path $\PP{j}$, where the $j$-th set consists of $u_1$, $u_3$, and $u_7$.}
  \label{fig:vertex_cover}
 \end{figure}

 \begin{lem}
 \label{thm:vc_triangle_path}
 Let $j \in [m]$ and $Y$ be a vertex cover of $G$, then $|Y \cap \PP{j}| \geq 2p_j$ and:
 \begin{enumerate}
   \item If $Y \cap N(\PP{j}) = \emptyset$, then $|Y \cap \PP{j}| \geq 2p_j + 1$.
   \item If $|Y \cap N(\PP{j})| \geq 1$, then there is a vertex cover $Y'$ with $Y \setminus \PP{j} = Y' \setminus \PP{j}$ and $|Y' \cap \PP{j}| \leq 2p_j$.
 \end{enumerate}
 \end{lem}

 \begin{proof}
  Let $Y$ be a vertex cover of $G$. Consider some $\PP{j}$ and notice that the triangles $\{a^j_{s}, b^j_{2s}, b^j_{2s + 1}\}$, $s \in [p_j]$, are vertex-disjoint and any vertex cover has to contain at least 2 vertices in each triangle. Hence, $|Y \cap \PP{j}| \geq 2p_j$ for all $j \in [m]$.

  Now, suppose that $Y \cap N(\PP{j}) = \emptyset$ for some $j \in [m]$. By assumption, the $p_j$ edges between $\PP{j}$ and $W$ are not covered by $Y \cap W$ and hence $Y$ must contain $\{a^j_{1} , a^j_{2}, \ldots, a^j_{p_j}\}$. Hence, $Y$ contains all $a$-vertices of $\PP{j}$ and after removing these from $\PP{j}$ a path on $2p_j + 2$ vertices remains. Therefore, $Y$ has to contain at least $p_j + 1$ vertices of this path. In total, $Y$ contains at least $2p_j + 1$ vertices of $\PP{j}$.

  Lastly, suppose that $Y$ is a vertex cover with $|Y \cap N(\PP{j})| \geq 1$ for some $j \in [m]$. Let $s^* \in [p_j]$ be the smallest integer such that the neighbor in $W$ of $a^j_{s^*}$ belongs to $Y$. We define $Y'_{P} = \{a^j_{s} : s \in [p_j] \setminus \{s^*\} \} \cup \{b^j_{2s} : s \in [s^*]\} \cup \{b^j_{2s + 1} : s \in [p_j] \setminus [s^* - 1]\}$ and claim that $Y'_P$ is a vertex cover of $G[\PP{j}]$. Notice that $Y'_P$ contains $2$ vertices in each triangle $\{a^j_{s}, b^j_{2s}, b^j_{2s + 1}\}$, $s \in [p_j]$, and the edges $\{b^j_{s}, b^j_{s+1}\}$ are covered by the $b^j$ with an even subscript if $s \leq 2s^*$ and otherwise by the $b^j$ with an odd subscript. Hence, $Y'_P$ is a vertex cover of $G[\PP{j}]$. We define $Y' = (Y \setminus \PP{j}) \cup Y'_P$. All edges between $\PP{j}$ and $W$ are covered by $Y' \cap \PP{j}$ except the edge incident to $a^j_{s^*}$ which is covered by $Y' \cap W$ by assumption. Therefore, $Y'$ is a vertex cover of $G$ with $Y \setminus \PP{j} = Y' \setminus \PP{j}$ and $|Y' \cap \PP{j}| = |Y'_P| = (p_j - 1) + s^* + (p_j + 1 - s^*) = 2p_j$.
 \end{proof}

 \begin{lem}
  \label{thm:vc_reduction_correct}
  Let $q \in \mathbb{N}$ and $(U, \mathcal{F})$ be a $q$-\textsc{Hitting Set}\xspace instance with $|U| = n$ and $|\mathcal{F}| = m$. There is a hitting set for $(U, \mathcal{F})$ of size at most $t$ if and only if $G = G(U, \mathcal{F})$ has a vertex cover of size at most $b = t + 2 \sum_{j \in [m]} p_j$.
 \end{lem}

 \begin{proof}
 Let $H$ be a hitting set of $(U, \mathcal{F})$ of size $|H| \leq t$. Let $Y_W = \{w_i \in W : u_i \in H\}$ and consider $Y = Y_W \cup \bigcup_{j = 1}^m \PP{j}$. The set $Y$ is certainly a vertex cover of $G$ and by applying the second part of  \cref{thm:vc_triangle_path} for every $j \in [m]$, which is possible since $H$ was a hitting set, we obtain a vertex cover $Y'$ with $Y' \cap W = Y_W$ and $|Y' \cap \PP{j}| \leq 2p_j$ for all $j \in [m]$. Hence, $Y'$ is a vertex cover of $G$ of size at most $t + 2 \sum_{j \in [m]} p_j$.

 For the other direction, let $Y$ be a vertex cover of $G$ of size at most $t + 2 \sum_{j \in [m]} p_j$. Due to \cref{thm:vc_triangle_path}, we have that $|Y \cap \PP{j}| \geq 2p_j$ for all $j \in [m]$. Define $J_Y = \{j \in [m] : |Y \cap \PP{j}| > 2p_j\}$ and $Y_W = Y \cap W$. The size constraint implies that $|J_Y| + |Y_W| \leq t$. If $J_Y = \emptyset$, then by the first part of \cref{thm:vc_triangle_path} we must have that $Y \cap N(\PP{j}) \neq \emptyset$ for all $j \in [m]$. By the construction of $G$ this means that $H = \{u_i \in U : w_i \in Y_W\}$ must be a hitting set for $(U, \mathcal{F})$ of size at most $t$.

 If $J_Y \neq \emptyset$, then take some $j \in J_Y$ and some $w_i \in N(\PP{j})$ and construct the vertex cover $Y' = Y \cup \{w_i\}$. By the second part of \cref{thm:vc_triangle_path}, there is a vertex cover $Y''$ with $Y'' \setminus \PP{j} = Y' \setminus \PP{j}$ and $|Y'' \cap \PP{j}| \leq 2p_j$. This implies that $|Y''| = |Y| + 1 + |Y'' \cap \PP{j}| - |Y \cap \PP{j}| \leq |Y| + 1 + 2p_j - (2p_j + 1) = |Y|$ and $J_{Y''} = J_Y \setminus \{j\}$. We replace $Y$ by $Y''$ and repeat this argument until $J_Y = \emptyset$ and then obtain the desired hitting set by the previous argument.
 \end{proof}

 \begin{lem}
  \label{thm:vc_param_bound}
  It holds that $\pw(\PP{j}) = \tw(\PP{j}) = 2$ for all $j \in [m]$.
 \end{lem}

  \begin{proof}
 We construct a path decomposition $\TT$ for $\PP{j}$ of width $2$. Let $\TT$ be a path on $2p_j + 1$ vertices $t_1, t_2, \ldots t_{2p_j + 1}$. For $s \in [p_j + 1]$, define the bag $\mathbb{B}_{t_{2s - 1}} = \{b_{2s-1}^j, b_{2s}^j\}$, and for $s \in [p_j]$ define bags $\mathbb{B}_{t_{2s}} = \{a_s^j, b_{2s}^j, b_{2s + 1}^j\}$. Using these bags, $\TT$ is a path decomposition of width $2$ for $\PP{j}$. Since $\PP{j}$ is neither a linear forest nor a forest, we have that $\pw(\PP{j}) \geq 2$ and $\tw(\PP{j}) \geq 2$.
 \end{proof}

 \begin{proof}[Proof of \cref{thm:vc_lb}]
  Suppose that \textsc{Vertex Cover} can be solved in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to pathwidth at most 2. We argue that we can then solve $q$-\textsc{Hitting Set}\xspace in time $\Oh^*((2 - \varepsilon)^n)$ for all $q$, violating SETH\xspace by \cref{thm:seth_hitting_set}.

  Fix an arbitrary integer $q \geq 1$ and a $q$-\textsc{Hitting Set}\xspace instance $(U, \mathcal{F})$ with $|U| = n$ and $|\mathcal{F}| = m$. From $(U, \mathcal{F})$ construct the graph $G = G(U, \mathcal{F}) = (V, E)$ as described above in polynomial time. Let $X = W$, then $G - X$ is the disjoint union of the $\PP{j}$, $j \in [m]$, and by \cref{thm:vc_param_bound} the pathwidth of $G - X$ is 2. So, $X$ is a modulator to pathwidth at most $2$ of size $|X| = |W| = n$. Running the \textsc{Vertex Cover} algorithm on $G$ with budget $b = t + 2 \sum_{j \in [m]} p_j$ and modulator $X$ solves $q$-\textsc{Hitting Set}\xspace by \cref{thm:vc_reduction_correct}. As the size of $G$ is polynomial in $|U| = n$ and $|\mathcal{F}| = m$, the resulting running time is $\Oh^*((2 - \varepsilon)^n)$ and hence SETH\xspace must be false.
 \end{proof}

\begin{cor}
 If \textsc{Vertex Cover} can be solved in time $\Oh^*((2 - \varepsilon)^{\td(G)})$ for some $\varepsilon > 0$, then SETH\xspace is false.
\end{cor}

\begin{proof}
  Follows from \cref{thm:vc_lb} and \cref{thm:mod_to_tw_implies_td}
\end{proof}

\subsection{Further Consequences}
\label{sec:further_consequences}

\begin{cor}
 \label{thm:mc_lb}
 If \textsc{Maximum Cut}\xspace can be solved in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to treewidth at most 2, then SETH\xspace is false.
\end{cor}

\begin{proof}
 We use a well-known reduction from \textsc{Vertex Cover}\xspace to \textsc{Maximum Cut}\xspace by Garey et al.~\cite{GareyJS76}. Let $G = (V, E)$ be a graph. We construct another graph $G' = (V', E')$ as follows: The vertex set is given by $V' = V \cup \{x\} \cup \{e_u, e_v : e = \{u,v\} \in E\}$. The vertex $x$ is adjacent to all $v \in V$ and for every edge $e = \{u, v\} \in E$, we add the five edges $\{x, e_u\}$, $\{x, e_v\}$, $\{e_u, e_v\}$, $\{e_u, u\}$, and $\{e_v, v\}$ to $E'$. Now, $G$ contains a vertex cover of size at most $|V(G)| - b$ if and only if $G'$ contains a cut of size at least $4|E(G)| + b$.

 Let $X$ be a modulator to treewidth at most 2 for $G$, i.e., $\tw(G - X) \leq 2$. We claim that $X' = X \cup \{x\}$ is a modulator to treewidth at most 2 for $G'$, i.e., $\tw(G' - X') \leq 2$. After removing $X'$ only edges of the form $\{e_u, e_v\}$, $\{e_u, u\}$, and $\{e_v, v\}$ remain. Notice that $G' - X'$ can be obtained from $G - X$ by subdividing each edge twice, i.e., replacing each edge by a path of length 3. It is well-known that subdividing edges does not affect the treewidth, hence we have that $\tw(G' - X') = \tw(G - X) \leq 2$.

 If we can solve \textsc{Maximum Cut}\xspace in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to treewidth at most 2, then we can also solve \textsc{Vertex Cover}\xspace in time $\Oh^*((2-\varepsilon)^{|X|})$ by using the discussed polynomial-time reduction and noting that any modulator to pathwidth at most 2 is also a modulator to treewidth at most 2. Hence, SETH\xspace must be false by \cref{thm:vc_lb}.
\end{proof}

\begin{cor}
 If \textsc{Maximum Cut}\xspace can be solved in time $\Oh^*((2 - \varepsilon)^{\td(G)})$ for some $\varepsilon > 0$, then SETH\xspace is false.
\end{cor}

\begin{proof}
 Follows from \cref{thm:mc_lb} and \cref{thm:mod_to_tw_implies_td}.
\end{proof}

\begin{cor}
 \label{thm:clique_del_lb}
  Let $r \geq 3$. If \textsc{$K_\ncols$-free Deletion}\xspace can be solved in time $\Oh^*((2 - \varepsilon)^{|X|})$ for some $\varepsilon > 0$, where $X$ is a modulator to treewidth at most $r - 1$, then SETH\xspace is false.
\end{cor}

\begin{proof}
 Let $G = (V, E)$ be a \textsc{Vertex Cover}\xspace instance. We construct $G' = (V', E')$ by using a classical trick and replacing each edge of $G$ by a clique on $r$ vertices which is just like the deletion edges for the \textsc{Deletion to $\ncols$-Colorable}\xspace lower bounds. It can be seen that $G$ has a vertex cover of size at most $b$ if and only if there is a set $Y \subseteq V'$, $|Y| \leq b$, such that $G' - Y$ is $K_r$-free.

 If $X$ is a modulator to treewidth at most 2 for $G$, i.e., $\tw(G - X) \leq 2$, then we claim that $X$ is also a modulator to treewidth at most $r$ for $G'$. Let $\TT$ be a tree decomposition of width 2 for $G - X$ with bags $\mathbb{B}_t$, $t \in V(\TT)$. We construct a tree decomposition $\TT'$ of width $r$ for $G' - X$ as follows. We start with the tree decomposition $\TT$ of $G - X$. For every edge $e \in E(G - X)$ there is a $t \in V(\TT)$ such that $e \subseteq \mathbb{B}_{t}$ and to $t$ we attach a degree-1 node $t^*$ and the bag of $t^*$ contains the clique that replaced edge $e$. Hence, every edge of $G' - X$ is captured in some bag of $\TT'$ and $\TT'$ is a tree decomposition of width $r - 1$.

 Since the construction of $G'$ can be performed in polynomial time and since the size of the modulator does not change, the result follows by \cref{thm:vc_lb}.
\end{proof}

\begin{cor}
 \label{thm:clique_del_td_lb}
 Let $r \geq 3$. If \textsc{$K_r$-free Deletion} can be solved in time $\Oh^*((2 - \varepsilon)^{\td(G)})$ for some $\varepsilon > 0$, then SETH\xspace is false.
\end{cor}

\begin{proof}
 Follows from \cref{thm:clique_del_lb} and \cref{thm:mod_to_tw_implies_td}.
\end{proof}

The lower bounds obtained for \textsc{Vertex Cover}\xspace, \textsc{Maximum Cut}\xspace, and \textsc{$K_r$-free Deletion} are tight in the sense that we have algorithms with matching running time by straightforward dynamic programming on tree decompositions.

redpajama_set_name: RedPajamaArXiv