Recall that for a node $t\in T$, we denote by $X_{t}$ the associated bag and
define $V_{t}$ to be the set of all vertices that have been introduced in the
subtree rooted at $t$ of $T$ (including $t$).

To goal of the algorithm is to compute, for each node $t$ of the nice tree
decomposition and each index $i\in\bm{[}\,0\,\bm{.\,.}\,n\,\bm{]}$, a language
$L\bm{[}\,t,i\,\bm{]}$ which contains all strings $x\in{\mathbb{A}}^{X_{t}}$
such that there exists a partial solution $S_{x}$ for the graph with portals
$(G\bm{[}\,V_{t}\,\bm{]},X_{t})$ with $|S_{x}\setminus X_{t}|=i$. Using
Section 2.1, one can immediately observe that, for all $t$ and $i$, the
language $L\bm{[}\,t,i\,\bm{]}$ is sparse. Recall that from the definition of
a partial solution, all vertices in $G\bm{[}\,V_{t}\setminus X_{t}\,\bm{]}$
must have the correct number of neighbors in $S_{x}$ whereas this might not be
the case for the vertices of $X_{t}$.

The algorithm now reads as follows. We traverse the tree decomposition in
post-order and depending on the type of the current node $t$, we apply one of
the following procedures.

Leaf Node.

For a leaf node $t$ of the tree decomposition, we have $X_{t}=\varnothing$.
Hence, we set $L\bm{[}\,t,0\,\bm{]}\coloneqq\\{\varepsilon\\}$ where
$\varepsilon$ denotes the empty vector. For all
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, we set
$L\bm{[}\,t,i\,\bm{]}\coloneqq\varnothing$.

Introduce Node.

Let $t$ be the introduce-node and $t^{\prime}$ its child. Furthermore, let $v$
be the introduced vertex. Each solution in $L[t^{\prime},i]$ provides two
solutions for $t$ depending on whether we select $v$ or not.

Before moving to the definition of the table entry, we first introduce some
notation. Let $y\in{\mathbb{A}}^{X_{t^{\prime}}}$ be a state-vector for the
child node $t^{\prime}$ and let $c\coloneqq|\\{u\in N(v)\mid
y\bm{[}\,u\,\bm{]}\in{\mathbb{S}}\\}$ be the number of neighbors of $v$ that
are selected according to string $y$. The $\rho$-extension of $y$ is defined
as the unique string $x$ such that

  * •

$x\bm{[}\,v\,\bm{]}\coloneqq\rho_{c\bmod{\mathrm{m}}}$ and

  * •

$x\bm{[}\,X_{t^{\prime}}\,\bm{]}\coloneqq y\bm{[}\,X_{t^{\prime}}\,\bm{]}$.

Similarly, we define the $\sigma$-extension of $y$ as the unique string $x$
such that

  * •

$x\bm{[}\,v\,\bm{]}\coloneqq\sigma_{c\bmod{\mathrm{m}}}$

  * •

$x\bm{[}\,X_{t^{\prime}}\setminus N(v)\,\bm{]}\coloneqq
y\bm{[}\,X_{t^{\prime}}\setminus N(v)\,\bm{]}$,

  * •

for all $u\in X_{t^{\prime}}\cap N(v)$ with $y\bm{[}\,u\,\bm{]}=\tau_{k}$, we
set $x\bm{[}\,u\,\bm{]}\coloneqq\tau_{k+1\bmod{\mathrm{m}}}$.

Then, we define the resulting language as

$L\bm{[}\,t,i\,\bm{]}\coloneqq\left(\\{x\mid x\text{ is the $\rho$-extension
of }y\in L\bm{[}\,t^{\prime},i\,\bm{]}\\}\cup\\{x\mid x\text{ is the
$\sigma$-extension of }y\in L\bm{[}\,t^{\prime},i\,\bm{]}\\}\right)$

for all $i\in\bm{[}\,0\,\bm{.\,.}\,n\,\bm{]}$.

Forget Node.

Let $t$ be a forget node with child $t^{\prime}$ and let $v$ be the vertex
that is forgotten. The language $L\bm{[}\,t,i\,\bm{]}$ should contain those
strings of languages of $t^{\prime}$ in which $v$ has a neighbor count that is
contained in $\sigma$ if $v$ is selected, and a neighbor count contained in
$\rho$ if $v$ is not selected. Furthermore, if we forget a selected vertex,
then we must take this into account with our second index $i$.

Hence, we set

$\displaystyle L\bm{[}\,t,0\,\bm{]}\coloneqq\leavevmode\nobreak\ $
$\displaystyle\\{x\bm{[}\,X_{t}\,\bm{]}\mid x\in
L\bm{[}\,t^{\prime},0\,\bm{]}\land x\bm{[}\,v\,\bm{]}=\rho_{c}\land
c\in\rho\\}$ (4) and, for all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, we set
$\displaystyle L\bm{[}\,t,i\,\bm{]}\coloneqq\leavevmode\nobreak\ $
$\displaystyle\\{x\bm{[}\,X_{t}\,\bm{]}\mid x\in
L\bm{[}\,t^{\prime},i\,\bm{]}\land x\bm{[}\,v\,\bm{]}=\rho_{c}\land
c\in\rho\\}$ $\displaystyle\cup\\{x\bm{[}\,X_{t}\,\bm{]}\mid x\in
L\bm{[}\,t^{\prime},i-1\,\bm{]}\land x\bm{[}\,v\,\bm{]}=\sigma_{c}\land
c\in\sigma\\}.$ (5)

Join Node.

Let $t$ be a join node with children $t_{1}$ and $t_{2}$.

We clearly want to use the previous algorithm to join languages efficiently.
However, when doing this naively with the languages from the child nodes, we
count the selected neighbors in the bag twice by simply summing up the number
of neighbors as the selected vertices are selected in _both_ partial
solutions. Thus, we define an auxiliary language, that can be computed
efficiently. For a language $L$, we define the auxiliary language $\hat{L}$ as

$\displaystyle\hat{L}\coloneqq\leavevmode\nobreak\ $
$\displaystyle\\{\hat{x}\mid x\in L\\}$ where, for each $v\in X_{t}$, we set
$\displaystyle\hat{x}\bm{[}\,v\,\bm{]}\coloneqq\leavevmode\nobreak\ $
$\displaystyle\left\\{\begin{array}[]{@{\;}c@{\quad}l@{}}\sigma_{\hat{c}}&\text{if
}x\bm{[}\,v\,\bm{]}=\sigma_{c}\text{, and }\hat{c}=c-|\\{w\in N(v)\cap
X_{t}\mid x\bm{[}\,w\,\bm{]}\in\mathbb{S}\\}|\bmod{\mathrm{m}},\\\
\rho_{\hat{c}}&\text{if }x\bm{[}\,v\,\bm{]}=\rho_{c}\text{, and
}\hat{c}=c-|\\{w\in N(v)\cap X_{t}\mid
x\bm{[}\,w\,\bm{]}\in\mathbb{S}\\}|\bmod{\mathrm{m}}.\end{array}\right.$

Now, we can use the procedure from Definition 4.15 to join the languages of
the two children efficiently and set

$L\bm{[}\,t,i\,\bm{]}\coloneqq\bigcup_{j\in\bm{[}\,0\,\bm{.\,.}\,i\,\bm{]}}\hat{L}\bm{[}\,t_{1},j\,\bm{]}\oplus
L\bm{[}\,t_{2},i-j\,\bm{]}$

Finally, a solution of size exactly $i$ exists if and only if, for the root
node $r$, the table entry $L\bm{[}\,r,i\,\bm{]}$ contains the empty string
$\varepsilon$ as the bag of the root node is empty.

######  Claim 6.

The algorithm is correct.

The correctness of the algorithm for the leaf nodes, introduce nodes, and
forget nodes follows directly from the above description of the algorithm.

For the join node it remains to show that the language $\hat{L}$ is also
sparse when $L\bm{[}\,t,i\,\bm{]}$ is a sparse language. For every $x\in
L\bm{[}\,t,i\,\bm{]}$, we have that there exists a compatible partial solution
$S_{x}$ for the graph with portals $(G\bm{[}\,V_{t}\,\bm{]},X_{t})$ with
$|S_{x}\setminus U|=i$. If we now consider the graph with portals
$G^{\prime}=(G\bm{[}\,V_{t}\,\bm{]}-E(X_{t},X_{t}),X_{t})$, then we can
observe that $S_{x}$ is a compatible partial solution for this graph that
witnesses the string $\hat{x}$. In other words, for every
$x\in\hat{L}\bm{[}\,t,i\,\bm{]}$, there is a compatible partial solution for
$G^{\prime}$ with $|S_{x}\setminus U|=i$ and thus,
$\hat{L}\bm{[}\,t,i\,\bm{]}$ is sparse by Section 2.1.

It remains to analyze the running time of the algorithm

######  Claim 7.

The running time of the algorithm is ${\mathrm{m}}^{\textup{{tw}}}\cdot
n^{\mathcal{O}(1)}$.

Regarding the runtime, it is easy to see that introduce nodes and forget nodes
can be computed in time ${\mathrm{m}}^{\textup{{tw}}}\cdot n^{\mathcal{O}(1)}$
because this bounds the size of the sparse languages of each tree node, and
processing each string of each language can be done in time polynomial in $n$.
Furthermore, there are exactly $n$ such languages, which only contributes to
the polynomial factor.

For join nodes, we first have to compute $\hat{L}$ in time $|L|\cdot
n^{\mathcal{O}(1)}={\mathrm{m}}^{\textup{{tw}}}\cdot n^{\mathcal{O}(1)}$ since
we must only iterate over $L$ once and processing each string is possible in
time polynomial in its length. Observe that, when we combine two sparse
languages in the join operation, by our definitions, the resulting language is
also sparse by Section 2.1. Therefore, computing the combination of the
languages takes time ${\mathrm{m}}^{\textup{{tw}}}\cdot n^{\mathcal{O}(1)}$ by
Definition 4.15. Thus, each node can be processed in time
${\mathrm{m}}^{\textup{{tw}}}\cdot n^{\mathcal{O}(1)}$.

For the root node and the leaf nodes it is easy to see that they can be
processed in constant time when first initializing each possible table entry
with the empty set. As the number of nodes of the tree decomposition is
polynomial in $n$, the dynamic programming algorithm runs in time
${\mathrm{m}}^{\textup{{tw}}}\cdot n^{\mathcal{O}(1)}$.

This concludes the proof of the algorithmic result for solving
$(\sigma,\rho)\mathchar 45\relax$DomSet from Section 1.

We conclude this section by introducing a generalization of the classical
$(\sigma,\rho)\mathchar 45\relax$DomSet problem where we provide a shift-
vector for every vertex.

######  Definition 4.22 ($(\sigma,\rho)\mathchar 45\relax$DomSet with Shift-
Vectors).

Fix two non-empty sets $\sigma$ and $\rho$ of non-negative integers. For a
graph $G$, and a vector $\pi\colon V(G)\to\bm{[}\,0\,\bm{.\,.}\,\lvert
V\rvert\,\bm{]}$, a set $S\subseteq V(G)$ is a $(\sigma,\rho)$-$\pi$-set for
$G$, if and only if (1) for all $v\in S$, we have $\lvert N(v)\cap
S\rvert+\pi(v)\in\sigma$, and (2), for all $v\in V(G)\setminus S$, we have
$\lvert N(v)\cap S\rvert+\pi(v)\in\rho$.

The problem $(\sigma,\rho)\mathchar 45\relax$DomSet with Shift-Vectors asks
for a given graph $G$ and a shift vector $\pi$ whether there is a
$(\sigma,\rho)$-$\pi$-set $S$ or not.

This covers the classical $(\sigma,\rho)\mathchar 45\relax$DomSet by setting
$\pi(v)=0$ for all vertices $v\in V(G)$.

When taking a closer look at our dynamic program, one can see that there are
only two places where we actually refer to the sets $\sigma$ and $\rho$. These
two positions are the definitions of the table entries for the forget nodes in
Equations 4 and 5. If we modify these definitions as follows and set

$\displaystyle L\bm{[}\,t,0\,\bm{]}\coloneqq\leavevmode\nobreak\ $
$\displaystyle\\{x\bm{[}\,X_{t}\,\bm{]}\mid x\in
L\bm{[}\,t^{\prime},0\,\bm{]}\land x\bm{[}\,v\,\bm{]}=\rho_{c}\land
c+\pi(v)\in\rho\\}$ and, for all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, we set
$\displaystyle L\bm{[}\,t,i\,\bm{]}\coloneqq\leavevmode\nobreak\ $
$\displaystyle\\{x\bm{[}\,X_{t}\,\bm{]}\mid x\in
L\bm{[}\,t^{\prime},i\,\bm{]}\land x\bm{[}\,v\,\bm{]}=\rho_{c}\land
c+\pi(v)\in\rho\\}$ $\displaystyle\cup\\{x\bm{[}\,X_{t}\,\bm{]}\mid x\in
L\bm{[}\,t^{\prime},i-1\,\bm{]}\land x\bm{[}\,v\,\bm{]}=\sigma_{c}\land
c+\pi(v)\in\sigma\\},$

then we directly get the following result by using the same proof as for
Section 1.

Let $\sigma,\rho\subseteq\mathbb{Z}_{\geq 0}$ be two periodic sets both with
period ${\mathrm{m}}\geq 2$. Then, in time
${\mathrm{m}}^{\textup{{tw}}}\cdot\lvert G\rvert^{\mathcal{O}(1)}$ we can
decide simultaneously for all $s$ if a given graph $G$ and a shift-vector
$\pi\colon V(G)\to\bm{[}\,0\,\bm{.\,.}\,{\mathrm{m}}-1\,\bm{]}$, whether there
is a $(\sigma,\rho)$-$\pi$-set of size $s$ when a tree decomposition of width
tw is given with the input.

