and $g(n-1,n-1)\coloneqq-(n-2)$.

We lift this function $g$ to all inputs of $G_{i}^{j}$ as seen above by
imposing that the edges going to $J_{i}^{j}$ are selected monotonically. But
now the top/first $\ell$ edges are selected and the bottom $n-1-\ell$ edges
are not selected for some $\ell\in[n]$. Note, that this is the converse of the
edges $\texttt{in}_{\ell}$ of $F_{i}^{j}$.

###### Construction of the Gadgets.

It remains to define the gadgets $G_{i}^{j}$. Their construction can be
divided into four stages as shown in Figure 4. We informally describe the
purpose of the stages and then formally define the relations. For this we
refer to the edges as left, top, bottom, and right edges and abbreviate them
by $\ell,t,b,r$. If there are more than one edge on one side, we enumerate
them from left to right, or from top to bottom.

  1. 1.

Check whether the ingoing edges are selected monotonically starting from the
top. While doing this, select the $\ell$th edge going to the next stage if and
only if the first $\ell-1$ edges are selected. The vertical edges encode
whether all ingoing edges of the blocks above have been selected.

We formally define $M=\\{\ell tb,tr,\emptyset\\}$.

  2. 2.

This stage assigns the different weights to the solutions depending on the
number of selected ingoing and outgoing edges. By the first and last stage
(monotonicity gadgets), this information is encoded by the position of the
selected edge from the first and to the third stage. The first and second
vertical edge encodes whether $n-1$ ingoing edges and $n-1$ outgoing edges are
selected, respectively.

We define $R_{0}=\\{\ell r,\ell
t_{2}b_{2},t_{1}b_{1}r,\emptyset,t_{1}b_{1},t_{2}b_{2},t_{1}t_{2}b_{1}b_{2}\\}$.
The input $\ell r$ of $R_{0}$ is assigned weight $-1$ and all other accepted
inputs are assigned weight $1$. $R_{W}$ completely agrees with $R_{0}$ except
that the input $t_{1}t_{2}b_{1}b_{2}$ is assigned weight $-(n-2)$.

  3. 3.

If the $\ell$th edge from the bottom is selected, then this corresponds to
element $x_{\ell}$ being selected for $X_{i}$. We propagate this information
to the next stage. If $x_{\ell}$ is contained in $A_{j}$, then we assign
relation $C^{+}$ to the $\ell$th block from the bottom and otherwise the
relation $C^{0}$. The vertical edges are selected, if the set has been hit by
any element (possibly also by some element from a $X_{i^{\prime}}$ with
$i^{\prime}<i$).

We define $C^{0}=\\{\emptyset,\ell r,tb,\ell tbr\\}$ and
$C^{+}=C^{0}\cup\\{\ell br\\}$.

  4. 4.

This stage is a rotated version of the first stage. That is, if the $\ell$th
edge from the bottom is selected, then we select $\ell-1$ outgoing edges. The
vertical edges now correspond to the fact whether all outgoing edges from
below have been selected.

We define $M^{\prime}=\\{tbr,\ell b,\emptyset\\}$.

Figure 4:  The gadget $G_{i}^{j}$ checks whether the element from $X_{i}$ hits
the set $A_{j}$ (here $x_{3},x_{4},x_{6}$ hit $A_{j}$ and the other elements
not). It additionally ensures together with $J_{i}^{j}$ that the information
about this selected element is consistent in the whole graph. The different
stages are separated by dashed lines.

######  Claim 2.

The pathwidth of the graph is $k+\mathcal{O}(1)$.

We use a mixed search strategy to clean the graph from left to right. For this
we place searchers on the vertices $J_{1}^{j}$ for all $j$ and clean the
monotonicity gadgets going from top to bottom.

The remaining graph is cleaned in $m$ rounds. For the $j$th round we clean the
gadgets $G_{i}^{j}$ from top to bottom. Before cleaning each $G_{i}^{j}$ we
place one searcher on the simple vertex on $J_{i}^{j+1}$ and afterward we
remove the searcher from $J_{i}^{j-1}$. Then we continue with the next row
until all $G_{i}^{j}$ are cleaned and we proceed to the $j+1$th round. For the
correctness of the final construction it suffices to show that the gadget
$G_{i}^{j}$ together with vertex $J_{i}^{j}$ satisfy all properties of
$F_{i}^{j}$. For this we first observe that the fourth stage of $G_{i}^{j}$
ensures property (1) of $F_{i}^{j}$. The third stage ensures the third
property and the first and second stage together with $J_{i}^{j}$ ensure
property (2) by the choice of the weights.

###  7.3 Replacing the Relations

In this section, we prove Lemma 7.2, i.e. the reduction from
#${Y}$-AntiFactorR to #$({X},{Y})$-AntiFactor, by a chain of reductions (cf.
Figure 5). Like in [32], we make use of the Holant framework. The first step
uses Lemmas 7.5 and 7.6 from [32]. The only observation is that the lemmas
work for #$B$-Factor even when $B$ is co-finite, that is
#$\overline{B}$-AntiFactor because the simple nodes in the instance are not
changed in any way.

#${X}$-AntiFactorR
---
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})$
---
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},w{[1,1]},w{[-1,1]},w{[0,1]})$
---
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}})$
---
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},w{[-1,1]},w{[0,1]})$
---
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},w{[0,1]})$
---
Lemma 7.21 (3 cases)
---
Lemma 7.30
---
Lemma 7.20
---
Figure 5: Chain of reductions that start with using relations and ends in
#${X}$-AntiFactor.

######  Lemma 7.20 (Lemma 7.5 and 7.6 in [32]).

There is a polynomial-time Turing reduction from #${X}$-AntiFactorR to
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})$
such that the maximum degree increases to at least 6 and the pathwidth
increases by at most a constant depending only on $\Delta^{\\!*}$, i.e. the
maximum total degree of the complex nodes in any bag of the path
decomposition.

Observe that Lemma 7.5 in [32] requires that the relation is even, i.e. the
Hamming weight of every accepted input is even. But we can easily make every
relation even by adding an additional input that is selected whenever the
parity of the original input is odd. This additional input is then connected
to a $\mathtt{EQ}_{1}$ node, which can easily be realized by forcing
$\max{X}+1$ edges to a fresh vertex using $\mathtt{HW}_{=1}^{(1)}$ nodes. For
the next step in the chain, we consider three separate cases depending on
${X}$. For these steps, we define a new kind of node. We define a $w{[x,y]}$
as a node with one dangling edge $e$ having the following function.

$f(e)=\begin{cases}y&\text{ if $e$ is selected}\\\ x&\text{ if $e$ is not
selected}.\end{cases}$

Observe that a $\mathtt{HW}_{=1}^{(1)}$ node is precisely a $w{[0,1]}$ node
and a $\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ node corresponds to a $w{[1,1]}$
node. In the following constructions we additionally use a $w{[-1,1]}$ node.
We use the $w{[x,y]}$ notation in the following wherever possible.

######  Lemma 7.21.

Let ${X}\subseteq{\mathbb{N}}$ be a finite set such that
${X}\not\subseteq\\{0\\}$. Let $R_{1},\dots,R_{d}$ be $d$ arbitrary relations
for some $d\geq 0$. There is a polynomial-time Turing reduction from

$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})\text{
to
}\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},w{[1,1]},w{[-1,1]},w{[0,1]})$

such that $\Delta^{\\!*}$ increases to $\Delta^{\\!*}f(\max{X})$ and
${\operatorname{pw}}$ increases to
${\operatorname{pw}}+\Delta^{\\!*}f(\max{X})$.

We can distinguish the following cases depending on the structure of ${X}$:

  1. 1.

$\operatorname{max-gap}({\overline{{X}}})>1$:

    1. (a)

${X}\neq[k]$ for some $k\geq 2$

    2. (b)

${X}=[k]$ for some $k\geq 2$

  2. 2.

$\operatorname{max-gap}({\overline{{X}}})=1$: In this case, ${X}$ contains no
two consecutive numbers but contains at least one positive integer.

  3. 3.

$\operatorname{max-gap}({\overline{{X}}})=0$: By assumption ${X}=[0,k]$ for
some $k\geq 1$