We immediately get the following corollary for solving Lights Out! in the
general setting.

We can find in time $2^{\textup{{tw}}}\cdot\lvert G\rvert^{\mathcal{O}(1)}$ an
optimal solution for Lights Out! for an arbitrary starting position assuming
the input graph $G$ comes with a tree decomposition of width tw.

##  5 Lower Bound for the Problem with Relations

As explained earlier, the first step of the lower bound is to show the
hardness of $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ which is
the generalization of $(\sigma,\rho)\mathchar 45\relax$DomSet where we
additionally allow relations. See Definition 2.5 for the formal definition. In
a second step, which is presented in Section 6, we then remove the relations.
Concretely, in the following we focus on the proof of Definition 2.5.

*

We establish this lower bound by a reduction from the constraint satisfaction
problem $q$-CSP-$B$ to $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\text{Rel}}$. We first explain the high-level idea in the
following and then describe the formal construction of the graph in Section
5.1. We prove the correctness of the construction and analyze the pathwidth of
the graph in Section 5.2, before we finish the proof in Section 5.3.

##### High-level Idea.

The high-level idea behind the construction follows the ideas presented by
Curticapean and Marx in [CM16] which have later been extended to Generalized
Matching [MSS21, MSS22] and $(\sigma,\rho)\mathchar 45\relax$DomSet [FMI+23c].

In contrast to these known lower bounds, our hardness result is _not_ based on
a direct reduction from SAT, instead we use $q$-CSP-$B$ as a basis. This
problem was introduced by Lampis [Lam20] to serve as a general starting point
to rule out algorithms with running times $(B-\varepsilon)^{k}\cdot
n^{\mathcal{O}(1)}$ for an appropriate parameter $k$.

See 2.3

By reducing from $q$-CSP-$B$, most technicalities resulting from the change of
the basis in the running time to achieve improved lower bounds are hidden. As
an immediate consequence the correspondence between the vertex states and the
variable assignments becomes more transparent.

To prove the required lower bounds, our construction must overcome certain
obstacles and must fulfill certain properties. In the following we name the
four most important ones.

  1. 1.

The constructed graph must have _low pathwidth_ , that is, ideally the
pathwidth of the constructed graph is the number of variables.

  2. 2.

We need to _encode the assignments_ for the variables of the CSP instance by
establishing a correspondence between these values and the states of so-called
information vertices of the constructed graph.

  3. 3.

The assignment to the variables must be _consistent_ across all constraints,
that is, the information vertices corresponding to different clauses must have
the same state.

  4. 4.

We need to embed the _constraints_ of the $q$-CSP-$B$ instance by the
relations of the $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$
instance.

We outline the general concepts to address these points in the following.

##### Low Pathwidth.

Assume that we are given an instance of $q$-CSP-${\mathrm{m}}$ containing $n$
variables and $\ell$ constraints. The general structure of the graph of the
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ instance is a
$n\times\ell$ _grid_ , which provides reasonably low pathwidth, i.e, pathwidth
$n$. Concretely, the graph contains $n$ rows, one row for each variable, and
$\ell$ columns, one for each constraint.

##### Encoding the Assignment.

For each row-column pair of the grid, there is an _information vertex_ which
we connect to specific gadgets that we later refer to as _managers_. The
purpose of these information vertices is to encode the assignment to the
variables of the $q$-CSP-${\mathrm{m}}$ instance. More precisely, each
information vertex has a specific state in a $(\sigma,\rho)$-set, depending on
the number of selected neighbors and whether it is selected itself. Since each
information vertex can have at least ${\mathrm{m}}$ states when fixing its
selection status, we can directly associate a state of the information vertex
to a specific value from $1$ to ${\mathrm{m}}$ the variables can have.

##### Consistency of the Assignment.

For the correctness of the reduction, we need to ensure that the assignment
for the variables is encoded consistently across the construction. By the
above idea, each row of the construction corresponds to one variable of the
input instance. Moreover, every such row contains multiple information
vertices which are not directly connected to each other. The construction must
guarantee that each vertex of a certain row receives the same state and thus,
the CSP solution induced by a $(\sigma,\rho)$-set assigns exactly one value to
each variable. It turns out that, by using the right type of additional
relations, for each fixed variable, the consistency across the row can be
achieved.

##### Encoding the Constraints.

As a last step, we ensure that, for every $(\sigma,\rho)$-set, the respective
states of the information vertices correspond to a satisfying assignment to
the CSP instance. This is easily achieved by introducing a new relation for
each constraint of the CSP instance and then adding it to specific vertices of
the construction. Combined with the previous ideas, the constraints of the CSP
instance are in direct correspondence to relations of the
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ instance.

###  5.1 Construction of the Graph

Since our lower bound construction covers an infinite class of problems, we
construct the graph using several gadgets. This allows us to reuse some
intermediate results from [FMI+23c] which have been used to establish the
lower bound for $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ when
$\sigma$ and $\rho$ are finite.

We first focus on the definition of the managers. These gadgets allow us to
associate the values of the variables of the CSP instance with the states of
the information vertices.

######  Definition 5.1 ($A$-manager [D]efinition 4.7).

focke_tight_2023_lb] Consider two sets $\sigma$ and $\rho$ that are both
finite. For a set $A\subseteq{\mathbb{A}}$, an _$A$ -manager_ is an infinite
family $((G_{\ell},U_{\ell}))_{\ell\geq 1}$ of pairs $(G_{\ell},U_{\ell})$
such that

  * •

$G_{\ell}$ is a graph with relations and

  * •

$U_{\ell}=\\{u_{1},\dots,u_{\ell}\\}\subseteq V(G_{\ell})$ is a set of $\ell$
distinguished vertices.

Moreover, there is a non-negative integer $b$ (that depends only on
$\max\sigma$ and $\max\rho$) such that the following holds for every $\ell\geq
1$:

  * •

The vertices from $V(G_{\ell})\setminus U_{\ell}$ can be partitioned into
$2\ell$ vertex-disjoint subgraphs $B_{1},\dots,B_{\ell}$ and
$\overline{B}_{1},\dots,\overline{B}_{\ell}$ (called _blocks_), such that

    * –

$|B_{i}|\leq b$ and $|\overline{B}_{i}|\leq b$ for all
$i\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$,

    * –

$N(u_{i})\subseteq B_{i}\cup\overline{B}_{i}$ for all
$i\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$,

    * –

there are edges only between the following pairs of blocks: $B_{i}$ and
$B_{i+1}$, $\overline{B}_{i}$ and $\overline{B}_{i+1}$, for each
$i\in\bm{[}\,1\,\bm{.\,.}\,\ell-1\,\bm{]}$, and $B_{\ell}$ and
$\overline{B}_{\ell}$, and

    * –

for each relation $R$ of $G_{\ell}$, there is some
$i\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$ such that either
$\operatorname{\mathsf{scp}}(R)\subseteq N\bm{[}\,B_{i}\,\bm{]}$ or
$\operatorname{\mathsf{scp}}(R)\subseteq
N\bm{[}\,\overline{B}_{i}\,\bm{]}$.666Note that this last condition about the
arity is not part of the original definition. However, in order to be able to
replace these relations, we need a guarantee on the arity of these relations.
Even though not mentioned explicitly, this condition is satisfied by all the
constructions in [FMI+23c].

  * •

Each $x\in A^{\ell}\subseteq{\mathbb{A}}^{\ell}$ is _managed_ in the sense
that there is a unique $(\sigma,\rho)$-set $S_{x}$ of $G_{\ell}$ such that for
all $i\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$:

    * –

If $x\bm{[}\,i\,\bm{]}=\sigma_{s}$, then $u_{i}\in S_{x}$. Moreover, $u_{i}$
has exactly $s$ neighbors in $B_{i}\cap S_{x}$ and exactly $\max\sigma-s$
neighbors in $\overline{B}_{i}\cap S_{x}$.

    * –

If $x\bm{[}\,i\,\bm{]}=\rho_{r}$, then $u_{i}\notin S_{x}$. Moreover, $u_{i}$
has exactly $r$ neighbors in $B_{i}\cap S_{x}$ and exactly $\max\rho-r$
neighbors in $\overline{B}_{i}\cap S_{x}$.

We refer to $G_{\ell}$ as the $A$-manager of rank $\ell$.

For certain cases, especially when $\sigma$ and $\rho$ are finite, the
existence of such managers is already known [FMI+23c].

[Implication of [FMI+23c, Lemma 6.1]] For non-empty finite sets $\sigma$ and
$\rho$, there is an $R$-manager with $R=\\{\rho_{i}\mid
i\in\bm{[}\,0\,\bm{.\,.}\,\max\rho\,\bm{]}\\}$.

Although these managers require finite sets, we can use them in a black-box
fashion for our construction even when dealing with periodic sets. Hence, we
simply use a finite subset of $\rho$ to obtain the managers. We formalize this
by the notion of a _cut set_ , which is a natural restriction of a periodic
set to a finite subset of it. We then extend this to the _cut states_.

######  Definition 5.2 (Cut Sets and States).

For a periodic set $\tau$ with period ${\mathrm{m}}$, we set

$\textsf{{cut}}(\tau)\coloneqq\\{\min(\tau),\min(\tau)+{\mathrm{m}}\\}\quad\text{and}\quad{\mathbb{R}}_{\textsf{{cut}}}\coloneqq\\{\rho_{i}\mid
i\in\bm{[}\,0\,\bm{.\,.}\,\max(\textsf{{cut}}(\rho))\,\bm{]}\\}.$

For example, consider the periodic set $\tau=\\{2,5,8,\dots\\}$ with period
three. With the above definition we get $\textsf{{cut}}(\tau)=\\{2,5\\}$.
Clearly, $\textsf{{cut}}(\tau)$ is finite for any periodic set $\tau$.

Before we move to the construction of the graph, we introduce the inverse of a
number. This definition is inspired by the definition of an inverse of a state
from [FMI+23c, Definition 3.10].

######  Definition 5.3 (Inverse of a Number).

Let $\sigma$ and $\rho$ be two periodic sets with the same period
${\mathrm{m}}\geq 2$.

For every number $n\in\mathbb{Z}_{\geq 0}$, the _inverse of $n$ relative to
$\rho$_ is defined as
${\operatorname{\mathsf{inv}}^{\rho}({n})}\coloneqq(\min\rho-n)\bmod{\mathrm{m}}$.

We extend this in the natural way to $\sigma$ and denote the inverse of $n$
relative to $\sigma$ by ${\operatorname{\mathsf{inv}}^{\sigma}({n})}$.

Observe that for every $n\in\bm{[}\,0\,\bm{.\,.}\,{\mathrm{m}}-1\,\bm{]}$, we
have

${\operatorname{\mathsf{inv}}^{\rho}({{\operatorname{\mathsf{inv}}^{\rho}({n})}})}=n\quad\text{and}\quad
n+{\operatorname{\mathsf{inv}}^{\rho}({n})}\in\rho.$

##### Construction of the Graph.

Consider a $q$-CSP-${\mathrm{m}}$ instance $I=(X,{\mathcal{C}})$ with $n$
variables $X=\\{x_{1},\dots,x_{n}\\}$ and $\ell$ constraints
${\mathcal{C}}=\\{C_{1},\dots,C_{\ell}\\}$. We construct an equivalent
instance $G_{I}$ of $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$
with low pathwidth.

We first require a suitable manager. For this purpose, we use Definition 5.1
with the sets $\textsf{{cut}}(\sigma)$ and $\textsf{{cut}}(\rho)$ to construct
an ${\mathbb{R}}_{\textsf{{cut}}}$-manager (as an instance of
$(\textsf{{cut}}(\sigma),\textsf{{cut}}(\rho))\mathchar
45\relax$DomSet${}^{\text{Rel}}$). Note that ${\mathbb{R}}_{\textsf{{cut}}}$
might contain states that are indistinguishable from other states, and in
particular, ${\mathbb{R}}\subseteq{\mathbb{R}}_{\textsf{{cut}}}$.

Since the constructed graph $G_{I}$ has a grid-like structure, we often refer
to objects by their row and column. We use the convention that the row is
written as a subscript index while the columns are denoted by superscript
indices.

Now we have everything ready to finally define the $G_{I}$ as follows:

  * •

For all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and all
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$, the graph $G_{I}$ contains a vertex
$w^{j}_{i}$, which we refer to as _information vertex_.

  * •

For all $j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$, there is a copy $M^{j}$ of
the ${\mathbb{R}}_{\textsf{{cut}}}$-manager of rank $n$ with $\\{w^{j}_{i}\mid
i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}\\}$ as the distinguished vertices.

We denote by $B^{j}_{i}$ and $\overline{B}^{j}_{i}$ the vertices of the
corresponding blocks of $M^{j}$. Moreover, we denote by $N_{B}(w^{j}_{i})$ the
neighborhood of $w^{j}_{i}$ in $B^{j}_{i}$, and denote by
$N_{\overline{B}}(w^{j}_{i})$ the neighborhood of $w^{j}_{i}$ in
$\overline{B}^{j}_{i}$.

  * •

For all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and all
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell-1\,\bm{]}$, we create a _consistency relation_
$\mathtt{R}^{j}_{i}$ with scope $\overline{B}^{j}_{i}\cup
B^{j+1}_{i}\cup\\{w^{j}_{i},w^{j+1}_{i}\\}$ which is defined later.

  * •