Note that the uncovered case ${X}=\\{0\\}$ corresponds to the edge-cover
problem. In this case, our techniques to realize relations fail. However, we
show the tight lower bound via another reduction in Section 8.

We group cases 1b and 3 together such that we are left with three separate
proofs.

######  Lemma 7.22 (Case 1a of Lemma 7.21).

Let ${X}\subseteq{\mathbb{N}}$ be a finite set such that $\operatorname{max-
gap}({\overline{{X}}})>1$ and ${X}\neq[k]$ for some $k\geq 2$. Let
$R_{1},\dots,R_{d}$ be $d$ arbitrary relations for some $d\geq 0$. There is a
polynomial-time many-one reduction from

$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})\text{
to
}\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},w{[1,1]},w{[0,1]})$

such that $\Delta^{\\!*}$ increases to $\Delta^{\\!*}f(\max{X})$ and
${\operatorname{pw}}$ increases to
${\operatorname{pw}}+\Delta^{\\!*}f(\max{X})$.

######  Proof 7.23.

Since $\operatorname{max-gap}({\overline{{X}}})>1$, there are $a\geq 0,d>1$
such that $[a,a+d+1]\cap{X}=[a+1,a+d]$. We now show how to get
$\mathtt{HW}_{=1}^{(2)}$ and $\mathtt{HW}_{=1}^{(3)}$ nodes. This is enough to
get $\mathtt{HW}_{=1}^{(\ell)}$ nodes for arbitrary $\ell$ by using the
construction from Lemma 5.15 (cf. Lemma 5.5 from [32] for more details).

We follow the process from Lemma 5.8 from [32] to first get a
$\mathtt{EQ}_{3}$ node. We first construct a $\mathtt{EQ}_{d+1}$ node by
forcing $a$ edges to a new vertex using $w{[0,1]}$ nodes. Adding $d-2$ many
$w{[1,1]}$ nodes to this $\mathtt{EQ}_{d+1}$ node gives us a $\mathtt{EQ}_{3}$
node.

We first construct a $\mathtt{HW}_{=1}^{(2)}$ node. Since $\operatorname{max-
gap}({\overline{{X}}})>1$ and ${X}\neq[k]$, there are
$a^{\prime}>0,d^{\prime}>0$ such that
$[a^{\prime},a^{\prime}+d^{\prime}+1]\cap{X}=[a^{\prime}+1,a^{\prime}+d^{\prime}]$.
Take two $\mathtt{EQ}_{3}$ nodes and set one edge of each of them as a
dangling edge. Using the remaining two edges, connect each of them to two
vertices $u,v$. Attach $a^{\prime}-1$ $w{[0,1]}$ nodes to $u$ and $\max{X}$
$w{[0,1]}$ nodes to $v$. Observe that by virtue of $u$, at most one
$\mathtt{EQ}_{3}$ node can have its edges selected and by virtue of $v$, at
least one $\mathtt{EQ}_{3}$ node must have its edges selected. Thus, exactly
one dangling edge must be selected in any solution.

To get a $\mathtt{HW}_{=1}^{(3)}$ node we distinguish two cases. If
$d^{\prime}\geq 2$ or $a\geq 1,d\geq 2$, we can use the same approach as for
the $\mathtt{HW}_{=1}^{(2)}$ node but using three $\mathtt{EQ}_{3}$ nodes
instead. For the case $a=0$ and $d^{\prime}=1$, this construction is not
sufficient. Then we force $d-1$ edges to a new vertex and add three
$\mathtt{HW}_{=1}^{(2)}$ nodes where the remaining edges are dangling edges.
If $d+2\in{X}$, then we get a $\mathtt{HW}_{=1}^{(3)}$ gadget and we are done.
Otherwise we have a $\mathtt{HW}_{\in\\{0,1\\}}^{(3)}$ gadget. Then we can use
the construction for the $\mathtt{HW}_{=1}^{(2)}$ gadget with three
$\mathtt{EQ}_{3}$ nodes and replace the vertex $u$ by this gadget.

######  Lemma 7.24 (Case 2 of Lemma 7.21).

Let ${X}\subseteq{\mathbb{N}}$ be a finite set such that $\operatorname{max-
gap}({\overline{{X}}})=1$. Let $R_{1},\dots,R_{d}$ be $d$ arbitrary relations
for some $d\geq 0$. There is a polynomial-time many-one reduction from

$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})\text{
to
}\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},w{[1,1]},w{[-1,1]},w{[0,1]})$

such that $\Delta^{\\!*}$ increases to $\Delta^{\\!*}f(\max{X})$ and
${\operatorname{pw}}$ increases to
${\operatorname{pw}}+\Delta^{\\!*}f(\max{X})$.

######  Proof 7.25.

Let $k=\max{X}$. Then since $\operatorname{max-gap}({\overline{{X}}})=1$, we
have that $k\in{X},k-1,k+1\not\in{X}$. To a vertex $v$, attach $k-1$ many
$w{[0,1]}$ nodes and one $w{[1,1]}$ node (by a red edge). We also attach a
$w{[-1,1]}$ to $v$ (by a blue edge). Now, we add $\ell$ dangling edges to $v$.
See Figure 6 for an illustration. We claim that $v$ acts as a
$\mathtt{HW}_{=1}^{(\ell)}$ node.

Figure 6:  Construction of the gadget in Lemma 7.24 and Lemma 7.26.

After attaching the $k-1$ many $w{[0,1]}$ nodes, $v$ cannot be incident to
exactly one more edge.

  * •

Suppose no dangling edges are chosen. Then we can extend the solution by
selecting neither of the blue and red edges or selecting both of them. The
number of solutions is $1+(-1)=0$ and therefore, this is not a possibility.
101010 Technically this is a solution but contributes $0$ to the Holant and
thus can be ignored (or treated as invalid).

  * •

Suppose more than one dangling edges are chosen. Then we can pick any
combination of the red and blue edges. The number of solutions is $1-1+1-1=0$.
Like before, this is not a possibility.

  * •

Suppose exactly one dangling edge is chosen. Then we must pick at least one of
the red or blue edges. The number of solutions is $1-1+1=1$.

Thus, the only solution is to pick exactly one dangling edge.

######  Lemma 7.26 (Cases 1b and 3 of Lemma 7.21).

Let ${X}=[0,k],k\geq 1$ or ${X}=[k],k\geq 2$ for some integer $k$. Let
$R_{1},\dots,R_{d}$ be $d$ arbitrary relations for some $d\geq 0$. There is a
polynomial-time Turing reduction from

$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})\text{
to
}\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},w{[1,1]},w{[-1,1]},w{[0,1]})$

such that $\Delta^{\\!*}$ increases to $\Delta^{\\!*}f(\max{X})$ and
${\operatorname{pw}}$ increases to
${\operatorname{pw}}+\Delta^{\\!*}f(\max{X})$.

######  Proof 7.27.

We first reduce from
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})$ to
$\operatorname{Holant}(\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{\in\\{0,1\\}})$
using Lemma 7.8 from [32].

Then the construction is the same as for the reduction in Lemma 7.24. Then we
show how to get $\mathtt{HW}_{\in\\{0,1\\}}^{(\ell)}$ nodes. See Figure 6 for
the construction. To a vertex $v$, attach $k-1$ many $w{[0,1]}$ nodes, one
$w{[1,1]}$ node (by a red edge), and one $w{[-1,1]}$ node (by a blue edge).
Now, we add $\ell$ dangling edges to $v$.

We claim that $v$ acts as a $\mathtt{HW}_{\in\\{0,1\\}}^{(\ell)}$ node. Note
that after attaching the $k-1$ many $w{[0,1]}$ nodes, $v$ can have any degree
except for 0 or 1.

  * •

Suppose more than one dangling edges are chosen. Then we can pick any
combination of the red and blue edges. The number of solutions is $1-1+1-1=0$.
Therefore, this is not a possibility.

  * •

Suppose no dangling edges are chosen. Then we can extend the solution only by
selecting both of the blue and red dangling edges. The number of solutions is
$1$.

  * •

Suppose exactly one dangling edge is chosen. Then we must pick at least one of
the red or blue dangling edges. The number of solutions is $1-1+1=1$.

Thus, the only solution is to pick exactly one or zero dangling edges.

Next we show that we can realize $w{[x,y]}$ node. In particular, we can get
the $w{[1,1]}$, $w{[-1,1]}$, and $w{[0,1]}$ needed in Lemma 7.21.