For all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, we create a consistency
relation $\mathtt{R}^{0}_{i}$ with scope $B^{1}_{i}\cup\\{w^{1}_{i}\\}$ which
is defined later.

  * •

For all $j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$, we create a _constraint
relation_ $\mathtt{C}^{j}$ with scope $\\{w^{j}_{i}\mid
x_{i}\in\operatorname{\mathsf{scp}}(C_{j})\\}\cup\bigcup_{x_{i}\in\operatorname{\mathsf{scp}}(C_{j})}B^{j}_{i}$
which is defined later.

As a last step of the construction we define the consistency relations
$\mathtt{R}^{j}_{i}$ and the constraint relations $\mathtt{C}^{j}$. For this
we first introduce some notation.

Given a selection $S$ of vertices from $G_{I}$, we define, for all
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and all
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$, two numbers $b^{j}_{i}$ and
$\overline{b}^{j}_{i}$. We denote by $b^{j}_{i}\coloneqq\lvert S\cap
N_{B}(w^{j}_{i})\rvert$ the number of selected neighbors of $w^{j}_{i}$ in the
block $B^{j}_{i}$, and denote by $\overline{b}^{j}_{i}\coloneqq\lvert S\cap
N_{\overline{B}}(w^{j}_{i})\rvert$ the number of selected neighbors of
$w^{j}_{i}$ in the block $\overline{B}^{j}_{i}$.

It remains to elaborate on the relations, whose definition we postponed so
far. We start with the _consistency relations_. Let $S$ be a subset of the
vertices of $G_{I}$. For all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell-1\,\bm{]}$, we denote by
$S^{j}_{i}=S\cap\operatorname{\mathsf{scp}}{(\mathtt{R}^{j}_{i})}$ the
selected vertices from the scope of $\mathtt{R}^{j}_{i}$. Relation
$\mathtt{R}^{j}_{i}$ accepts the set $S^{j}_{i}$ if and only if

  * •

$w_{i}^{j}$ and $w_{i}^{j+1}$ are both unselected,

  * •

$b^{j+1}_{i}\in\bm{[}\,0\,\bm{.\,.}\,{\mathrm{m}}-1\,\bm{]}$, and

  * •

$b^{j+1}_{i}={\operatorname{\mathsf{inv}}^{\rho}({\overline{b}^{j}_{i}})}$.

Similarly, for each $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, the set
$S^{0}_{i}=S\cap\operatorname{\mathsf{scp}}{(\mathtt{R}^{0}_{i})}$ is accepted
by $\mathtt{R}^{0}_{i}$ if and only if $w^{1}_{i}$ is unselected and
$b^{1}_{i}\in\bm{[}\,0\,\bm{.\,.}\,{\mathrm{m}}-1\,\bm{]}$.

Finally, we define the _constraint relations_ that realize the constraints of
the $q$-CSP-${\mathrm{m}}$ instance. For each
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$, denote by
$\operatorname{\mathsf{scp}}(C_{j})=(x_{\lambda_{1}},\dots,x_{\lambda_{q}})$
the variables appearing in this constraint. Then, the set
$S\cap\operatorname{\mathsf{scp}}{(\mathtt{C}^{j})}$ is accepted by
$\mathtt{C}^{j}$ if and only if

$(b^{j}_{\lambda_{1}}+1,\dots,b^{j}_{\lambda_{q}}+1)\in\operatorname{\mathsf{acc}}(C_{j}).$

That is, the states of the information vertices corresponding to the variables
of the constraint $C_{j}$ must represent a satisfying assignment of $C_{j}$.
Note that the variables takes values from
$\bm{[}\,1\,\bm{.\,.}\,{\mathrm{m}}\,\bm{]}$ while the states $b_{i}^{j}$ take
values from $\bm{[}\,0\,\bm{.\,.}\,{\mathrm{m}}-1\,\bm{]}$.

This concludes the construction of the instance $G_{I}$.

###  5.2 Properties of the Constructed Graph

In the following part we first prove the correctness of the reduction and then
provide the formal bound on the pathwidth.

We show the two directions of the correctness independently.

######  Lemma 5.4.

If $I$ is a satisfiable instance of $q$-CSP-${\mathrm{m}}$, then the
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ instance $G_{I}$ has
a solution.

######  Proof 5.5.

Recall that $I=(X,{\mathcal{C}})$ is a $q$-CSP-${\mathrm{m}}$ instance with
$n$ variables $X=\\{x_{1},\dots,x_{n}\\}$ and $\ell$ constraints
${\mathcal{C}}=\\{C_{1},\dots,C_{\ell}\\}$. Consider an assignment $\pi\colon
X\to\bm{[}\,1\,\bm{.\,.}\,{\mathrm{m}}\,\bm{]}$ that satisfies all constraints
of $I$.

For each $j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$, we select the vertices of
the ${\mathbb{R}}_{\textsf{{cut}}}$-manager $M^{j}$ such that
$b^{j}_{i}=\pi(x_{i})-1$ for all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$. We
select no other vertices. Such a solution exists by the definition of a
manager in Definition 5.1 as
$\rho_{\pi(x_{i})-1}\in{\mathbb{R}}_{\textsf{{cut}}}$.

Let $S$ denote this set of selected vertices. Because of the definition of
managers, this set $S$ is a solution for $G_{I}$ when considering it as a
$(\textsf{{cut}}(\sigma),\textsf{{cut}}(\rho))\mathchar 45\relax$DomSet
instance where we ignore all relations. Since $\textsf{{cut}}(\sigma)$ and
$\textsf{{cut}}(\rho)$ are subsets of $\sigma$ and $\rho$, the set $S$ is
actually a solution for the $(\sigma,\rho)\mathchar 45\relax$DomSet instance.

Hence, all that remains is to argue that $S$ also satisfies all relations of
$G_{I}$. Per construction, all information vertices are unselected. As the
proof follows directly for $\mathtt{R}^{0}_{i}$ where
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, we consider a relation
$\mathtt{R}^{j}_{i}$ for an arbitrary $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$
and $j\in\bm{[}\,1\,\bm{.\,.}\,\ell-1\,\bm{]}$. We now prove that
$b^{j+1}_{i}={\operatorname{\mathsf{inv}}^{\rho}({\overline{b}^{j}_{i}})}$.

It directly follows from the definition of the managers and the choice of $S$
(which implies $b^{j}_{i}=b^{j+1}_{i}$) that
$\overline{b}^{j}_{i}=(\min\rho+{\mathrm{m}})-b^{j}_{i}=\min\rho+{\mathrm{m}}-b^{j+1}_{i}$.
We furthermore know that ${\mathbb{R}}$ only contains states where the number
of neighbors is at most ${\mathrm{m}}-1$. Since $b^{j+1}_{i}$ corresponds to a
state in ${\mathbb{R}}$ by our choice of $S$, we obtain
$b^{j+1}_{i}\leq{\mathrm{m}}-1$ which in turn implies that
$b^{j+1}_{i}\mod{\mathrm{m}}=b^{j+1}_{i}$. Overall, we have

${\operatorname{\mathsf{inv}}^{\rho}({\overline{b}^{j}_{i}})}=\min\rho-(\min\rho+{\mathrm{m}}-b^{j+1}_{i})\mod{\mathrm{m}}=b^{j+1}_{i}\mod{\mathrm{m}}=b^{j+1}_{i}.$

Finally, we need to confirm that the constraint relations $\mathtt{C}^{j}$ are
satisfied for all $j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$. This directly
follows from our selection of the vertices such that
$b^{j}_{i}=\mathsf{enc}(\pi(x_{i}))-1$ for all
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$. Hence, all relations accept because
$\pi$ is an assignment satisfying all constraints of $I$.

As a next step we prove the reverse direction of the correctness.

######  Lemma 5.6.

If the $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ instance
$G_{I}$ has a solution, then the $q$-CSP-${\mathrm{m}}$ instance $I$ is
satisfiable.

######  Proof 5.7.

Let $S$ be a $(\sigma,\rho)$-set for $G_{I}$ that also satisfies all
relations. We start by proving that

$b^{j}_{i}=b^{j+1}_{i}\quad\text{ for all
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell-1\,\bm{]}$}.$ (6)

For this fix an arbitrary pair $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ and
$j\in\bm{[}\,1\,\bm{.\,.}\,\ell-1\,\bm{]}$. The relation $\mathtt{R}_{i}^{j}$
ensures that
$b^{j+1}_{i}={\operatorname{\mathsf{inv}}^{\rho}({\overline{b}^{j}_{i}})}$.
Moreover, the relation guarantees that $w^{j+1}_{i}$ and $w^{j}_{i}$ are not
selected.

The definition of $\mathtt{R}^{j}_{i}$ implies that
$b^{j+1}_{i}={\operatorname{\mathsf{inv}}^{\rho}({\overline{b}^{j}_{i}})}=(\min\rho-\overline{b}^{j}_{i})\bmod{\mathrm{m}}$
and moreover, since $w^{j}_{i}$ has a neighbor count in $\rho$, we must also
have $b^{j}_{i}+\overline{b}^{j}_{i}\equiv_{{\mathrm{m}}}\min\rho$. By
rearranging the terms we get
$\overline{b}^{j}_{i}\equiv_{{\mathrm{m}}}\min\rho-b^{j}_{i}$, and when
combining with the previous result, it follows that
$b^{j+1}_{i}\equiv_{{\mathrm{m}}}\min\rho-(\min\rho-b^{j}_{i})\equiv_{{\mathrm{m}}}b^{j}_{i}$.
Since $S$ is a solution, for all $k\in\bm{[}\,0\,\bm{.\,.}\,\ell-1\,\bm{]}$,
the relation $\mathtt{R}_{i}^{k}$ ensures that
$b_{i}^{k+1}\in\bm{[}\,0\,\bm{.\,.}\,{\mathrm{m}}-1\,\bm{]}$. Using
$b^{j}_{i}\leq{{\mathrm{m}}-1}$ and $b^{j+1}_{i}\leq{{\mathrm{m}}-1}$, we
conclude that $b^{j}_{i}=b^{j+1}_{i}$.

We can now define a satisfying assignment for $I$. Because all information
vertices are unselected, the states of all information vertices for a single
variable are the same. We define the variable assignment $\pi\colon
X\to\bm{[}\,1\,\bm{.\,.}\,{\mathrm{m}}\,\bm{]}$ by setting
$\pi(x_{i})\coloneqq b^{1}_{i}+1$ for all
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$.

To see that $\pi$ is an assignment satisfying all constraints of $I$, consider
an arbitrary constraint $C_{j}$ of $I$. The relation $\mathtt{C}^{j}$ then
ensures that
$(b^{j}_{\lambda_{1}},\dots,b^{j}_{\lambda_{q}})\in\operatorname{\mathsf{acc}}(C_{j})$,
where
$\operatorname{\mathsf{scp}}(C_{j})=(x_{\lambda_{1}},\dots,x_{\lambda_{q}})$
are the variables of the constraint. Hence, the definition of $\pi$ implies
that $C_{j}$ is satisfied.

This concludes the proof of the correctness of the reduction. It remains to
analyze the size and the pathwidth such that the lower bound of
$q$-CSP-${\mathrm{m}}$ transfers to $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\text{Rel}}$. However, for this we first have to formally
introduce the notion of pathwidth of a graph with relations.

######  Definition 5.8 (Width Measures for Graphs with Relations [FMI+23c,
Definition 4.4]).

Let $G=(V,E,{\mathcal{C}})$ be a graph with relations. Let $\hat{G}$ be the
graph we obtain from $(V,E)$ when, for all $C\in{\mathcal{C}}$, we
additionally introduce a complete set of edges on the scope
$\operatorname{\mathsf{scp}}(C)$. The _treewidth of a graph with relations_
$G$, is the treewidth of the graph $\hat{G}$. Analogously, we define tree
decompositions, path decompositions, and pathwidth of $G$ as the corresponding
concepts in the graph $\hat{G}$.

Now we can prove that even after this transformation, the pathwidth of the
constructed graph is not too large.

######  Lemma 5.9.

There is a function $f$ depending only on $\sigma$ and $\rho$ such that
$G_{I}$ has size at most $n\cdot\ell\cdot f(q)$, pathwidth at most $n+f(q)$,
and arity at most $f(q)$.

######  Proof 5.10.

We first elaborate on the number of vertices of $G_{I}$. Graph $G_{I}$
contains $\ell$ copies of an ${\mathbb{R}}_{\textsf{{cut}}}$-manager of rank
$n$. By Definition 5.1, the size of each block of an
${\mathbb{R}}_{\textsf{{cut}}}$-manager is at most $b$, for some constant $b$
depending only on $\textsf{{cut}}(\sigma)$ and $\textsf{{cut}}(\rho)$. Since
$\textsf{{cut}}(\sigma)$ and $\textsf{{cut}}(\rho)$ only depend on $\sigma$
and $\rho$, it is evident that $b$ only depends on $\sigma$ and $\rho$. Since
each manager consists of exactly $2n$ blocks as well as $n$ information
vertices, we see that $G_{I}$ consists of $\ell\cdot(2n\cdot b+n)$ vertices.
Observe that

$\displaystyle\ell\cdot(2n\cdot b+n)=n\cdot\ell\cdot c_{\textsf{v}}$

for an appropriately chosen constant $c_{\textsf{v}}$ only depending on
$\sigma$ and $\rho$.

For the arity of the relations, we notice that each consistency relations has
arity at most $2\cdot(b+1)$, each constraint relation has arity at most
$q\cdot(b+1)$, and the arity of each relation stemming from a manager is in
$\mathcal{O}(b)$. Hence, the maximum arity of each relation is bounded by
$\mathcal{O}(q\cdot b).$

Recall from Definition 2.4, that the size of a graph with relations is defined
as the number of vertices plus the size of each relation (which might be
exponential in the arity). The graph $G_{I}$ contains exactly $n\cdot\ell$
consistency relations and $\ell$ constraint relations plus the relations of
the managers each of which has at most $\mathcal{O}(n\cdot 2^{b})$ relations
of arity at most $b$.

Combining our knowledge of the number of vertices, with the maximal arity of
any relation, and the number of relations, we can conclude that the size of
$G_{I}$ is bounded by

$\displaystyle n\cdot\ell\cdot c_{\textsf{v}}+n\cdot\ell\cdot
2^{\mathcal{O}(q\cdot b)}=n\cdot\ell\cdot f_{1}(q,\sigma,\rho),$

for an appropriately chosen function $f_{1}(q,\sigma,\rho)$.

It remains to bound the pathwidth of $G_{I}$. We do this by the standard
approach of providing a node search-strategy (see [CFK+15, Section 7.5] for
example). From Definition 5.8, we know that the pathwidth of a graph $G$ with
relations is defined as the pathwidth of the graph we obtain when making the
vertices in the scope of each relation a clique. Let $\hat{G}_{I}$ be the
graph obtain from $G_{I}$ by this modification (while keeping all indexed
vertices/sets the same).

The graph is cleaned in $\ell+1$ stages, where each stage consists of $n$
rounds. Intuitively, each stage is responsible for cleaning the left side of
one column of the construction, and each round for cleaning a block of the
column.

For each round, we list the vertices on which searchers are placed. This makes
it clear that one can go from one stage to the next without recontaminating
already cleaned parts and without the use of additional searchers. For
notational convenience, we define

  * •

$w^{j}_{i}$ as a dummy vertex that is not part of the graph $G_{I}$ whenever
$i\not\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ or
$j\not\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$,

  * •

$B^{j}_{i}$ and $\overline{B}^{j}_{i}$ to be the empty set whenever
$i\not\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ or
$j\not\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$,

  * •

$\operatorname{\mathsf{scp}}(\mathtt{C}^{j})$ to be the empty set when
$j\not\in\bm{[}\,1\,\bm{.\,.}\,\ell\,\bm{]}$.

Let ${\mathcal{S}}^{j}_{i}$ denote the set of vertices on which searchers are
placed in round $i$ of stage $j$. We define this set as

$\displaystyle{\mathcal{S}}^{j}_{i}=\ $ $\displaystyle\\{w^{j-1}_{x}\mid i\leq
x\leq n\\}\cup\\{w^{j}_{x}\mid 1\leq x\leq i+1\\}$
$\displaystyle\cup\overline{B}^{j-1}_{i}\cup
B^{j}_{i}\cup\overline{B}^{j-1}_{i+1}\cup B^{j}_{i+1}$
$\displaystyle\cup\overline{B}^{j-1}_{n}\cup B^{j-1}_{n}$
$\displaystyle\cup\operatorname{\mathsf{scp}}{(\mathtt{C}^{j})}.$

First observe that every vertex of the graph is contained in some set
${\mathcal{S}}_{i}^{j}$. It remains to argue that the graph does not get
recontaminated. Consider the intersection of the vertices from two consecutive
rounds of the same stage, that is,

$\displaystyle{\mathcal{S}}_{i}^{j}\cap{\mathcal{S}}_{i+1}^{j}=$
$\displaystyle\\{w^{j-1}_{x}\mid i+1\leq x\leq n\\}\cup\\{w^{j}_{x}\mid 1\leq
x\leq i+1\\}\cup\overline{B}^{j-1}_{i+1}\cup
B^{j}_{i+1}\cup\overline{B}^{j-1}_{n}\cup
B^{j-1}_{n}\cup\operatorname{\mathsf{scp}}{(\mathtt{C}^{j})}.$

As these vertices form a separator of the graph, the cleaned part of the graph
does not get recontaminated.

When moving from one stage to the next one, we can use the same technique by
observing that

$\displaystyle{\mathcal{S}}_{n}^{j}\cap{\mathcal{S}}_{1}^{j+1}=\\{w^{j}_{x}\mid
1\leq x\leq n\\}\cup B^{j}_{n}$

separates the graph. We conclude that the node search number of $\hat{G}_{I}$
is at most

$\displaystyle\max_{\begin{subarray}{c}i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]},\\\
j\in\bm{[}\,1\,\bm{.\,.}\,\ell+1\,\bm{]}\end{subarray}}\Big{|}{\mathcal{S}}^{j}_{i}\Big{|}=n+2+6b+q\cdot(b+1),$

which means that the pathwidth of $\hat{G}_{I}$ and thus, of $G_{I}$ is at
most

$\displaystyle n+f_{2}(q,\sigma,\rho),$

for an appropriately chosen function $f_{2}(q,\sigma,\rho)$. This concludes
the proof by choosing the function $f$ from the statement as the maximum of
$f_{1}$ and $f_{2}$.

###  5.3 Combining the Results

As a last ingredient to our proof of Definition 2.5, we need the SETH-based
lower bound for $q$-CSP-${\mathrm{m}}$ from Definition 2.3.

See 2.3

Finally, we are ready to conclude the proof of the lower bound for
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ from Definition 2.5.

######  Proof 5.11.

We assume for contradiction’s sake, that, for some $\varepsilon>0$, there
exists an algorithm that can solve $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\text{Rel}}$ in time
$({\mathrm{m}}-\varepsilon)^{\textup{{pw}}}\cdot\lvert
G\rvert^{\mathcal{O}(1)}$ when the input contains a graph $G$ and a path
decomposition of $G$ of width pw.

Let $q$ be the arity from Definition 2.3 such that there is no algorithm that
can solve $q$-CSP-${\mathrm{m}}$ in time
$({\mathrm{m}}-\varepsilon)^{n}\cdot(n+\ell)^{\mathcal{O}(1)}$ for an instance
with $n$ variables and $\ell$ constraints.

Given an arbitrary $q$-CSP-${\mathrm{m}}$ instance $I$ as input, let $G_{I}$
denote the corresponding $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\text{Rel}}$ instance from Section 5.1 together with its
provided path decomposition. Then, we run the hypothetical algorithm for
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ on this instance and
return the output as the output of the $q$-CSP-${\mathrm{m}}$ instance.

Since, by Lemmas 5.4 and 5.6, the instance $G_{I}$ has a solution if and only
if $I$ is satisfiable, this algorithm correctly decides if the
$q$-CSP-${\mathrm{m}}$ instance $I$ is satisfiable.

It remains to analyze the running time of the algorithm. The construction of
$G_{I}$ (which bounds the size) takes time polynomial in the size of $I$ (and
thus, also in $G_{I}$). By Lemma 5.9, the width of the given path
decomposition is $n+f(q)$. Hence, the final algorithm runs in time

$({\mathrm{m}}-\varepsilon)^{n+f(q)}\cdot(n+\ell)^{\mathcal{O}(1)}=({\mathrm{m}}-\varepsilon)^{n}\cdot(n+\ell)^{\mathcal{O}(1)}$

since $q$ is a constant that only depends on $\sigma$ and $\rho$, which are
fixed sets and thus, not part of the input. Therefore, this directly
contradicts SETH by Definition 2.3 and concludes the proof.

##  6 Realizing Relations

Section 5 covers the proof of the conditional lower bound for
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ based on a reduction
from $q$-CSP-${\mathrm{m}}$, see Definition 2.5 for the precise statement.
From a higher level perspective, this reduction just considers how the values
for the variables are chosen and encodes this choice by a graph problem; the
constraints are hardly changed. More concretely, the constraints of the CSP
instance are not (yet) encoded by graph gadgets, but the reduction just
transformed them into relations of the resulting $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\text{Rel}}$ instance. Therefore, our next step is to
remove these relations or rather replace them by appropriate gadgets. Recall
that the reduction from Definition 2.5 also introduces relations that do not
correspond to constraints of the CSP instance due to technical reasons. In the
following we design a reduction which replaces all relations that appear in
the given $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ instance by
suitable gadgets.

Formally, this section is dedicated entirely to the proof of Definition 2.6.

*

Similar to the known lower bound for general classes of problems (especially
the bound for $(\sigma,\rho)\mathchar 45\relax$DomSet when $\sigma$ and $\rho$
are finite or simple cofinite from [FMI+23c, Section 8] but also the
constructions in [CM16, MSS21, MSS22]), we divide the reduction into smaller
steps. As a first step, we replace the general relations, which might be very
complex, by relations that are simple and easy to define. We mainly base our
construction on the existence of $\mathtt{HW}_{=1}$ relations and variants
there of which we formally introduce as follows.

######  Definition 6.1 (Relations).

Consider an integer $k\geq 1$ and an arbitrary non-empty set $\tau$ of non-
negative integers. We define $\mathtt{HW}_{\in\tau}^{(k)}$ as the relation of
arity $k$ that only accepts exactly $t$ selected vertices in the scope if and
only if $t\in\tau$. Otherwise, the relation does not accept.

To simplify notation, we write $\mathtt{HW}_{=1}^{(k)}$ for the
$\mathtt{HW}_{\in\\{1\\}}^{(k)}$. Moreover, we denote by
$\mathtt{HW}_{\in\tau}$ (or similarly for the other relations) to the set of
the relations $\mathtt{HW}_{\in\tau}^{(k)}$ for every arity $t$.

As a first step, we make use of [FMI+23c, Corollary 8.8] to replace the
arbitrary relations by gadgets using only $\mathtt{HW}_{=1}$ as relations. A
close examination of the proofs in [FMI+23c, Section 8.1] yields that the
results indeed holds for arbitrary, non-empty sets. We denote by
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\mathtt{HW}_{=1}}$ the variant of
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ where all relations
are $\mathtt{HW}_{=1}$ relations.

[[FMI+23c, Corollary 8.8]] Let $\sigma,\rho$ denote non-empty sets with
$\rho\neq\\{0\\}$. For all constants $d$, there is a parsimonious reduction
from $(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\text{Rel}}$ on instances of
arity at most $d$ and pathwidth $p$ to $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\mathtt{HW}_{=1}}$ on instances of arity at most $2^{d}+1$
and pathwidth $p+\mathcal{O}(1)$.

With the reduction from Definition 6.1, it remains to design gadgets realizing
$\mathtt{HW}_{=1}$ relations. Intuitively _a gadget $F$ realizes some relation
$R$_ if removing the relation $R$ and inserting the gadget $F$ does not
introduce any new solutions but also does not remove solutions when projecting
onto the remaining graph. We formalize this intuition in the following
definition.

######  Definition 6.2 (Realization of A Relation [FMI+23c, Definition 8.2]).

For a set of vertices $S$ with $d=\lvert S\rvert$, let $R\subseteq 2^{S}$
denote a $d$-ary relation. For an element $r\in R$, we write $x_{r}$ for the
length-$d$ string that is $\sigma_{0}$ at every position $v\in r$, and
$\rho_{0}$ at the remaining positions, i.e.,