######  Lemma 7.28.

Let ${X}\subseteq{\mathbb{N}}$ be a fixed, finite set with
${X}\not\subseteq\\{0\\}$. Let $R_{1},\dots,R_{d}$ be $d$ arbitrary relations
for some $d\geq 0$. The following holds for arbitrary values $x,y$. There is a
polynomial-time Turing reduction from
$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},w{[x,y]})$
to
$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}})$
such that $\Delta^{\\!*}$ decreases and ${\operatorname{pw}}$ increases to
${\operatorname{pw}}+\Delta^{\\!*}f(\max{X})$.

######  Proof 7.29.

We use Lemma 7.11 from [32] as our prototype. However, some arguments from
their proof do not follow in our case.

Let $U$ be the set of $w{[x,y]}$ nodes in the given graph $G$. We know that

$\operatorname{Holant}(G)=\sum_{i=0}^{\lvert U\rvert}A_{i}x^{i}y^{\lvert
U\rvert-i}$

where $A_{i}$ denotes the number of possible extension if for exactly $i$ of
the $w{[x,y]}$ nodes the dangling edge is not selected and for the other
$\lvert U\rvert-i$ nodes the dangling edge is selected.

We construct a new graphs $H_{d}$ for a new parameter $d$ where we replace all
$w{[x,y]}$ nodes by a gadget $G_{d}$ depending on $d$ with exactly one
dangling edge. The construction of $G_{d}$ is described in the following as it
depends on ${X}$. Then we get

$\operatorname{Holant}(H_{d})=\sum_{i=0}^{\lvert
U\rvert}A_{i}P_{0}(d)^{i}P_{1}(d)^{\lvert U\rvert-i}=P_{1}(d)^{\lvert
U\rvert}\sum_{i=0}^{\lvert
U\rvert}A_{i}{\mathopen{}\left(\frac{P_{0}(d)}{P_{1}(d)}\right)\mathclose{}}^{\\!\\!i}$

where $P_{0}(d)$ denotes the number of solutions for $G_{d}$ when the dangling
edge is not selected and $P_{1}(d)$ when the dangling edge is selected.

The idea is to compute $\operatorname{Holant}(H_{d})$ for different $d$ to
recover the values $A_{i}$. For this we need that $\frac{P_{0}(d)}{P_{1}(d)}$
can take more than $\lvert U\rvert$ different values according to $d$. Then we
can easily compute the value of $\operatorname{Holant}(G)$.

In the remainder of the proof we show how to obtain these gadgets $G_{d}$.

##### Case 1: $0\in{X}$ or $1\not\in{X}$

We first show how to get a $\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ node.

  * •

If $0,1\not\in{X}$, then any vertex with a dangling edge acts as a
$\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ node.

  * •

If $0\in{X},1\not\in{X}$, then attach $\max{X}+1$ pendant vertices to any
vertex $v$. Then $v$ acts as a $\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ node.

  * •

If $0\in{X},1\in{X}$, then take a clique of size $\min({\overline{{X}}})+1$.
Split the edge between two vertices into two dangling edges. This now acts as
a $\mathtt{HW}_{=2}^{(2)}$ node. Attaching $\lceil\frac{\max{X}+1}{2}\rceil$
many $\mathtt{HW}_{=2}^{(2)}$ nodes to a new vertex with one dangling edge
gives us a $\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ node.

Figure 7: Gadget to realize $w{[x,y]}$ nodes in Case 1. Red nodes are
$\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ nodes.

$G_{d}$ consists of a path of $d$ vertices with a dangling edge on the first
vertex. For an integer $z\geq\max{X}+1$ that we will choose later, attach $z$
pendant $\mathtt{HW}_{\in\\{0,1\\}}^{(1)}$ nodes to each vertex in the path.
See Figure 7 for an illustration. Define the following quantities.

$\displaystyle F_{0}=\sum_{i\mathrel{\mathop{\mathchar
58\relax}}i\in{\overline{{X}}}}\binom{z}{i},\qquad
F_{1}=\sum_{i\mathrel{\mathop{\mathchar 58\relax}}i\geq
0,i+1\in{\overline{{X}}}}\binom{z}{i},\qquad
F_{2}=\sum_{i\mathrel{\mathop{\mathchar 58\relax}}i\geq
0,i+2\in{\overline{{X}}}}\binom{z}{i}.$

Then we have the following relations.

$\displaystyle P_{0}(d)$ $\displaystyle=F_{0}P_{0}(d-1)+F_{1}P_{1}(d-1)$
$\displaystyle P_{0}(1)$ $\displaystyle=F_{0}$ $\displaystyle P_{1}(d)$
$\displaystyle=F_{1}P_{0}(d-1)+F_{2}P_{1}(d-1)$ $\displaystyle P_{1}(1)$
$\displaystyle=F_{1}$

To do the interpolation we need to show that the sequence
$\\{\frac{P_{0}(d)}{P_{1}(d)}\\}_{d}$ does not contain any repetitions. By
Proposition 7.7 in [32] and the recursive definition of $P_{0}$ and $P_{1}$ it
suffices to show that the matrix $M=\bigl{[}\begin{smallmatrix}F_{0}&F_{1}\\\
F_{1}&F_{2}\end{smallmatrix}\bigr{]}$ is invertible and that
$U=\bigl{[}\begin{smallmatrix}F_{0}\\\ F_{1}\end{smallmatrix}\bigr{]}$ is not
an eigenvector of $M$. We claim that it suffices to show that

$F_{0}F_{2}\neq(F_{1})^{2}.$ (1)

Then $M$ is clearly invertible. Assume for contradiction sake that $U$ is an
eigenvector of $M$. Then there is some $\lambda\neq 0$ such that
$(F_{0})^{2}+(F_{1})^{2}=\lambda F_{0}$ and $F_{1}(F_{0}+F_{2})=\lambda
F_{1}$. This implies
$F_{1}(F_{0})^{2}+(F_{1})^{3}=F_{1}(F_{0})^{2}+F_{0}F_{1}F_{2}$ which is a
contradiction when $F_{1}\neq 0$ (which is true when ${X}\neq\\{0\\}$) because
of inequality (1).

We claim that there is a $z$ such that inequality (1) holds. Suppose not. We
will show a contradiction. We first expand the equations above. Then for every
$z$,

$\displaystyle\mathopen{}\left(\sum_{i\in{\overline{{X}}}}\binom{z}{i}\right)\mathclose{}\mathopen{}\left(\sum_{i+2\in{\overline{{X}}}}\binom{z}{i}\right)\mathclose{}$
$\displaystyle=\Bigg{(}\sum_{i+1\in{\overline{{X}}}}\binom{z}{i}\Bigg{)}^{2}$
$\displaystyle\mathopen{}\left(2^{z}-\sum_{i\in{X}}\binom{z}{i}\right)\mathclose{}\mathopen{}\left(2^{z}-\sum_{i+2\in{X}}\binom{z}{i}\right)\mathclose{}$
$\displaystyle=\Bigg{(}2^{z}-\sum_{i+1\in{X}}\binom{z}{i}\Bigg{)}^{2}$

which implies $2^{z}Q_{1}(z)=Q_{2}(z)$, where

$\displaystyle Q_{1}(z)$
$\displaystyle=\mathopen{}\left(2\sum_{i+1\in{X}}\binom{z}{i}-\sum_{i\in{X}}\binom{z}{i}-\sum_{i+2\in{X}}\binom{z}{i}\right)\mathclose{}$
$\displaystyle Q_{2}(z)$
$\displaystyle=\Bigg{(}\sum_{i+1\in{X}}\binom{z}{i}\Bigg{)}^{2}-\mathopen{}\left(\sum_{i\in{X}}\binom{z}{i}\right)\mathclose{}\mathopen{}\left(\sum_{i+2\in{X}}\binom{z}{i}\right)\mathclose{}.$

For large enough $z$, we argue that $Q_{1}(z)$ is not identically zero.
Observe that the second term in $Q_{1}(z)$ gives a non-zero $z^{\max{X}}$
monomial whereas the other two terms cannot give a monomial of this degree.
Now, since ${X}$ is a fixed, finite set, $Q_{1},Q_{2}$ are polynomials with
constant degree. Thus, $Q_{1}(z)$ is zero only for finitely many $z$ and thus,
there are infinitely many (positive) $z$ such that $Q_{1}(z)$ is non-zero. For
each such $z$ we have