$x_{r}\bm{[}\,v\,\bm{]}\coloneqq\left\\{\begin{array}[]{@{\;}c@{\quad}l@{}}\sigma_{0}&\text{if
$v\in r$},\\\ \rho_{0}&\text{otherwise.}\end{array}\right.$

We set $L_{R}\coloneqq\\{x_{r}\mid r\in R\\}$. A graph with portals $(H,U)$
_realizes_ $R$ if it realizes $L_{r}$. We say that $R$ is realizable if there
is a graph with portals that realizes $R$.

Unfortunately, the gadget constructions for the lower bound when the sets
$\sigma$ and $\rho$ are finite [FMI+23c], do not apply in our setting. A main
reason is that the gadgets for realizing $\mathtt{HW}_{=1}$ are heavily
tailored to the set $\sigma$ and $\rho$ and thus, do usually rely on the fact
that the sets are finite or cofinite. In particular, we need to create new
gadgets that can realize $\mathtt{HW}_{=1}$ relations from scratch.

For constructing the $\mathtt{HW}_{=1}$ gadgets, a significant obstacle is
that in our setting the sets $\sigma$ and $\rho$ do not necessarily have a
largest element which can be exploited in the construction. Moreover, directly
creating gadgets that realize the $\mathtt{HW}_{=1}$ relation for large arity
seems to be difficult; for a single vertex, having one selected neighbor is
essentially the same as having ${\mathrm{m}}+1$ selected neighbors. Instead,
we first realize the $\mathtt{HW}_{\in\rho-\min\rho+1}$ relation777For a set
$S\subseteq\mathbb{Z}_{\geq 0}$ and an integer $k\in\mathbb{Z}_{\geq 0}$, we
write $S-k$ for the set $\\{s-k\mid s\in S\\}$. which enforces that at least
one vertex is selected while not giving too many other guarantees.

We prove Section 2.2 in Section 6.1. *

This gadget can directly be used to instantiate $\mathtt{HW}_{=1}$ for arity
one, two, or three as stated by Corollary 6.3.

######  Corollary 6.3.

Let $\sigma$ and $\rho$ be two difficult periodic sets with the same period
${\mathrm{m}}$. Then, the relation $\mathtt{HW}_{=1}^{(k)}$ can be realized
for $k\in\bm{[}\,1\,\bm{.\,.}\,3\,\bm{]}$.

######  Proof 6.4.

We know that $1\in\rho-\min\rho+1$. Since $\sigma$ and $\rho$ are difficult,
we furthermore have ${\mathrm{m}}\geq 3$, which in turn implies that
$0,2,3,\not\in\rho-\min\rho+1$. Thus, the realization from Section 2.2 already
provides a realization of $\mathtt{HW}_{=1}^{(k)}$ for
$k\in\bm{[}\,1\,\bm{.\,.}\,3\,\bm{]}$.

##### Finalizing the Proof.

With the gadgets from Corollary 6.3, we can now realize $\mathtt{HW}_{=1}$
relations in the general setting. Before diving into the details of this
construction, we introduce a useful gadget provided by Focke et al. [FMI+23c].

[[FMI+23c, Lemma 5.2]] Let $\sigma$ and $\rho$ be two arbitrary non-empty
sets. For any $s\in\sigma$ and $r\in\rho$, there is a
$\\{\sigma_{s},\rho_{r}\\}$-provider.

The provider of Section 6 is extremely useful because it allows us to
introduce a vertex to a graph that can be both selected and unselected in
feasible solutions, as long as this vertex receives no additional selected
neighbors.

Next, we show how to realize $\mathtt{HW}_{=1}$ with an arbitrary arity, given
gadgets realizing $\mathtt{HW}_{=1}$ of arity one, two, and three.

Figure 3: The gadget constructions from Lemma 6.5.

######  Lemma 6.5.

Let $\sigma$ and $\rho$ denote sets such that $\mathtt{HW}_{=1}^{(1)}$,
$\mathtt{HW}_{=1}^{(2)}$, and $\mathtt{HW}_{=1}^{(3)}$ can be realized. Then,
for all $k\geq 1$, the relation $\mathtt{HW}_{=1}^{(k)}$ can be realized by a
gadget of size $\mathcal{O}(k)$.

######  Proof 6.6.

We use the same ideas as in the proof of [MSS21, Lemma 4.4], which uses a
simple approach of obtaining a higher degree relation by combining
$\mathtt{HW}_{=1}^{(2)}$ and $\mathtt{HW}_{=1}^{(3)}$ relations in a path-like
manner.

Concretely, we proceed by strong induction. The base cases, $1\leq k\leq 3$
hold by assumption.

For the induction step $(k\geq 4)$, we assume that we can realize the relation
for all arities from $1$ to $k$, and show that we can realize the relation for
arity $k+1$. We first describe the gadget construction; then we argue about
its properties. Also consult Figure 3 for a visualization of the construction.

Denote by $u_{1},\dots,u_{k+1}$ the vertices of the relation scope. First, we
set $s=\min\sigma\in\sigma$ and $r=\min\rho\in\rho$, and we add to the graph
two independent copies of the gadget from Section 6 for $s$ and $r$; call the
portal vertices of said gadgets $v_{1}$ and $v_{2}$, respectively. Next, we
add the relation $\mathtt{HW}_{=1}^{(k)}$ with scope
$u_{1},\dots,u_{k-1},v_{1}$ to the graph. Then, we add the relation
$\mathtt{HW}_{=1}^{(2)}$ with scope $v_{1},v_{2}$ to the graph. After that, we
add the relation $\mathtt{HW}_{=1}^{(3)}$ with scope $v_{2},u_{k},u_{k+1}$ to
the graph. Finally, we replace all relations with the respective realization
gadgets, which exist by assumption. For the rest of this proof, call the
resulting graph $G$.

######  Claim 8.

The graph $G$ realizes the $\mathtt{HW}_{=1}^{(k+1)}$ relation.

First, assume that no vertex of the relation scope is selected. In this case,
both $v_{1}$, and $v_{2}$ must be selected, which is not possible due to the
$\mathtt{HW}_{=1}^{(2)}$ relation.

Next, it is not possible that two vertices of $u_{1},\dots,u_{k-1}$ or two
vertices of $u_{k},u_{k+1}$ are selected, due to the $\mathtt{HW}_{=1}^{(k)}$
and $\mathtt{HW}_{=1}^{(3)}$ relations. If one vertex of $u_{1},\dots,u_{k-1}$
and one vertex of $u_{k}$ and $u_{k+1}$ are selected, then both $v_{1}$, and
$v_{2}$ cannot be selected, which is once again impossible in any solution.

Finally, if one vertex of $u_{1},\dots,u_{k+1}$ is selected, then exactly one
of $v_{1}$ and $v_{2}$ must be selected, and all relations are fulfilled.
Moreover, the vertices $v_{1}$ and $v_{2}$ can always receive a feasible
number of neighbors, regardless of their selection status.

To conclude the proof, we analyze the size of the gadget. The gadgets for
arities $1$, $2$ and $3$, and the gadgets from Section 6 have constant size
each. Hence, the size of the gadget grows only by a constant amount as we go
from one arity to the next, proving that the size of the gadget for arity $k$
is linear in $k$.

With Corollaries 6.3 and 6.5 at hand, we can now finally prove the main result
of this section, that is, prove Definition 2.6 which we restate here for
convenience.

######  Proof 6.7.

Let $\sigma$ and $\rho$ denote sets as in the statement of the lemma. Further,
let $I_{1}$ denote an instance of $(\sigma,\rho)\mathchar
45\relax$DomSet${}^{\text{Rel}}$, let pw denote the pathwidth of the graph
corresponding to $I_{1}$, and let $d$ denote the arity of the graph
corresponding to $I_{1}$.

First, we apply Definition 6.1 to obtain an equivalent instance $I_{2}$ of
$(\sigma,\rho)\mathchar 45\relax$DomSet${}^{\mathtt{HW}_{=1}}$ with pathwidth
$\textup{{pw}}+\mathcal{O}(1)$ and arity $2^{d}+1$. By Corollaries 6.3 and
6.5, we can replace all remaining relations of the graph with their
realizations. To do this, observe that any remaining relation is a
$\mathtt{HW}_{=1}$ relation. To replace such a relation with a graph, we add
the graph that realizes this relation, and unify its portal vertices with the
vertices of the relation. Write $I_{3}$ to denote the resulting instance of
$(\sigma,\rho)\mathchar 45\relax$DomSet.

######  Claim 9.

The instances $I_{2}$ and $I_{3}$ are equivalent.

First, assume that $I_{2}$ is a yes-instance. Then, selecting the same
vertices that are selected in $I_{2}$, and extending this solution to the
newly added graphs results in a solution for instance $I_{3}$. Because all
relations of $I_{2}$ are fulfilled, such an extension is indeed possible by
Definition 6.2.

Now, assume that $I_{3}$ is a yes-instance. Since no solution can select
neighbors of vertices of $I_{3}$ that were not yet present in $I_{2}$,
restricting the solution of $I_{3}$ to graph $I_{2}$ ensures that all vertices
of $I_{2}$ receive a feasible number of neighbors. Moreover, the gadgets that
were added to replace the relations ensure that exactly one vertex of each
relation of $I_{2}$ must be selected in any solution, hence, this solution
also fulfills all relations.

######  Claim 10.

The instance $I_{3}$ has a pathwidth of $\textup{{pw}}+\mathcal{O}(2^{d})$.

Recall from Definition 5.8 that the pathwidth of $I_{2}$ is defined as the
pathwidth of the graph obtained by forming a clique out of all vertices in the
relation scope for each relation. Let $\hat{I}_{2}$ denote the graph that is
obtained from $I_{2}$ by applying the aforementioned transformation. Consider
a path decomposition of $\hat{I}_{2}$. For any relation, there exists a bag of
the decomposition in which all vertices of the relation are present. We can
duplicate this bag and reconnect the bags in the natural way. Then, we simply
add all vertices of the gadget that realizes the relation to the duplicated
bag. It is easy to see that one can obtain a path decomposition of $I_{3}$ by
performing this operation for each relation such that we never add the
vertices of two realization gadgets to the same bag. The width of this
decomposition is the width of the decomposition of $I_{2}$ plus the size of
the largest gadget that was added to the graph. Using Lemma 6.5, we observe
that this results in a decomposition of width
$\textup{{pw}}+\mathcal{O}(2^{d})$, as desired. Combining 9 and 10, we obtain
the claimed result.

###  6.1 Realizing $\mathtt{HW}_{\in\rho-\min\rho+1}$

In this section, we construct gadgets that realize
$\mathtt{HW}_{\in\rho-\min\rho+1}$. Formally, we prove Section 2.2, which we
restate here for convenience.

(a) The case $\min\rho\geq 2$ illustrated for $\min\sigma=1,\min\rho=3$.

(b) The case $\min\rho=1,\min\sigma\geq 2$ illustrated for
$\min\sigma=2,\min\rho=1$ and $r=1$.

(c) The case $\min\rho=\min\sigma=1$ illustrated for $r=1,s=1$.

(d) The case $\min\rho=1,\min\sigma=0$.

Figure 4: The gadget constructions from Section 2.2. In each sketched
construction we mark vertices corresponding to a feasible solution within the
gadget. From the relation scope $U$, we select an arbitrary vertex.

######  Proof 6.8.

We consider different cases, depending on $\sigma$ and $\rho$. Note that
$\sigma$, $\rho$ being difficult implies that ${\mathrm{m}}\geq 3$ and
$\min\rho\geq 1$.

  * •

If $\min\rho\geq 2$, then we use 11.

  * •

If $\min\rho=1$ and $\min\sigma\geq 2$, then we use 12.

  * •

If $\min\rho=1$, $\min\sigma=1$, then we use 13.

  * •

If $\min\rho=1$, $\min\sigma=0$, then we use 14.

Consult Figure 4 for a visualization of the gadgets used in the different
cases of the proof.

In the following, we describe the gadgets in the strongest-possible way, that
is, we describe the minimal requirements for the gadgets to work.

We start with the first case where $\min\rho\geq 2$. Clearly,
${\mathrm{m}}\geq 3$ implies that $\min\sigma+1\notin\sigma$.

######  Claim 11.

Let $\sigma$ and $\rho$ be arbitrary non-empty sets such that $\min\rho\geq 2$
and $\min\sigma+1\notin\sigma$. Then, $\mathtt{HW}_{\in\rho-\min\rho+1}$ is
realizable.

For all $i\in\bm{[}\,1\,\bm{.\,.}\,\min\rho-1\,\bm{]}$, we create a clique
$K_{\min\sigma+1}^{(i)}$ on $\min\sigma+1$ vertices. We create a vertex $v$
that is made adjacent to all vertices in the scope of the relation. Finally,
we select a vertex $u^{(i)}$ from the clique $K_{\min\sigma+1}^{(i)}$, and
make $v$ adjacent to $u^{(i)}$ for all
$i\in\bm{[}\,1\,\bm{.\,.}\,\min\rho-1\,\bm{]}$.

The correctness relies on the fact that all vertices of each clique must be
selected in a solution. To see this, fix some
$i\in\bm{[}\,1\,\bm{.\,.}\,\min\rho-1\,\bm{]}$ and consider the clique
$K_{\min\sigma+1}^{(i)}$.

If $\min\sigma+1=1$, then the clique consists of a single vertex $u^{(i)}$
that must be selected since $u^{(i)}$ only has a single neighbor, and if the
vertex would be unselected, it would need at least two neighbors because of
$\min\rho\geq 2$.

If $\min\sigma+1=2$, then the clique consists of two vertices connected by an
edge. Let $w$ be the vertex of the clique that is not $u^{(i)}$. Since $w$ has
only a single neighbor, vertex $w$ must be selected. But, since
$\min\sigma=1$, this means that also $u^{(i)}$, the only neighbor of $w$, must
be selected.

If $\min\sigma+1\geq 3$, assume that some vertex $v^{(i)}$ of the clique that
is not $u^{(i)}$ is not selected in a solution. Then, $v^{(i)}$ must have two
selected neighbors in the clique. At least one of them, denote it by
$w^{(i)}$, must be different from $u^{(i)}$, Hence, $w^{(i)}$ is selected and
requires $\min\sigma$ selected neighbors, which implies that all vertices of
the clique must be selected, contradicting that $v^{(i)}$ is not selected.

By the previous argument vertex $v$ is adjacent to a vertex $u^{(i)}$ such
that $u^{(i)}$ has exactly $\min\sigma$ selected neighbors in the clique.
Since $\min\sigma+1\not\in\sigma$, vertex $v$ cannot be selected. Furthermore,
$v$ is adjacent to $\min\rho-1$ vertices that are selected, and we know that
$\min\rho-1\not\in\rho$. Thus, at least one vertex in the scope of the
relation must be selected, so that $v$ can have enough neighbors. Moreover,
exactly $r$ vertices from the scope must be selected where
$r+\min\rho-1\in\rho$.

For all the remaining cases we assume that $\min\rho=1$. We proceed with the
case where $\min\sigma\geq 2$.

######  Claim 12.

Let $\sigma$ and $\rho$ be arbitrary non-empty sets such that $\min\rho=1$,
there exists an $r\in\rho$ with $r+1\notin\rho$, $\min\sigma\geq 2$, and
$\min\sigma+1\notin\sigma$. Then, $\mathtt{HW}_{\in\rho}$ is realizable.

Observe that in our case choosing $r=\min\rho$ is possible. The gadget
contains the $r+2$ vertices $v,z,p_{1},\dots,p_{r}$ and $r$ cliques
$K^{(i)}_{\min\sigma+1}$ on $\min\sigma+1$ vertices each where
$i\in\bm{[}\,1\,\bm{.\,.}\,r\,\bm{]}$, and $u_{i}$ and $w_{i}$ denote two
distinct vertices of the clique $K^{(i)}_{\min\sigma+1}$. We make $v$ adjacent
to all vertices of the scope and to $z$. Vertex $z$ is adjacent to all $u_{i}$
and vertex $w_{i}$ is adjacent to $p_{i}$ for all $i$.

In any solution, all vertices of each clique $K^{(i)}_{\min\sigma+1}$ must be
selected due to vertex $p_{i}$: Vertex $p_{i}$ has only a single neighbor and
hence, cannot be selected as $\min\sigma\geq 2$. Moreover, since $\min\rho=1$,
the unique neighbor $w_{i}$ of $p_{i}$ must also be selected. The selected
vertex $w_{i}$ then needs $\min\sigma$ selected neighbors, and so the whole
clique must be selected. Then, vertex $u_{i}$ has $\min\sigma$ selected
neighbors, which implies that its only other neighbor $z$ cannot be selected.
Since the unselected vertex $z$ already has $r$ selected neighbors $u_{i}$,
vertex $v$ cannot be selected as $r+1\notin\rho$. However, as $v$ is
unselected and has no selected neighbors, it requires to have $t$ selected
neighbors for some $t\in\rho$ which have to stem from the scope of the
relation.

Next we change the requirement for $\min\sigma$ by assuming $\min\sigma=1$.

######  Claim 13.

Let $\sigma$ and $\rho$ be arbitrary non-empty sets such that $\min\rho=1$,
there exists an $r\in\rho$ with $r+1\notin\rho$, $\min\sigma=1$,
$\min\sigma+1\notin\sigma$, and there is an $s\in\sigma$ with
$s+1,s+2\notin\sigma$. Then $\mathtt{HW}_{\in\rho}$ is realizable.

Observe that this covers our case by setting $r=1$ and $s=1$ as
${\mathrm{m}}\geq 3$. Assume we can construct a gadget $F$ where a
distinguished vertex $p$ is forced to be not selected, and the only possible
solution also provides exactly one selected neighbor for this vertex $p$. Then
we can realize the relation as follows. Create $r$ copies of $F$ which we
denote by $F_{1},\dots,F_{r}$ where we identify all vertices
$p_{1},\dots,p_{r}$ with a new vertex $p$ We additionally add a vertex $v$ and
make $v$ adjacent to all vertices in the scope of the relation and $p$.

By the properties of the gadget $F$, the vertex $p$ is not selected and has
one neighbor in each copy $F_{i}$. Hence, vertex $v$ cannot be selected as
$r+1\notin\rho$. Therefore, the number of vertices that are selected from the
scope must be $t$ for some $t\in\rho$.

It remains to construct the gadget we assumed to exist above. For this we
introduce $2s+3$ vertices $p,q,w$ and $u_{1},v_{1},\dots,u_{s},v_{s}$ where
$p,q,w$ are connected to a path and $q,u_{i},v_{i}$ are also connected to form
a path.

Since $\min\rho=\min\sigma=1$, all vertices $u_{i}$ must be selected because
of the requirement of each $v_{i}$. Moreover, because the only neighbor of $w$
is $q$, vertex $q$ must be selected as well. Hence, as
$\min\sigma+1\notin\sigma$ and $q$ is selected, each vertex $u_{i}$ forces
$v_{i}$ to not be selected. With this selection vertex $q$ has $s$ neighbors.
Since $s+1,s+2\notin\sigma$, it is not possible to select any of the vertices
$w$ and $p$ which have one selected neighbor each.

This concludes the construction of the auxiliary gadget $F$ with $p$ as the
distinguished vertex.

For the remaining case we now assume that $\min\sigma=0$.

######  Claim 14.

Let $\sigma$ and $\rho$ be arbitrary non-empty sets such that $\min\rho=1$,
and $2,3\not\in\rho$, $\min\sigma=0$, and $\min\sigma+1\notin\sigma$. Then
$\mathtt{HW}_{\in\rho}$ is realizable.

Observe that our case is covered since ${\mathrm{m}}\geq 3$, $\min\rho=1$ and
$\min\sigma=0$ implies all required conditions. We start by creating a star
graph $S_{3}$ with $3$ leaves. Let $c$ be the center of the star. Add a vertex
$v$ to the graph, and make $v$ adjacent to one leaf of $S_{3}$, and to all
vertices in the scope of the relation.

We first argue that in any solution, vertex $c$ must be selected, and
furthermore, all of its neighbors cannot be selected. Towards a contradiction,
assume that $c$ is not selected. Then, there are two leaves of $c$ that must
be selected to become happy. However, for $c$, two out of three of its
neighbors are now selected, and $2\not\in\rho,3\not\in\rho$. Thus, $c$ must be
selected in any solution. The leaves of $c$ that have no other neighbors
cannot be selected now, as they have selected neighbor $c$ and
$1\not\in\sigma$.

Consider the leaf $\ell$ of $S_{3}$ that is a neighbor of $v$. This leaf has
two neighbors, one of which is selected. As $c$ is selected and
$1\notin\sigma$, vertex $\ell$ cannot be selected. Furthermore, $v$ cannot be
selected either, because selecting $v$ would give $\ell$ two selected
neighbors and $2\not\in\rho$. Thus, $v$ is not selected and requires at least
one more selected vertex from the scope of the relation.

Finally, we can make all vertices of the gadget happy if $r\in\rho$ vertices
of the relation scope are selected. In that case, $c$ is the only gadget
vertex that must be selected. The leaves of $c$ are happy, because they have a
single selected neighbor and are unselected. Furthermore, vertex $v$ is happy,
because it has $r$ selected neighbors in the scope of the relation.

This finishes the proof of Section 2.2 by combining 11, 12, 13, and 14.

##  7 Turn the Lights Off!

As already mentioned in the introduction the decision version of Lights Out!
is solvable in polynomial-time by Gaussian elimination on the corresponding
set of linear equations [Sut89, AF98]. However, as the minimization version of
the problem is NP-complete when $\rho=\\{x\in\mathbb{Z}_{\geq 0}\mid
x\equiv_{2}1\\}$ [Sut88, CKG01, HKT00b], it is open whether our algorithm from
Section 1 is optimal or not. In this section we answer this question in the
positive by formally proving Section 1.

*

Recall that we denote by Reflexive-AllOff the minimization version of
$(\sigma,\rho)\mathchar 45\relax$DomSet where $\sigma=\\{x\in\mathbb{Z}_{\geq
0}\mid x\equiv_{2}0\\}$ and $\rho=\\{x\in\mathbb{Z}_{\geq 0}\mid
x\equiv_{2}1\\}$, and by AllOff the variant where
$\sigma=\rho=\\{x\in\mathbb{Z}_{\geq 0}\mid x\equiv_{2}1\\}$.

We use the NP-hardness result by Sutner in [Sut88, Theorem 3.2] as a basis and
strengthen our results by directly proving the bounds for the larger parameter
pathwidth. We consider AllOff in Section 7.2 and Reflexive-AllOff in Section
7.1. The proof of Section 1 then directly follows from the combination of the
main results of the aforementioned sections.

###  7.1 Lower Bound for Reflexive-AllOff

In the following we prove the lower bound for Reflexive-AllOff by a reduction
from $k$-SAT to an equivalent instance of Reflexive-AllOff with small
pathwidth.

######  Theorem 7.1.

For all $\varepsilon>0$, there is no algorithm deciding in time
$(2-\varepsilon)^{\textup{{pw}}}\cdot n^{\mathcal{O}(1)}$ whether there exists
a solution of size at most $k$ for a given Reflexive-AllOff instance even if
we are given a path decomposition of width pw, unless SETH fails.

######  Proof 7.2.

We prove the lower bound by a reduction from CNF-SAT. Fix some $\varepsilon>0$
for this and let $k$ be the smallest integer such that $k$-SAT does not have a
$(2-\varepsilon)^{n}\cdot(n+m)^{\mathcal{O}(1)}$ algorithm where $n$ is the
number of variables and $m$ the number of clauses.

Consider an arbitrary $k$-SAT formula $\varphi$ with $n$ variables
$x_{1},\dots,x_{n}$ and $m$ clauses $C^{1},\dots,C^{m}$ as input.888We assume
that every clause contains exactly $k$ literals. This restriction is not of
technical nature as the constructions works for the general case but rather to
keep notation simple and clean. In the following we construct a graph
$G_{\varphi}$ as an instance of Reflexive-AllOff. The graph is build based on
variable gadgets, clause gadgets, and a single negation gadget.

We first construct the gadgets and then describe how they are connected. For
every variable $x_{i}$ where $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, the
_variable gadget_ $V_{i}$ consists of the two vertices $v_{i}$ and
$\overline{v}_{i}$ that are connected by an edge.

For every clause $C^{j}=\lambda^{j}_{1}\lor\dots\lor\lambda^{j}_{k}$ where
$j\in\bm{[}\,1\,\bm{.\,.}\,m\,\bm{]}$, the _clause gadget_ $D^{j}$ contains
the following vertices and edges. There are $k$ _literal vertices_
$t^{j}_{1},\dots,t^{j}_{k}$ where each vertex corresponds to one literal of
the clause. Moreover, the gadget $D^{j}$ contains so-called _subset vertices_
$s^{j}_{L}$ for all $L\subsetneq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$, that is, for
every proper subset of the literals of the clause, there exists a vertex
labeled with this subset (and the gadget index). For each subset
$L\subsetneq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$, the subset vertex $s^{j}_{L}$ is
connected to the literal vertex $t^{j}_{\ell}$ if and only if $\ell\in L$.
Moreover, all subset vertices together form a clique on $2^{k}-1$ vertices.

The negation gadget consists of three vertices $q_{0}$, $q_{1}$, and $q_{2}$
that are connected to a path on three vertices with $q_{1}$ in the middle.

As a last step it remains to connect the vertices of the different gadgets.
Intuitively, each literal vertex of the clause gadget is connected to the
corresponding variable vertex of the variable gadgets. Consider literal
$\lambda^{j}_{\ell}$, that is, the $\ell$th literal in the $j$th clause. If
this literal is positive, i.e., if $\lambda^{j}_{\ell}=x_{i}$ for some
variable $x_{i}$, then the vertex $t^{j}_{\ell}$ is adjacent to vertex
$v_{i}$. If the literal is negative, i.e., if $\lambda^{j}_{\ell}=\lnot x_{i}$
for some variable $x_{i}$, then the vertex $t^{j}_{\ell}$ is also adjacent to
vertex $v_{i}$ but additionally also to vertex $q_{1}$.

This concludes the description of $G_{\varphi}$. See Figure 5 for an
illustration of the clause gadget and the negation gadget. To prove the
correctness of this reduction we set $m+n+1$ as the upper bound for the number
of selected vertices.

Figure 5: A depiction of the clause gadget for the clause $x_{1}\lor
x_{2}\lor\neg x_{3}$ as well as the negation gadget. Some indices are omitted
for simplicity.

######  Claim 15.

If $\varphi$ is a yes-instance of $k$-SAT, then $(G_{\varphi},n+m+1)$ is a
yes-instance of Reflexive-AllOff.

Let $\pi$ be a satisfying assignment for the $k$-SAT formula $\varphi$. We
select the following vertices:

In the variable gadget of variable $x_{i}$, we select $v_{i}$ if
$\pi(x_{i})=1$ and $\overline{v}_{i}$ otherwise.

In the clause gadget of clause $C^{j}$, let
$L\subsetneq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$ be the set of literal indices of
this clause that are _not_ satisfied. (This is well-defined as $\pi$ is a
satisfying which means that not all literals are unsatisfied.) We select
vertex $s^{j}_{L}$.

We select vertex $q_{1}$ from the negation gadget. Let $S$ denote the set of
all selected vertices.

Since we select exactly one vertex from each gadget, the size of $S$ is
precisely $n+m+1$. It remains to prove that $S$ is indeed a solution, that is,
$S$ is a $(\sigma,\rho)$-set where $\sigma=\\{x\in\mathbb{Z}_{\geq 0}\mid
x\equiv_{2}0\\}$ and $\rho=\\{x\in\mathbb{Z}_{\geq 0}\mid x\equiv_{2}1\\}$.

First, consider the vertices of the negation gadget. Since only vertex $q_{1}$
is selected, the vertices $q_{0}$ and $q_{2}$ have exactly one selected
neighbors. As none of the literal vertices are selected, vertex $q_{1}$ is
adjacent to zero selected vertices.

Consider any vertex of the variable gadgets and observe that none of them have
a selected neighbor outside the gadget. By our choice of $S$, exactly one of
the two vertices is selected and has no selected neighbors, while the other
vertex is not selected and has exactly one selected neighbor, the one in the
variable gadget.

It remains to check the vertices of the clause gadget. For the subset vertices
we notice that in every clause gadget exactly one of them is selected. Recall
that all subset vertices of one clause are connected to each other, and they
are not connected to any other vertices outside the gadget but only to the
unselected literal vertices of the gadget. This implies that exactly one of
the subset vertices is selected and has no selected neighbors, whereas the
other subset vertices are not selected and have exactly one selected neighbor.

Next we check the literal vertices. Consider a positive literal, say
$\lambda^{j}_{\ell}=x_{i}$. By assumption $t^{j}_{\ell}$ is unselected and has
vertex $v_{i}$ as neighbor if $\pi(x_{i})=1$. In this case no subset vertex
$s^{j}_{L}$ with $\ell\in L$ is selected by definition of $S$. Hence, the
vertex has exactly one selected neighbor. If $\pi(x_{i})=0$, then the literal
does not satisfy the clause and hence, by the definition of $S$, a vertex
$s^{j}_{L}$ is selected where $\ell\in L$.

As a last step we check the literal vertices corresponding to negated
variables, say $t^{j}_{\ell}=\lnot x_{i}$. Once more, this vertex is not
selected but always adjacent to the selected vertex $q_{1}$ from the negation
gadget. If $\pi(x_{i})=1$, then also the neighboring vertex $v_{i}$ is
selected. However, this is not a problem since in this case the literal does
not satisfy the clause and hence, a subset vertex $s^{j}_{L}$ with $\ell\in L$
must be selected. Thus, the literal vertex is adjacent to three selected
vertices. If $\pi(x_{i})=0$, then the literal satisfies the clause and no
subset vertex $s^{j}_{L}$ with $\ell\in L$ is selected; the literal vertex has
exactly one selected neighbor.

We conclude that every selected vertex of the graph has no selected neighbors,
whereas every unselected vertex has either exactly one or exactly three
selected neighbors.

As a next step we show the reverse direction of the correctness.

######  Claim 16.

If $(G_{\varphi},n+m+1)$ is a yes-instance of Reflexive-AllOff, then $\varphi$
is a yes-instance of $k$-SAT.

Consider a solution $S$ of the Reflexive-AllOff instance of size at most
$n+m+1$. Recall that $S$ is a $(\sigma,\rho)$-set for $G_{\varphi}$ where
$\sigma=\\{x\in\mathbb{Z}_{\geq 0}\mid x\equiv_{2}0\\}$ and
$\rho=\\{x\in\mathbb{Z}_{\geq 0}\mid x\equiv_{2}1\\}$.

In the negation gadget at least one vertex must be selected as $q_{0}$ and
$q_{2}$ must be selected themselves or require one selected neighbor which can
only be $q_{1}$. Similarly, in each variable gadget $V_{i}$, the set $S$
contains at least one vertex; vertex $\overline{v}_{i}$ is either selected
itself or it requires a selected neighbor (which must be $v_{i}$).

In each clause gadget $D^{j}$, we must also select at least one vertex which
must be a subset vertex. Indeed, the subset vertex $s^{j}_{\varnothing}$ must
either be selected or have a selected neighbor. As all neighbors of this
subset vertex are also subset vertices, the claim follows.

Hence, we see that any solution $S$ of size at most $n+m+1$ must select
_exactly one_ vertex of each variable gadget, as well as exactly one subset
vertex of each clause gadget, and vertex $q_{1}$ of the negation gadget.

Based on these observations we define an assignment $\pi$ for the formula
$\varphi$ by setting $\pi(x_{i})=1$ if and only if $v_{i}\in S$ and
$\pi(x_{i})=0$ otherwise.

In the following we prove that $\pi$ satisfies $\varphi$. For this consider an
arbitrary clause $C^{j}$. By the above discussion, we know that there is some
selected subset vertex $s^{j}_{L}$ of the clause gadget $D^{j}$. Since
$L\subsetneq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$, there is, by the construction of
$G_{\varphi}$, a literal vertex $t^{j}_{\ell}$ where
$\ell\in\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}\setminus L$. Since this vertex
$t^{j}_{\ell}$ is not selected, it must have an odd number of neighbors in
$S$. We first consider the case that the corresponding literal
$\lambda^{j}_{\ell}$ is positive, that is, $\lambda^{j}_{\ell}=x_{i}$ for some
variable $x_{i}$. In this case the only selected neighbor of $t^{j}_{\ell}$ is
$v_{i}$. From $v_{i}\in S$ the definition of $\pi$ gives $\pi(x_{i})=1$ which
implies that the clause $C^{j}$ is satisfied by literal $\lambda^{j}_{\ell}$.
Now consider the case when $\lambda^{j}_{\ell}=\lnot x_{i}$ for some variable
$x_{i}$. In this case vertex $t^{j}_{\ell}$ is adjacent to the selected vertex
$q_{1}$ of the negation gadget, by the construction of $G_{\varphi}$ and the
above observations. As the literal vertex is still unselected and only
adjacent to unselected subset vertices and one additional variable vertex, the
variable vertex $v_{i}$ cannot be selected. Hence, the definition of the
assignment $\pi$ gives $\pi(x_{i})=0$ which directly implies that the clause
$C^{j}$ is satisfied by the literal $\lambda^{j}_{\ell}$.

Before we combine all parts of the proof to obtain the lower bound, we first
provide a bound on the pathwidth of the constructed graph.

######  Claim 17.

$G_{\varphi}$ has pathwidth at most $2^{k}+k+n$.

If we delete vertex $q_{1}$ and, for all
$i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, the variable vertex $v_{i}$, then the
graph decomposes into small components of size at most $2^{k}-1+k$. This
allows us to get a path decomposition of small width.

Concretely, we create a node for every variable gadget, clause gadget, and the
negation gadget. We add the vertices of the corresponding gadgets to the bag
of the node. We connect these nodes in an arbitrary way to form a path. As a
last step we extend all bags by adding the vertices in $\\{v_{i}\mid
i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}\\}\cup\\{q_{1}\\}$. It is easy to see that
this is a valid path decomposition.

The bags corresponding to the variable gadgets have size $1+(n+1)$ and the
bags of the clause gadgets have size $2^{k}-1+k+(n+1)$. Finally, the bag of
the negation gadget has size $2+(n+1)$. Hence, the pathwidth of the graph is
at most $\max(2^{k}+k+n-1,n+2)\leq 2^{k}+k+n$.

Recall that we fixed some $\varepsilon>0$ and set $k$ to the smallest integer
such that $k$-SAT does not have an algorithm with running time
$(2-\varepsilon)^{n}\cdot n^{\mathcal{O}(1)}$ where $n$ is the number of
variables. For a given $k$-SAT formula $\varphi$ with $n$ variables and $m$
clauses we constructed an equivalent Reflexive-AllOff instance
$(G_{\varphi},n+m+1)$ together with a path decomposition.