$\displaystyle\lvert 2^{z}Q_{1}(z)\rvert$ $\displaystyle=\lvert
Q_{2}(z)\rvert.$

This is immediately a contradiction since $2^{z}=\omega(z^{c})$ for any
constant $c$ if $z$ is large enough. Thus, there is some positive integral
value of $z$ such that $F_{0}F_{2}\neq(F_{1})^{2}$. We use this value of $z$
in the construction of the gadget. Note that $z$ only depends on ${X}$ and can
thus be precomputed.

##### Case 2: $0\not\in{X},1\in{X}$.

In this case, we first get a $\mathtt{EQ}_{2}$ node in the following way. Let
$m$ be the minimum non-zero element in ${\overline{{X}}}$. We create a clique
of size $m+1$ and split one edge into two dangling edges.

Figure 8: Gadget to realize $w{[x,y]}$ nodes in Case 2. Red nodes are
$\mathtt{EQ}_{2}$ nodes.

For $G_{d}$, we create a path of length $d$ and add a dangling edge to the
first vertex. To each vertex in the path, attach $z$ $\mathtt{EQ}_{2}$ nodes
via both of its dangling edges, where $z$ is chosen later such that
$2z\geq\max{X}+1$ See Figure 8 for an illustration. Define the following
quantities.

$\displaystyle F_{0}=\sum_{i\mathrel{\mathop{\mathchar 58\relax}}i\geq
0,2i\in{\overline{{X}}}}\binom{z}{i},\qquad
F_{1}=\sum_{i\mathrel{\mathop{\mathchar 58\relax}}i\geq
0,2i+1\in{\overline{{X}}}}\binom{z}{i},\qquad
F_{2}=\sum_{i\mathrel{\mathop{\mathchar 58\relax}}i\geq
0,2i+2\in{\overline{{X}}}}\binom{z}{i}.$

Then we again have the following relations.

$\displaystyle P_{0}(d)$ $\displaystyle=F_{0}P_{0}(d-1)+F_{1}P_{1}(d-1)$
$\displaystyle P_{0}(1)$ $\displaystyle=F_{0}$ $\displaystyle P_{1}(d)$
$\displaystyle=F_{1}P_{0}(d-1)+F_{2}P_{1}(d-1)$ $\displaystyle P_{1}(1)$
$\displaystyle=F_{1}$

Using the same arguments as for the first case above, based on Proposition 7.7
in [32], it suffices to show that there is some $z$ such that the following
inequality holds, to be able to do the interpolation:

$F_{0}F_{2}\neq(F_{1})^{2}.$ (2)

Suppose there is no such $z$. Then for every $z$,

$\displaystyle\mathopen{}\left(\sum_{2i\in{\overline{{X}}}}\binom{z}{i}\right)\mathclose{}\mathopen{}\left(\sum_{2i+2\in{\overline{{X}}}}\binom{z}{i}\right)\mathclose{}$
$\displaystyle=\Bigg{(}\sum_{2i+1\in{\overline{{X}}}}\binom{z}{i}\Bigg{)}^{2}$
$\displaystyle\mathopen{}\left(2^{z}-\sum_{2i\in{X}}\binom{z}{i}\right)\mathclose{}\mathopen{}\left(2^{z}-\sum_{2i+2\in{X}}\binom{z}{i}\right)\mathclose{}$
$\displaystyle=\Bigg{(}2^{z}-\sum_{2i+1\in{X}}\binom{z}{i}\Bigg{)}^{2}$

which implies $2^{z}Q_{1}(z)=Q_{2}(z)$, where

$\displaystyle Q_{1}(z)$
$\displaystyle=\mathopen{}\left(2\sum_{2i+1\in{X}}\binom{z}{i}-\sum_{2i\in{X}}\binom{z}{i}-\sum_{2i+2\in{X}}\binom{z}{i}\right)\mathclose{}$
$\displaystyle Q_{2}(z)$
$\displaystyle=\Bigg{(}\sum_{2i+1\in{X}}\binom{z}{i}\Bigg{)}^{2}-\mathopen{}\left(\sum_{2i\in{X}}\binom{z}{i}\right)\mathclose{}\mathopen{}\left(\sum_{2i+2\in{X}}\binom{z}{i}\right)\mathclose{}.$

Like before, $Q_{1}(z)$ is not identically zero for large enough $z$. The
first term of $Q_{1}(z)$ gives a constant of $2$, the second term cannot give
a constant since $0\not\in{X}$, and the third term gives a constant of $-1$ if
$2\in{X}$. Thus, $Q_{1}(z)$ has a non-zero constant term and is hence zero
only for finitely many $z$. Therefore, for infinitely many positive values of
$z$, we have

$\displaystyle\lvert 2^{z}Q_{1}(z)\rvert=\lvert Q_{2}(z)\rvert$

This is a contradiction since $2^{z}=\omega(z^{c})$ for any constant $c$ and
$Q_{1},Q_{2}$ are polynomials of constant degree. Thus, we can choose a $z$
such that $F_{0}F_{2}\neq(F_{1})^{2}$ to do the interpolation.

######  Lemma 7.30.

Let ${X}\subseteq{\mathbb{N}}$ be a fixed, finite set with
${X}\not\subseteq\\{0\\}$. Let $R_{1},\dots,R_{d}$ be $d$ arbitrary relations
for some $d\geq 0$. There is a polynomial-time Turing reduction from

$\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}},w{[1,1]},w{[-1,1]},w{[0,1]})\text{
to
}\operatorname{Holant}(R_{1},\dots,R_{d},\mathtt{HW}_{\in{\overline{{X}}}})$

such that $\Delta^{\\!*}$ decreases and ${\operatorname{pw}}$ increases to
${\operatorname{pw}}+\Delta^{\\!*}f(\max{X})$.

######  Proof 7.31.

We first use Lemma 7.28 to remove the $w{[1,1]}$ nodes. Observe that this can
alternatively be done by a simple construction using a fresh vertex and
$\max{X}+2$ forced edges. Then we apply the lemma two more times to remove the
$w{[-1,1]}$ nodes and finally the $w{[0,1]}$ nodes.

Now we can prove the reduction from #${Y}$-AntiFactorR to
#$({X},{Y})$-AntiFactor.

######  Proof 7.32 (Proof of Lemma 7.2).

By the reduction of Lemma 7.20 we can reduce #${Y}$-AntiFactorR to
$\operatorname{Holant}(\mathtt{HW}_{\in\overline{Y}},\mathtt{HW}_{=1})$. This
can trivially be reduced to
$\operatorname{Holant}(\mathtt{HW}_{\in\overline{Y}},\mathtt{HW}_{\in{\overline{{X}}}},\mathtt{HW}_{=1})$
as we do not have any nodes with relation $\mathtt{HW}_{\in{\overline{{X}}}}$.
Then we can invoke Lemmas 7.21 and 7.30 such that the nodes with relation
$\mathtt{HW}_{\in\overline{Y}}$ are always preserved and not changed (or used
for any construction). By this we end the reduction with
$\operatorname{Holant}(\mathtt{HW}_{\in\overline{Y}},\mathtt{HW}_{\in{\overline{{X}}}})$
which precisely corresponds to #$({X},{Y})$-AntiFactor.

##  8 Lower Bound for Counting Edge Covers

Observe that the constructions in the previous section do not apply for the
case of ${X}=\\{0\\}$. This case precisely corresponds to #EdgeCover which we
handle separately in this section. Due to its special structure we show a
different reduction which still leads to the expected hardness result for the
problem.

######  Theorem 8.1.