Towards a contradiction, assume that Reflexive-AllOff can be solved in time
$(2-\varepsilon)^{\textup{{pw}}}\cdot N^{\mathcal{O}(1)}$. Applying this
algorithm to the constructed instance $(G_{\varphi},n+m+1)$, yields, by using
15, 16, and 17, an algorithm for $k$-SAT with running time

$(2-\varepsilon)^{\textup{{pw}}}\cdot(n+m)^{\mathcal{O}(1)}=(2-\varepsilon)^{2^{k}+k+n}\cdot(n+m)^{\mathcal{O}(1)}\leq(2-\varepsilon)^{n}\cdot(n+m)^{\mathcal{O}(1)}$

as the constant $k$ only depends on the fixed value $\varepsilon$. This
directly contradicts SETH and finishes the proof.

###  7.2 Lower Bound for AllOff

In the previous section we have seen the lower bound for Reflexive-AllOff. In
this section we focus on the non-reflexive version AllOff instead. Recall,
that when representing this problem as $(\sigma,\rho)\mathchar 45\relax$DomSet
we have $\sigma=\rho=\\{x\in\mathbb{Z}_{\geq 0}\mid x\equiv_{2}1\\}$, that is,
every vertex needs and odd number of selected neighbors independent of whether
the vertices are themselves selected or not.

We again use the ideas by Sutner [Sut88] which allows a reduction in a similar
spirit as the previous one. The main difference is that the subset vertices
now do not form a clique. As there are naturally other minor modifications we
present the full proof.

######  Theorem 7.3.

For all $\varepsilon>0$, there is no algorithm that for a given instance of
AllOff decides in time $(2-\varepsilon)^{\textup{{pw}}}\cdot
n^{\mathcal{O}(1)}$ whether there exists a solution of size at most $k$ even
if we are given a path decomposition of width pw, unless SETH fails.

######  Proof 7.4.

Similar to Theorem 7.1, we prove the bound by a reduction from CNF-SAT. For
this fix some $\varepsilon>0$ and let $k$ be the smallest integer such that
$k$-SAT has no $(2-\varepsilon)^{n}\cdot(n+m)^{\mathcal{O}(1)}$ algorithm
under SETH where $n$ is the number of variables and $m$ the number of clauses.

Let $\varphi$ be an arbitrary $k$-SAT instance with $n$ variables
$x_{1},\dots,x_{n}$ and $m$ clauses $C^{1},\dots,C^{m}$ as input.999As for the
proof of Theorem 7.1 we assume purely for the ease of the presentation that
each clause contains exactly $k$ literals.  We construct a graph $G_{\varphi}$
that consists of variable and clause gadgets. See Figure 6 for an illustration
of the construction.

For every variable $x_{i}$ where $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, the
graph $G_{\varphi}$ contains a variable gadget $V_{i}$. Gadget $V_{i}$
consists of a cycle of length four on the four vertices $v_{i}$, $w_{i}$,
$\overline{v}_{i}$, and $\overline{w}_{i}$ (in this order).

For every clause $C_{i}=\lambda^{j}_{1}\lor\dots\lor\lambda^{j}_{k}$ where
$j\in\bm{[}\,1\,\bm{.\,.}\,m\,\bm{]}$, the graph $G_{\varphi}$ contains a
clause gadget $D^{j}$. This gadget $D^{j}$ contains $k$ literal vertices
$t^{j}_{1},\dots,t^{j}_{k}$, that is, one distinguished vertex for every
literal of the clause. Additionally, $D^{j}$ contains, for every subset
$L\subsetneq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$, a so called _subset_ -vertex
$s^{j}_{L}$, that is, for every proper subset of the literals of the clause,
there exists a vertex labeled with the subset (and the gadget index). These
subset vertices are used to indicate which literals of the clause are _not_
satisfied by the encoded assignment. As a last vertex there is an additional
vertex $h^{j}$ (for happy) in $D^{j}$. There are two different groups of edges
in the gadget; first, each subset vertex $s^{j}_{L}$ is connected to each
literal vertex $t^{j}_{\ell}$ if and only if $\ell\in L$. Second, the vertex
$h^{j}$ is connected to all subset vertices of the gadget $D^{j}$.

As a last step of the construction we describe the edges encoding the
appearance of variables in the clauses. Intuitively each literal vertex of the
clause gadget is connected to the corresponding variable vertex of the
variable gadgets. Formally, if the $\ell$th literal of the $j$th clause is
positive, i.e., if $\lambda^{j}_{\ell}=x_{i}$ for some variable $x_{i}$, then
vertex $t^{j}_{\ell}$ is adjacent to vertex $v_{i}$. If the $\ell$th literal
is negative, i.e., if $\lambda^{j}_{\ell}=\neg x_{i}$ for some variable
$x_{i}$, then vertex $t^{j}_{\ell}$ is again adjacent to vertex $v_{i}$ but
also to vertex $h^{j}$.

This concludes the description of $G_{\varphi}$. We prove in the following
that the AllOff instance $(G_{\varphi},2m+2n)$ is equivalent to the input
instance $\varphi$ of $k$-SAT.

(a) A depiction of the variable gadget.

(b) A depiction of the clause gadget for the clause $x_{1}\lor x_{2}\lor\neg
x_{3}$.

Figure 6:  A depiction of a literal gadget and a clause gadget from the proof
of the lower bound for AllOff. Some indices are omitted for simplicity.

We first show that if the $k$-SAT formula $\varphi$ is satisfiable, then the
constructed AllOff instance is a yes-instance.

######  Claim 18.

If $\varphi$ is a yes-instance of $k$-SAT, then $(G_{\varphi},2m+2n)$ is a
yes-instance of AllOff.

Consider a satisfying assignment $\pi$ for $\varphi$. We select the following
vertices:

For all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$, if $\pi(x_{i})=1$, then we
select the two vertices $v_{i}$ and $w_{i}$. If $\pi(x_{i})=0$, then we select
the other two vertices of the variable gadget, which are $\overline{v}_{i}$
and $\overline{w}_{i}$.

For all $j\in\bm{[}\,1\,\bm{.\,.}\,m\,\bm{]}$, we select in the clause gadget
the vertex $h^{j}$. Moreover, let $L\subsetneq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$
be the set of all positions of the literals of the clause that are _not_
satisfied by $\pi$. Since the clause is satisfied by the assignment, the set
$L$ cannot contain all literals of the clause. Thus, there is a subset vertex
$s^{j}_{L}$ corresponding to this set $L$. We select this vertex $s^{j}_{L}$.
Let $S$ denote the set of all selected vertices. Clearly this set contains
exactly $2n+2m$ vertices as we select exactly two vertices from every gadget.
It remains to show that $S$ is indeed a solution, that is, every vertex of
$G_{\varphi}$ has an odd number of neighbors in $S$.

Consider any vertex of the variable gadgets and observe that none of them have
a selected neighbor outside the gadget. With this it is easy to see that each
vertex of a variable gadget has exactly one selected neighbor in $S$.

Each subset vertex of a clause gadget $D^{j}$ has exactly one selected
neighbor, namely vertex $h^{j}$. Furthermore, vertex $h^{j}$ has exactly one
selected neighbor, namely the selected subset vertex of the clause gadget. Now
consider an arbitrary literal vertex $t^{j}_{\ell}$. First assume that the
corresponding literal is positive, that is, $\lambda^{j}_{\ell}=x_{i}$ for
some variable $x_{i}$. If this literal is satisfied, the vertex $v_{i}$ in the
variable gadget is selected, otherwise if the literal is not satisfied,
$t^{j}_{\ell}$ is a neighbor if the selected subset vertex.

Now assume that the corresponding literal is negative, that is,
$\lambda^{j}_{\ell}=\lnot x_{i}$ for some variable $x_{i}$. If the variable
$x_{i}$ is not satisfied by $\pi$, then the only selected neighbor of
$t^{j}_{\ell}$ is $h^{j}$. If the variable $x_{i}$ is satisfied by $\pi$, then
the literal $\lambda^{j}_{\ell}$ is not satisfied which implies that the
literal vertex is adjacent to the selected subset vertex of this clause
gadget. Moreover, vertex $t^{j}_{\ell}$ is adjacent to $v_{i}$ and thus, to
three selected vertices which is a valid number.