For every constant $\epsilon>0$, #EdgeCover cannot be solved in time
$(2-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$ on graphs given with a
path decomposition of width ${\operatorname{pw}}$, unless #SETH fails.

The main step to prove this lower bound is to show a lower bound for
#MaxIndSet.

######  Definition 8.2 (Counting Maximum Independent Sets (#MaxIndSet)).

Given a graph $G=(V,E)$. Let $\mathcal{I}=\\{I\subseteq
V\mid\forall\\{u,v\\}\in E\mathrel{\mathop{\mathchar 58\relax}}u\in I\lor v\in
I\\}$ and $M=\max_{I\in\mathcal{I}}\lvert I\rvert$.

Compute $\lvert\\{I\in\mathcal{I}\mid M=\lvert I\rvert\\}\rvert$.

We split the lower bound for #EdgeCover into the following steps.

  1. 1.

Lemma 8.3 reduces the counting version of SAT to a variant of SAT where we
want to count the satisfying assignments given the promise that the formula is
satisfiable.

  2. 2.

In Lemma 8.5 we show a lower bound for #MaxIndSet on low degree graphs under
#SETH.

  3. 3.

Lemma 8.7 extends the previous lower bound to regular graphs.

  4. 4.

For Theorem 8.1 we reduce #MaxIndSet on regular graphs to #EdgeCover using
ideas from [8, 9] and thus prove the lower bound.

We start with the reduction from #SAT to the variant of #SAT.

######  Lemma 8.3.

Given a SAT formula $\phi$ with $n$ variables and $m$ clauses, we can
construct in time linear in the output size a SAT formula $\psi$ on $n+1$
variables and $m+n$ clauses such that $\\#SAT(\phi)+1=\\#SAT(\psi)$.

######  Proof 8.4.

Let $x_{1},\dots,x_{n}$ be the variables of $\phi$ and $x_{0}$ be a free
variable. We define $\psi$ such that $\psi\equiv(x_{0}\lor\phi)\land(\neg
x_{0}\lor(x_{1}\land\dots\land x_{n}))$. One can easily see that the
assignment $x_{0}=x_{1}=\dots=x_{n}=\textsf{true}$ is satisfying for $\psi$.
Further, for $x_{0}=\textsf{true}$ this is the only satisfying assignment. For
$x_{0}=\textsf{false}$ the satisfying assignments of $\phi$ directly transfer
to $\psi$.

One can easily transform the right hand-side into a CNF by adding $x_{0}$ to
each clause of $\phi$ and additionally add the clauses $(\neg x_{0}\lor
x_{i})$ for all $i\in[n]$.

There is a known lower bound of
$(2-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$ for finding the Maximum
Independent set on graphs with pathwidth ${\operatorname{pw}}$ under SETH,
[28]. Observe that their reduction is not parsimonious and therefore does not
hold under #SETH. We instead show a lower bound for #MaxIndSet based on the
weaker assumption of #SETH.

######  Lemma 8.5.

For every constant $\epsilon>0$, there is a $r>0$ such that #MaxIndSet on
graphs with maximum degree $r$ cannot be solved in time
$(2-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$, even if we are given a
path decomposition of width ${\operatorname{pw}}$, unless #SETH fails.

######  Proof 8.6.

We start with a SAT instance with $n$ variables and $m$ clauses. By Lemma 8.3
we can assume that the instance is satisfiable. We build two types of gadgets.
The first type ensures that this information is transferred consistently while
the second one checks that a clause is satisfied. We bound the size of the MIS
for each part of the construction separately. The ideas for both gadgets is
that the size decreases significantly if the properties of these gadgets are
not fulfilled. Finally, we argue that the number of independent sets of this
size corresponds to the number of satisfying assignments of the formula.

*Encoding Assignments. We create multiple sets with $d$ vertices that allow us to encode the assignments for the variables depending on the subset of selected vertices. See Figure 9 for an illustration of the construction. We group $g$ variables together for some $g$ to be chosen later. Then we repeat the following procedure for all of the $t\coloneqq\lceil n/g\rceil$ many groups of variables. For every group $i\in[t]$ and every $j\in[m]$ denoting the clause, we create a consistency gadget $C_{i}^{j}$ which ensures the consistency of the encoded assignments. For each $C_{i}^{j}$ we create $d$ input vertices $v_{i,1}^{j},\dots,v_{i,d}^{j}$ where we choose $d$ later.

We encode the partial assignments to the variables of the $i$th group by
subsets of these vertices (or their indices from $[d]$). To each assignment we
assign a unique subset from $[d]$ of size exactly $d/2$. This is possible as
we set $d$ such that $\binom{d}{d/2}\geq 2^{g}$. For one $i$, we always use
the same mapping, though it can be different if the $i$ is different. For
simplicity we can assign the all zeros assignment to the remaining subsets of
$[d]$ of size exactly $d/2$. Then every subset of size $d/2$ of $d$ (and the
extension to the input vertices), encodes a partial assignment for the $i$th
group.

To ensure the assignment is consistently for all $j$, we add $d$ cliques of
size $\binom{d}{d/2}$ each to $C_{i}^{j}$. Each vertex of such a clique is
identified with a unique subset of size $d/2$ from $[d]$. We denote the vertex
for the set $S$ in the $\ell$th clique by $w_{i,S,\ell}^{j}$. Then for every
$S\subseteq[d]$ with $\lvert S\rvert=d/2$ and all $\ell\in[d]$, we connect
$w_{i,S,\ell}^{j}$ to the vertices $v_{i,k}^{j}$ and $v_{i,k}^{j+1}$ for all
$k\in[d]\setminus S$. 111111 The vertices for $j=m$ are only connected to the
first set of vertices, as the vertices $v_{i,k}^{m+1}$ do not exist.  That is,
if the vertices $\\{v_{i,k}^{j}\mid k\in S\\}$ with indices from $S$ are
selected, where $S\subseteq[d]$ and $\lvert S\rvert=d/2$, then we can also
select the vertices $\\{w_{i,S,\ell}^{j}\\}_{\ell}$ by the definition of the
graph.

Figure 9:  High-Level construction of the graph for $d=4$. The boxes represent
$6$-cliques where the red vertex corresponds to the vertex of set
$S=\\{2,3\\}$.

######  Claim 3.

The maximum independent sets of $C_{i}^{j}$ have size $d/2+d$.

For arbitrary $S\subseteq[d]$ with $\lvert S\rvert=d/2$ (depending on the
assignment), we select the vertices $\\{v_{i,k}^{j}\mid k\in S\\}$ and the
vertices $w_{i,S,\ell}^{j}$ for all $\ell\in[d]$.

Now assume otherwise such that more vertices are selected. Trivially each of
the $d$ cliques can contribute at most 1 vertex to the total number. Hence,
there must be more than $d/2$ input vertices selected. But then all sets of
$d/2$ input vertices intersect with the set of selected input vertices. Thus,
all vertices of the cliques are adjacent to at least one selected input
vertex. As a consequence this is not an independent set and the bound is
tight.

######  Claim 4.

Let $i\in[t]$. The size of the MIS in the graph induced by
$C_{i}^{1},\dots,C_{i}^{m}$ is exactly $(d/2+d)m$ if and only if for each
$C_{i}^{j}$ the same subset of vertices (with respect to the indices) is
selected. Otherwise the size of the MIS is smaller.

The “if” follows directly by the definition of the graph. For the “only if”
direction, the upper bound follows by bounding the size for each $C_{i}^{j}$
individually using 3. Assuming otherwise, there must be a $j\in[m]$ and some
$S,S^{\prime}\subseteq[d]$ with $\lvert S\rvert=\lvert S^{\prime}\rvert=d/2$
and $S\neq S^{\prime}$ such that the vertices $\\{v_{i,k}^{j}\mid k\in S\\}$
and the vertices $\\{v_{i,k}^{j+1}\mid k\in S^{\prime}\\}$ are selected. Thus,
there is some $k\in S^{\prime}\setminus S$ such that $w_{i,S,\ell}^{j}$ is
connected to $v_{i,k}^{j+1}$. As we are given an independent set, either none
of the vertices $w_{i,S,\ell}^{j}$ is selected or $v_{i,k}^{j+1}$ is not
selected. therefore the size can be at most $(d/2+d)m-1$ by using the upper
bound from 3 for the remaining gadgets. Thus the assignment is actually the
same for each $C_{i}^{j}$ when considering a MIS. We say that the partial
assignment is consistently encoded if the MIS has the size from 4.

Figure 10: Clause gadget for the lower bound for #MaxIndSet with $d=2,k=3$.
The splitted boxes at the bottom correspond to the $d$ cliques of each group
where the top part contains the $w_{i,S,\ell}$ with not satisfying $S$ and the
bottom part the ones with satisfiyng $S$. Black and gray edges connect
vertices of the same and different type, respectively.

*Encoding the Clauses. The clause gadget checks whether a specific clause is satisfied by the encoded partial assignments. See Figure 10 for an example of the construction. For this we fix some clause $C_{j}$ and omit $j$ from all vertices in the following to simplify notation. Without loss of generality we assume that $C_{j}$ contains only variables from the first $k$ groups.

The gadget uses three types of vertices:

  1. 1.

We create vertices $u_{0},\dots,u_{k}$ and $s_{0},\dots,s_{k}$ and connect
each pair of $u_{i},s_{i}$ by an edge. Moreover we connect $s_{i-1}$ to
$u_{i}$ for all $i\in[k]$. The idea is that the vertices $s_{i}$ represent the
“satisfied” state while the vertices $u_{i}$ represent the “unsatisfied”
state.

  2. 2.

We repeat the following procedure for all $i\in[k]$. We introduce vertices
$v_{ss,i,\ell}$, $v_{uu,i,\ell}$, and $v_{\square s,i,\ell}$ that are pairwise
connected for each $\ell\in[d]$, i.e. for each $\ell$ this is an triangle. We
make $v_{ss,i,\ell}$ adjacent to $u_{i-1}$ and $u_{i}$. Likewise we connect
$v_{uu,i,\ell}$ to $s_{i-1}$ and $s_{i}$. We also connect $v_{\square
s,i,\ell}$ to $u_{i}$.

For all $\ell\in[d]$, we connect the vertices $v_{uu,i,\ell}$ and
$v_{ss,i,\ell}$ to $w_{i,S,\ell}$ for all $S\subseteq[d]$ with $\lvert
S\rvert=d/2$ that represent a _satisfying_ partial assignment. Conversely, for
all $\ell$ the vertices $v_{\square s,i,\ell}$ are connected to $w_{i,S,\ell}$
for all $S$ representing an _unsatisfying_ partial assignment.

The idea is that the vertices $v_{uu,i,\ell}$ are selected, if the clause is
not yet satisfied and is also not satisfied by the assignment from this group.
The vertices $v_{ss,i,\ell}$ are selected if the clause was already satisfied
(and will be satisfied in the future). The vertices $v_{\square s,i,\ell}$ are
selected if the clause is satisfied by the assignment of the $i$th group,
independent from whether the clause was already satisfied.

  3. 3.

We make $s_{0}$ and $u_{k}$ adjacent to $d$ new vertices, each. This ensures
that in an MIS the vertices $s_{0}$ and $u_{k}$ are not selected. Instead, the
vertices $u_{0}$ and $s_{k}$ should be selected representing that the clause
is initially not satisfied and eventually is satisfied, respectively.

For the correctness observe that we only count the vertices that are newly
introduced. That is, we do not count the vertices $w_{i,S,\ell}$.

######  Claim 5.

If the assignment satisfies the clause and is consistently encoded, then there
is a unique way of selecting exactly $(k+1)+(kd)+(2d)$ vertices for a MIS.

We select $k+1$ vertices of the first type, $kd$ vertices of the second type,
and $2d$ vertices of the third type. Bounding the size of the MIS for each
type of vertices separately, shows that no MIS can be of larger size.

By these observations, we must select all vertices of the third type. This
implies that we must select the vertex $u_{0}$ as we either must select
$s_{i}$ or $u_{i}$ for all $i\in[0,k]$. We select the other vertices in
rounds.

If $u_{i-1}$ is selected, we cannot select $v_{ss,i,\ell}$ for the MIS. By the
above observation and since we want to construct an independent set we must
either select all $v_{uu,i,\ell}$ or all $v_{\square s,i,\ell}$. But observe
that we can only select the latter ones, if the assignment for group $i$ is
satisfying because the nodes are connected to the vertices that represent a
unsatisfying assignment. Conversely, the former vertices can only be selected
if the assignment is unsatisfying, as they are connected to vertices
representing a satisfying assignment.

If $s_{i-1}$ is selected, we cannot select $v_{uu,i,\ell}$ for the MIS because
of the adjacency of these vertices. We know that $s_{i}$ must also be
selected, as $u_{i}$ cannot be selected. Therefore, either all $v_{ss,i,\ell}$
vertices or all $v_{\square s,i,\ell}$ vertices are selected. The same
argument as before applies depending on the assignment which we are given.

By this procedure we eventually arrive at a point, where either $u_{k}$ or
$s_{k}$ must be selected. Since the clause is satisfied by the encoded
assignment, there is some $c\in[k]$ such that $u_{c-1}$ and $s_{c}$ are
selected. Thus, $s_{k}$ is selected and we can also select the remaining
vertices of the third type, namely the ones adjacent to $u_{k}$.

######  Claim 6.

Assume the assignment is consistently encoded. If the MIS has size
$(k+1)+(kd)+(2d)$, then this assignment satisfies the clause.

From the definition of the graph we get that $k+1$ vertices of the first type,
$kd$ vertices of the second type, and $2d$ vertices of the third type must be
selected.

Therefore, $u_{0}$ and $s_{k}$ must be selected. Since either $u_{i}$ or
$s_{i}$ must be selected for all $i\in[k]$, and by the edge between the
vertices $s_{i-1}$ and $u_{i}$ for all $i\in[k]$, there must be some $c\in[k]$
such that $u_{0},\dots,u_{c-1}$ and $s_{c},\dots,s_{k}$ are selected. This
especially implies that none of the vertices $v_{uu,c,\ell}$ and
$v_{ss,c,\ell}$ can be selected because they are connected to $s_{c}$ and
$u_{c-1}$, respectively. Therefore, the vertices $v_{\square s,c,\ell}$ must
be selected. But this is only possible if the vertices $w_{c,S,\ell}$ are
selected for some $S$ corresponding to a satisfying assignment. Thus, the
assignment satisfies the clause.

*Analysis of the Construction. For the final part of the lower bound it remains to analyze the pathwidth of the construction and to bound the degree. Both are depending on the parameters $d$ and $g$ we still need to set.

######  Claim 7.

The pathwidth of the graph is bounded by $\lceil{n}/{g}\rceil\cdot
d+\binom{d}{d/2}+d+\mathcal{O}(1).$

We use a mixed search approach. For this we iterate over all clauses. Then we
clean the clause gadget and the corresponding columns starting from the first
row (i.e. first group of variables). For this we place $d$ searchers on the
input vertices of the next gadget and then clean the cliques and clause gadget
sequentially by cleaning repetition by repetition. This is possible by using
$\binom{d}{d/2}+\mathcal{O}(1)$ searchers as the cliques are not connected to
each other. Moreover, the cliques are only connected to vertices that already
have a searcher on them, i.e. the vertices $v_{i,k}^{j}$, or to vertices
$v_{ss,i,\ell},v_{uu,i,\ell},v_{\square s,i,l}$ for a fixed $\ell$ on which we
also place searcher simultaneously. Thus we can clean the clause gadgets with
$\mathcal{O}(1)$ searchers. The degree of the vertices is bounded by
$\binom{d}{d/2}+2d+\mathcal{O}(1)$. This corresponds to the $r$ in the
statement of the lemma. As we will see later, the choice of $d$ depends only
on the choice of $\epsilon$.

*Lower Bound. Assume we are given an algorithm for #MaxIndSet with running time $(2-\epsilon)^{\operatorname{pw}}N^{\mathcal{O}(1)}$ for a graph with $N$ vertices and maximum degree $r$ for some $\epsilon>0$. We show that this can be used to count the number of satisfying assignments of a SAT formula in time $(2-\delta)^{n}n^{\mathcal{O}(1)}$ where we set $\delta=\epsilon/2>0$.

We choose an $\alpha>1$ such that $(2-\epsilon)^{\alpha}\leq(2-\delta)$ for
some suitable $\epsilon>\delta>0$. For the ease of simpler notation we define
$\epsilon^{\prime}=\log(2-\epsilon)$ and $\delta^{\prime}=\log(2-\delta)$.
Hence we get $\epsilon^{\prime}\alpha\leq\delta^{\prime}<1$. We choose some
$\beta<1$ such that $\alpha\beta>1$. Next we set $d$ to be an even integer
large enough such that

  * •

$g\coloneqq\lfloor\beta d\rfloor>0$,

  * •

$d\leq\alpha\lfloor\beta d\rfloor$,

  * •

and $d\leq 2^{(1-\beta)d+1}$.

We first show that we can actually encode all partial assignments. For this it
suffices to bound $\binom{2n}{n}$ from below by $4^{n}/n$ which follows
directly by induction starting from $n=4$. Then we get:

$\binom{d}{d/2}\geq\frac{2^{d+1}}{d}\geq 2^{\beta d}\geq 2^{g}.$

Now construct the graph as given above and count the number of maximum
independent sets. Since we know that the formula is satisfiable, the number of
MISs corresponds to the number of satisfying assignments. The running time of
this procedure is as follows:

$\displaystyle(2-\epsilon)^{\operatorname{pw}}(n+m)^{\mathcal{O}(1)}$
$\displaystyle\leq(2-\epsilon)^{\lceil\frac{n}{g}\rceil\cdot
d+\binom{d}{d/2}+d+\mathcal{O}(1)}(n+m)^{\mathcal{O}(1)}$
$\displaystyle\leq(2-\epsilon)^{\frac{n}{g}\cdot
d+\binom{d}{d/2}+2d+\mathcal{O}(1)}(n+m)^{\mathcal{O}(1)}$ Observe that $d$
does not depend on the input formula but just on $\epsilon$. Thus the term
$(2-\epsilon)^{\binom{d}{d/2}+2d+\mathcal{O}(1)}$ contributes only a constant
factor to the overall running time which can be hidden by the
$(n+m)^{\mathcal{O}(1)}$. $\displaystyle\leq(2-\epsilon)^{\frac{n}{g}\cdot
d}(n+m)^{\mathcal{O}(1)}$ $\displaystyle\leq
2^{\epsilon^{\prime}\frac{n}{\lfloor\beta d\rfloor}\cdot
d}(n+m)^{\mathcal{O}(1)}$ By our choice of $d$, $\alpha$, and $\beta$ be get:
$\displaystyle\leq 2^{\epsilon^{\prime}\alpha n}(n+m)^{\mathcal{O}(1)}\leq
2^{\delta^{\prime}n}(n+m)^{\mathcal{O}(1)}\leq(2-\delta)^{n}(n+m)^{\mathcal{O}(1)}$

But this running time now immediately contradicts #SETH and the claim follows.

The next step extends the previous result to regular graphs.

######  Lemma 8.7.

For every constant $\epsilon>0$, there is a $r>0$ such that #MaxIndSet on
$r$-regular graphs given with a path decomposition of width
${\operatorname{pw}}$ cannot be solved in time
$(2-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$, unless #SETH fails.

######  Proof 8.8.

Let $\epsilon>0$ be arbitrary. By Lemma 8.5 there is some $r^{\prime}>0$ (just
depending on $\epsilon$) such that #MaxIndSet on graphs of maximum degree
$r^{\prime}$ cannot be solved in time
$(2-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$, unless #SETH fails. We
modify such a #MaxIndSet instance $G$ to become a regular graph.

Set $r$ to be the odd number of $r^{\prime}$ and $r^{\prime}+1$. We first
construct a gadget with a vertex that is “forced” to _not_ be in any solution
of the #MaxIndSet instance. Take a $K_{r+1}$ and remove an edge between any
two vertices. Add an edge from both of these vertices to a vertex $v$. We
repeat this process $(r-1)/2-1$ more times to have $(r-1)/2$ modified cliques
such that $v$ has a degree of $r-1$ whereas all other vertices in the gadget
have a degree of $r$. We look at $v$ as the portal vertex of this gadget.
Observe that this gadget has a unique maximum independent set of size $r-1$
that does not contain $v$, i.e. the two non adjacent vertices from each of the
$(r-1)/2$ cliques are selected.

Now, for any vertex $u$ in $G$ we attach $r-\deg(u)$ copies of the gadget via
their portal vertex. The resulting graph is $r$-regular and retains all the
maximum independent sets from before.

The size of the graph increases to $\mathcal{O}(nr^{3})$ and the pathwidth
increases by an additive term of $r+2$. Observe that $r$ depends on
$r^{\prime}$ which only depends on the fixed $\epsilon$. When running the
claimed algorithm for the modified instance, this is just a constant factor
which asymptotically does not change the running time. But this contradicts
#SETH by Lemma 8.5.

Now we have everything ready for the last step of the reduction where we
reduce from #MaxIndSet on regular graphs to #EdgeCover.

######  Proof 8.9 (Proof of Theorem 8.1).

For a given $\epsilon>0$, we know from Lemma 8.7, that there is a $r>0$ such
that #MaxIndSet on $r$-regular graphs cannot be solved in time
$(2-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$, unless #SETH fails. Let
$G=(V,E)$ be such an $r$-regular #MaxIndSet instance. We follow the ideas from
the #P-completeness proof of #EdgeCover in [8].

Let $I_{j}(G)$ be the number of independent sets of size exactly $j$. Let
$G^{\prime}$ be graph after subdividing all edges by placing one new vertex on
each edge. Let the set of new vertices be $U$. Let $N_{i}(G^{\prime})$ be the
number of subsets $E^{\prime}$ of edges of $G^{\prime}$ such that $i$ vertices
of $V$ are not covered and all vertices of $U$ are covered. We follow a
similar argument as in [8, 9] to count the number of subgraphs that contribute
to $N_{i}(G^{\prime})$. For some independent set $S$ of size $j$ in $G$,
consider some vertex $v\in S$. Suppose its adjacent edges
$(v,v_{1}),\ldots,(v,v_{r})$ got subdivided to get the edges
$(v,u_{1}),\ldots,(v,u_{r}),(v_{1},u_{1}),\ldots,(v_{r},u_{r})$ for some
$u_{1},\ldots,u_{r}\in U$. We select none of $(v,u_{1}),\ldots,(v,u_{r})$ and
select all of $(v_{1},u_{1}),\ldots,(v_{r},u_{r})$ in the solution. Let us
repeat this for every $v\in S$. For the remaining edges, we choose them in
such a way that every $u\in U$ has at least one of its two incident edges
selected. The number of possible ways for this forms the LHS of the below
equation. The RHS is obtained from the observation that the above process
creates every subset of edges where $S$ is not covered and all of $U$ is
covered. If $E^{\prime}$ is a subset of edges that leaves a subset
$S^{\prime}$ of vertices uncovered, then the process generates $E^{\prime}$
when it is performed on a $S\subseteq S^{\prime}$. This means that there are
exactly $\binom{i}{j}$ subsets $S$ for which the process creates $E^{\prime}$.

$3^{rn/2-jr}I_{j}(G)=\sum_{i=j}^{n}\binom{i}{j}N_{i}(G^{\prime}).$

Thus, to recover the values of $I_{j}(G)$, we only need to recover the values
of $N_{i}(G^{\prime})$. Let $N_{ij}(G^{\prime})$ be the number of edge subsets
of $G^{\prime}$ which leave $i$ vertices in $V$ and $j$ vertices in $U$
uncovered. We now attach paths of length $m$ to all $v\in V$ and attach paths
of length $k$ to all $u\in U$. Let the resulting graph be $G^{\prime}_{m,k}$.
Let $M_{m}$ be the number of edge covers of a path of length $m$. We show how
to extend edge subsets of $G^{\prime}$ which leave $i$ vertices in $V$ and $j$
vertices in $U$ uncovered to edge covers of $G^{\prime}_{m,k}$. For a vertex
$v$ that is already covered by some edge, we can choose an edge cover of the
path attached to $v$ that either covers $v$ or not. For a vertex $v$ that is
not covered by any edge, we must choose an edge cover of the path attached to
$v$ that also covers $v$.

$\displaystyle N_{0}(G^{\prime}_{m,k})$
$\displaystyle=\sum_{i=0}^{n}\sum_{j=0}^{rn/2}M_{m}^{i}(M_{m}+M_{m-1})^{n-i}M_{k}^{j}(M_{k}+M_{k-1})^{rn/2-j}N_{ij}(G^{\prime})$
$\displaystyle=M_{m}^{n}M_{k}^{rn/2}\sum_{i=0}^{n}\Bigg{(}1+\frac{M_{m-1}}{M_{m}}\Bigg{)}^{n-i}\sum_{j=0}^{n}\Bigg{(}1+\frac{M_{k-1}}{M_{k}}\Bigg{)}^{rn/2-j}N_{ij}(G^{\prime}).$

Observe that $M_{m}=M_{m-1}+M_{m-2}$ with $M_{0}=M_{1}=1$. Since this is
precisely the definition of the Fibonacci numbers, we know that
$\frac{M_{m}}{M_{m-1}}$ takes infinitely many distinct values (though the
sequence is converging).

We can interpret $N_{0}(G^{\prime}_{m,k})$ as a polynomial in two variables
$1+\frac{M_{m-1}}{M_{m}}$ and $1+\frac{M_{k-1}}{M_{k}}$. Now, we use an oracle
for #EdgeCover to get the value of $N_{0}(G^{\prime}_{m,k})$ to do
interpolation and recover $N_{ij}(G^{\prime})$ for all values of $i,j$. This
then gives us $N_{i}(G^{\prime})=N_{i0}(G^{\prime})$ using which we can
recover the number of maximum independent sets of $G$.

The only remaining task is to argue that we do not affect the pathwidth much.
Observe that we only subdivided edges and attached graphs of constant
pathwidth to vertices. Both of these steps do not alter the pathwidth by more
than a constant. Thus, given a
$(2-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$ algorithm for #EdgeCover,
we can get a $(2-\delta)^{\operatorname{pw}}n^{\mathcal{O}(1)}$ algorithm for
#MaxIndSet on $r$-regular graphs. From Lemma 8.7, this contradicts #SETH.

## References

  * [1] Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh.  Parameterized complexity of conflict-free matchings and paths.  Algorithmica, 82(7):1939–1965, 2020.  doi:10.1007/s00453-020-00681-y.
  * [2] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 522–539. SIAM, 2021.  doi:10.1137/1.9781611976465.32.
  * [3] Hans L Bodlaender.  Dynamic programming on graphs with bounded treewidth.  In International Colloquium on Automata, Languages, and Programming, pages 105–118. Springer, 1988.
  * [4] Hans L Bodlaender.  Treewidth: Algorithmic techniques and results.  In International Symposium on Mathematical Foundations of Computer Science, pages 19–36. Springer, 1997.
  * [5] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof.  Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.  Inf. Comput., 243:86–111, 2015.  doi:10.1016/j.ic.2014.12.008.
  * [6] Hans L. Bodlaender and Arie M. C. A. Koster.  Combinatorial optimization on graphs of bounded treewidth.  Comput. J., 51(3):255–269, 2008.  doi:10.1093/comjnl/bxm037.
  * [7] Édouard Bonnet, Nick Brettell, O-joung Kwon, and Dániel Marx.  Generalized feedback vertex set problems on bounded-treewidth graphs: Chordality is the key to single-exponential parameterized algorithms.  Algorithmica, 81(10):3890–3935, 2019.  doi:10.1007/s00453-019-00579-4.
  * [8] Magnus Bordewich, Martin E. Dyer, and Marek Karpinski.  Path coupling using stopping times and counting independent sets and colorings in hypergraphs.  Random Struct. Algorithms, 32(3):375–399, 2008.  doi:10.1002/rsa.20204.
  * [9] Russ Bubley and Martin E. Dyer.  Graph orientations with no sink and an approximation for a hard case of #sat.  In Michael E. Saks, editor, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA, pages 248–257. ACM/SIAM, 1997.  URL: http://dl.acm.org/citation.cfm?id=314161.314263.
  * [10] Jin-yi Cai, Sangxia Huang, and Pinyan Lu.  From holant to #csp and back: Dichotomy for holant${}^{\mbox{\emph{c}}}$ problems.  In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, volume 6506 of Lecture Notes in Computer Science, pages 253–265. Springer, 2010.  doi:10.1007/978-3-642-17517-6_24.
  * [11] Jin-yi Cai, Pinyan Lu, and Mingji Xia.  A computational proof of complexity of some restricted counting problems.  Theor. Comput. Sci., 412(23):2468–2485, 2011.  doi:10.1016/j.tcs.2010.10.039.
  * [12] Gérard Cornuéjols.  General factors of graphs.  J. Comb. Theory, Ser. B, 45(2):185–198, 1988.  doi:10.1016/0095-8956(88)90068-8.
  * [13] Radu Curticapean.  Block interpolation: A framework for tight exponential-time counting complexity.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 380–392. Springer, 2015.  doi:10.1007/978-3-662-47672-7\\_31.
  * [14] 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.
  * [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.
  * [16] Víctor Dalmau and Daniel K. Ford.  Generalized satisfability with limited occurrences per variable: A study through delta-matroid parity.  In Branislav Rovan and Peter Vojtás, editors, Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings, volume 2747 of Lecture Notes in Computer Science, pages 358–367. Springer, 2003.  doi:10.1007/978-3-540-45138-9_30.
  * [17] Szymon Dudycz and Katarzyna Paluch.  Optimal general matchings.  In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, volume 11159 of Lecture Notes in Computer Science, pages 176–189. Springer, 2018.  Full version: arXiv:1706.07418.  doi:10.1007/978-3-030-00256-5_15.
  * [18] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.  doi:10.4153/CJM-1965-045-4.
  * [19] Eduard Eiben and Iyad Kanj.  A colored path problem and its applications.  ACM Trans. Algorithms, 16(4):47:1–47:48, 2020.  doi:10.1145/3396573.
  * [20] 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.
  * [21] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Representative families of product families.  ACM Trans. Algorithms, 13(3):36:1–36:29, 2017.  doi:10.1145/3039243.
  * [22] Heng Guo and Pinyan Lu.  On the complexity of holant problems.  In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 159–177. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/DFU.Vol7.15301.6.
  * [23] John E Hopcroft and Richard M Karp.  An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.  SIAM Journal on computing, 2(4):225–231, 1973.
  * [24] Sangxia Huang and Pinyan Lu.  A dichotomy for real weighted holant problems.  Comput. Complex., 25(1):255–304, 2016.  doi:10.1007/s00037-015-0118-3.
  * [25] 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.
  * [26] Michael Kowalczyk and Jin-Yi Cai.  Holant problems for 3-regular graphs with complex edge functions.  Theory Comput. Syst., 59(1):133–158, 2016.  doi:10.1007/s00224-016-9671-7.
  * [27] 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.
  * [28] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Known algorithms on graphs of bounded treewidth are probably optimal.  ACM Trans. Algorithms, 14(2):13:1–13:30, 2018.  doi:10.1145/3170442.
  * [29] L. Lovász and M. D. Plummer.  Matching Theory.  North-Holland Publishing Co., Amsterdam, 1986.  Annals of Discrete Mathematics, 29.
  * [30] László Lovász.  The factorization of graphs. II.  Acta Mathematica Hungarica, 23(1-2):223–246, 1972.
  * [31] Pinyan Lu.  Complexity dichotomies of counting problems.  Electron. Colloquium Comput. Complex., 18:93, 2011.  URL: http://eccc.hpi-web.de/report/2011/093.
  * [32] 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.  Full version: arXiv:2105.08980.  doi:10.4230/LIPIcs.ICALP.2021.95.
  * [33] Dániel Marx and Paul Wollan.  An exact characterization of tractable demand patterns for maximum disjoint path problems.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 642–661. SIAM, 2015.  doi:10.1137/1.9781611973730.44.
  * [34] Silvio Micali and Vijay V. Vazirani.  An O(sqrt($|$v$|$) $|$E$|$) algorithm for finding maximum matching in general graphs.  In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 17–27. IEEE Computer Society, 1980.  doi:10.1109/SFCS.1980.12.
  * [35] Burkhard Monien.  How to find long paths efficiently.  In Analysis and design of algorithms for combinatorial problems (Udine, 1982), volume 109 of North-Holland Math. Stud., pages 239–254. North-Holland, Amsterdam, 1985.
  * [36] András Sebö.  General antifactors of graphs.  J. Comb. Theory, Ser. B, 58(2):174–184, 1993.
  * [37] Hadas Shachnai and Meirav Zehavi.  Representative families: A unified tradeoff-based approach.  J. Comput. Syst. Sci., 82(3):488–502, 2016.  doi:10.1016/j.jcss.2015.11.008.
  * [38] 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.