We conclude the proof by observing that every vertex has either one or three
selected neighbors and thus, we constructed a valid solution.

As a next step we prove the reverse direction of the correctness.

######  Claim 19.

If $(G_{\varphi},2m+2n)$ is a yes-instance of AllOff, then $\varphi$ is a yes-
instance of $k$-SAT.

Consider a solution $S$ to the AllOff instance of size at most $2m+2n$. Recall
that every vertex of $G_{\varphi}$ is adjacent to an odd number of vertices in
$S$.

We first start with some observations about the solution $S$. In each variable
gadget $V_{i}$, vertex $\overline{v}_{i}$ must have a selected neighbor in $S$
(which is either $w_{i}$ or $\overline{w}_{i}$), and this selected neighbor
itself requires a selected neighbor in $S$ (which is either $v_{i}$ or
$\overline{v}_{i}$). Hence, at least two vertices must be selected from each
variable gadget.

In each clause gadget $D^{j}$, the vertex $s^{j}_{\varnothing}$ must have a
selected neighbor which forces its only neighbor, which is vertex $h^{j}$, to
be selected. As this vertex also needs a selected neighbor, one of the subset
vertices of this clause gadget must be selected as well. From the given bound
on the solution size, we conclude that in every variable gadget and every
clause gadget exactly two vertices are selected. Moreover, from each clause
gadget $D^{j}$ exactly one subset vertex, and vertex $h^{j}$ are selected.

We define the assignment $\pi$ for the variables of $\varphi$ such that
$\pi(x_{i})=1$ if and only if $v_{i}\in S$ and $\pi(x_{i})=0$ otherwise.

It remains to show that $\pi$ satisfies $\varphi$. To prove this, consider an
arbitrary clause $C^{j}$. Let $s^{j}_{L}$ be the selected subset vertex from
the clause gadget $D^{j}$. As $L\neq\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$ by the
construction of $G_{\varphi}$, there is some literal vertex $t^{j}_{\ell}$
such that $\ell\notin L$. If the corresponding literal is positive, i.e., if
$\lambda^{j}_{\ell}=x_{i}$, then $t^{j}_{\ell}$ is not adjacent to $h^{j}$. As
$t^{j}_{\ell}$ must have one selected neighbor in $S$ and since the vertex is
not adjacent to any selected subset vertex, the only remaining neighbor of
$t^{j}_{\ell}$, i.e., vertex $v_{i}$, must be selected which implies that
$\pi$ was defined such that $\pi(x_{i})=1$.

If the literal is negative, i.e., if $\lambda^{j}_{\ell}=\lnot x_{i}$, then
the vertex $t^{j}_{\ell}$ is adjacent to $h^{j}$ by the construction of
$G_{\varphi}$. Since $h^{j}$ is selected, vertex $t^{j}_{\ell}$ cannot have
further selected neighbors as all other adjacent subset vertices are
unselected. Hence, the vertex $v_{i}$ is also unselected which implies that,
by the definition of $\pi$, the variable $x_{i}$ is not satisfied but the
literal $\lambda^{j}_{\ell}$ is satisfied which makes the clause $C^{j}$ true.

As a last step we prove a bound on the pathwidth of the constructed graph.

######  Claim 20.

$G_{\varphi}$ has pathwidth at most $n+k+1$.

Intuitively the idea is as follows. If we delete all the variable vertices
$v_{i}$ for all $i\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ in the variable gadgets,
the graph decomposes into small components. We use this to construct a path
decomposition in the following by providing a node search strategy (see e.g.
[CFK+15, Section 7.5]).

We start by placing one searcher on each vertex $v_{i}$ for every
$i\in\bm{[}\,1\,\bm{.\,.}\,k\,\bm{]}$. Each of the variable gadget can be
cleaned by using $3$ additional searchers which we just place on all vertices.

For the clause gadgets we use a more complex approach to clean all vertices.
Fix a clause gadget $D^{j}$ for this. We first place $k$ new searchers on the
$k$ literal vertices of the gadget and one more searcher on the vertex
$h^{j}$. The remaining subset vertices can then be cleaned by using one
additional searcher which we put one subset vertex after the other. Repeating
this procedure for all clause gadgets cleans the entire graph.

This approach uses at most $n+k+2$ searchers simultaneously. Thus, the claimed
bound on the pathwidth follows immediately.

Recall that we fixed some $\varepsilon>0$ and chose $k$ as the smallest
integer such that $k$-SAT has no
$(2-\varepsilon)^{n}\cdot(n+m)^{\mathcal{O}(1)}$ algorithm under SETH where
$n$ is the number of variables and $m$ the number of clauses. For a given
$k$-SAT instance $\varphi$ with $n$ variables and $m$ clauses we constructed
an equivalent AllOff instance $(G_{\varphi},2n+2m)$ together with a path
decomposition.

For the sake of a contradiction, now assume that AllOff can be solved in time
$(2-\varepsilon)^{\textup{{pw}}}\cdot N^{\mathcal{O}(1)}$ on graphs of size
$N$. If we apply this algorithm to the constructed instance, we also solve, by
18, 19, and 20 the $k$-SAT instance in time

$(2-\varepsilon)^{\textup{{pw}}}\cdot
N^{\mathcal{O}(1)}=(2-\varepsilon)^{n+k+1}\cdot(n+m)^{\mathcal{O}(1)}=(2-\varepsilon)^{n}\cdot(n+m)^{\mathcal{O}(1)}$

as $k$ depends only on the fixed value $\varepsilon$ and thus, only
contributes a constant to the running time. This then directly contradicts
SETH and finishes the proof.

######  Proof 7.5.

Follows from Theorems 7.1 and 7.3.

## References

  * [ABF+02] Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier.  Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs.  Algorithmica, 33(4):461–493, 2002.  doi:10.1007/S00453-001-0116-5.
  * [AF98] Marlow Anderson and Todd Feil.  Turning lights out with linear algebra.  Mathematics Magazine, 71(4):300–303, 1998.
  * [BBH21] Abraham Berman, Franziska Borer, and Norbert Hungerbühler.  Lights out on graphs.  Mathematische Semesterberichte, 68(2):237–255, 2021.  doi:10.1007/s00591-021-00297-5.
  * [BL16] Glencora Borradaile and Hung Le.  Optimal dynamic program for r-domination problems over tree decompositions.  In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 8:1–8:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPICS.IPEC.2016.8.
  * [BMOR18] Michael A. Bennett, Greg Martin, Kevin O’Bryant, and Andrew Rechnitzer.  Explicit bounds for primes in arithmetic progressions.  Illinois J. Math., 62(1-4):427–532, 2018.  doi:10.1215/ijm/1552442669.
  * [BTV13] Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle.  Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems.  Theor. Comput. Sci., 511:66–76, 2013.  doi:10.1016/J.TCS.2013.01.009.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [Cha10] Mathieu Chapelle.  Parameterized complexity of generalized domination problems on bounded tree-width graphs.  CoRR, abs/1004.2642, 2010.  arXiv:1004.2642v5, doi:10.48550/arxiv.1004.2642.
  * [Cha11] Mathieu Chapelle.  Décompositions de graphes : quelques limites et obstructions. (Graphs decompositions: some limites and obstructions).  PhD thesis, University of Orléans, France, 2011.
  * [CHKS07] Robert Cowen, Stephen H. Hechler, John W. Kennedy, and Arthur Steinberg.  Odd neighborhood transversals on grid graphs.  Discrete Mathematics, 307(17-18):2200–2208, 2007.  doi:10.1016/j.disc.2006.11.006.
  * [CIP09] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi.  The complexity of satisfiability of small depth circuits.  In IWPEC, volume 5917 of LNCS, pages 75–85, 2009.
  * [CJ03] Yair Caro and Michael S. Jacobson.  On non-z(mod k) dominating sets.  Discussiones Mathematicae Graph Theory, 23(1):189–199, 2003.
  * [CK03] Yair Caro and William F. Klostermeyer.  The odd domination number of a graph.  Journal of Combinatorial Mathematics and Combinatorial Computing, 44:65–84, 2003.
  * [CKG01] Yair Caro, William F. Klostermeyer, and John L. Goldwasser.  Odd and residue domination numbers of a graph.  Discussiones Mathematicae Graph Theory, 21(1):119–136, 2001.  doi:10.7151/dmgt.1137.
  * [CM16] Radu Curticapean and Dániel Marx.  Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1650–1669. SIAM, 2016.  doi:10.1137/1.9781611974331.CH113.
  * [Cou90] Bruno Courcelle.  The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.  doi:10.1016/0890-5401(90)90043-H.
  * [FGK+09] Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Dieter Kratsch, and Mathieu Liedloff.  Sort and search: Exact algorithms for generalized domination.  Inf. Process. Lett., 109(14):795–798, 2009.  doi:10.1016/J.IPL.2009.03.023.
  * [FLPS16] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Efficient computation of representative families with applications in parameterized and exact algorithms.  J. ACM, 63(4):29:1–29:60, 2016.  doi:10.1145/2886094.
  * [FMI+23a] Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, and Philip Wellnitz.  Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3664–3683. SIAM, 2023.  doi:10.1137/1.9781611977554.CH140.
  * [FMI+23b] Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, and Philip Wellnitz.  Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs Part I: Algorithmic results, June 2023.  arXiv:2211.04278, doi:10.48550/arxiv.2211.04278.
  * [FMI+23c] Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, and Philip Wellnitz.  Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs Part II: Hardness results, May 2023.  arXiv:2306.03640, doi:10.48550/arXiv.2306.03640.
  * [FY13] Rudolf Fleischer and Jiajin Yu.  A survey of the game ”lights out!”.  In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066 of Lecture Notes in Computer Science, pages 176–198. Springer, 2013.  doi:10.1007/978-3-642-40273-9_13.
  * [GH08] Elisabeth Gassner and Johannes Hatzl.  A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs.  Computing, 82(2-3):171–187, July 2008.  doi:10.1007/s00607-008-0005-8.
  * [GK07] John L. Goldwasser and William F. Klostermeyer.  Odd and even dominating sets with open neighborhoods.  Ars Combinatoria, 83:229–247, 2007.
  * [GKT97] John L. Goldwasser, William Klostermeyer, and George Trapp.  Characterizing switch-setting problems.  Linear and Multilinear Algebra, 43:121–135, 1997.
  * [GKTZ95] John Goldwasser, William Klostermeyer, George Trapp, and Cun-Quan Zhang.  Setting switches in a grid.  Technical Report TR-95-20, West Virginia University, Dept. of Statistics and Computer, 1995.
  * [GP13] Alexander Giffen and Darren B. Parker.  On generalizing the ”Lights Out” game and a generalization of parity domination.  Ars Comb., 111:273–288, 2013.
  * [HKT00a] Magnús M. Halldórsson, Jan Kratochvíl, and Jan Arne Telle.  Independent sets with domination constraints.  Discret. Appl. Math., 99(1-3):39–54, 2000.  doi:10.1016/S0166-218X(99)00124-9.
  * [HKT00b] Magnús M. Halldórsson, Jan Kratochvíl, and Jan Arne Telle.  Mod-2 independence and domination in graphs.  Int. J. Found. Comput. Sci., 11(3):355–363, 2000.  doi:10.1142/S0129054100000272.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the Complexity of k-SAT.  J. Comput. Syst. Sci., 62(2):367–375, 2001.  doi:10.1006/jcss.2000.1727.
  * [KW20] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.  doi:10.1145/3390887.
  * [Lam20] Michael Lampis.  Finer tight bounds for coloring on clique-width.  SIAM J. Discret. Math., 34(3):1538–1558, 2020.  doi:10.1137/19M1280326.
  * [LMS18] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Known algorithms on graphs of bounded treewidth are probably optimal.  ACM Transactions on Algorithms, 14(2):13:1–13:30, April 2018.  doi:10.1145/3170442.
  * [Min12] Igor Minevich.  Symmetric matrices over f_2 and the lights out problem.  CoRR, abs/1206.2973, 2012.  arXiv:1206.2973, doi:10.48550/arxiv.1206.2973.
  * [MSS21] Dániel Marx, Govind S. Sankar, and Philipp Schepper.  Degrees and gaps: Tight complexity results of general factor problems parameterized by treewidth and cutwidth.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 95:1–95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPICS.ICALP.2021.95.
  * [MSS22] Dániel Marx, Govind S. Sankar, and Philipp Schepper.  Anti-factor is FPT parameterized by treewidth and list size (but counting is hard).  In Holger Dell and Jesper Nederlof, editors, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany, volume 249 of LIPIcs, pages 22:1–22:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPICS.IPEC.2022.22.
  * [Sut88] Klaus Sutner.  Additive automata on graphs.  Complex Systems, 2(6):649–661, 1988.
  * [Sut89] Klaus Sutner.  Linear cellular automata and the garden-of-eden.  The Mathematical Intelligencer, 11(2):49–53, 1989.  doi:10.1007/BF03023823.
  * [SZ14] Hadas Shachnai and Meirav Zehavi.  Representative families: A unified tradeoff-based approach.  In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 786–797. Springer, 2014.  doi:10.1007/978-3-662-44777-2_65.
  * [Tel94] Jan Arne Telle.  Complexity of domination-type problems in graphs.  Nord. J. Comput., 1(1):157–171, 1994.
  * [vR20] Johan M. M. van Rooij.  Fast algorithms for join operations on tree decompositions.  In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 262–297. Springer, 2020.  doi:10.1007/978-3-030-42071-0_18.
  * [vRBR09] Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith.  Dynamic programming on tree decompositions using generalised fast subset convolution.  In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566–577. Springer, 2009.  doi:10.1007/978-3-642-04128-0_51.