CISPA Helmholtz Center for Information Security, Saarland Informatics Campus,
Germany<EMAIL_ADDRESS>Indian Institute of Technology Madras, Chennai,
India<EMAIL_ADDRESS>https://orcid.org/0000-0002-7443-9599 CISPA
Helmholtz Center for Information Security, Saarland Informatics Campus,
Germany and Saarbrücken Graduate School of Computer Science, Saarland
Informatics Campus, Germany<EMAIL_ADDRESS>https://orcid.org/0000-0002-5810-7949 Dániel Marx, Govind S. Sankar, and
Philipp Schepper Research supported by the European Research Council (ERC)
consolidator grant No. 725978 SYSTEMATICGRAPH. Nikhil Bansal, Emanuela
Merelli, and James Worrell 3 48th International Colloquium on Automata,
Languages, and Programming (ICALP 2021) ICALP 2021 ICALP 2021 July 12–16, 2021
Glasgow, Scotland (Virtual Conference) 198 91 Theory of computation
Parameterized complexity and exact algorithms Full version of the paper
accepted for ICALP21.

# Degrees and Gaps: Tight Complexity Results of General Factor Problems
Parameterized by Treewidth and Cutwidth

Dániel Marx  Govind S. Sankar  Philipp Schepper

###### Abstract

In the General Factor problem, we are given an undirected graph $G$ and for
each vertex $v\in V(G)$ a finite set $B_{v}$ of non-negative integers. The
task is to decide if there is a subset $S\subseteq E(G)$ such that
$\deg_{S}(v)\in B_{v}$ for all vertices $v$ of $G$. Define the
$\operatorname{max-gap}$ of a finite integer set $B$ to be the largest $d\geq
0$ such that there is an $a\geq 0$ with $[a,a+d+1]\cap B=\\{a,a+d+1\\}$.
Cornuéjols showed in 1988 that if the $\operatorname{max-gap}$ of all sets
$B_{v}$ is at most 1, then the decision version of General Factor is
polynomial-time solvable. This result was extended 2018 by Dudycz and Paluch
for the optimization (i.e. minimization and maximization) versions. We present
a general algorithm counting the number of solutions of a certain size in time
$(M+1)^{\operatorname{tw}}n^{\mathcal{O}(1)}$, given a tree decomposition of
width ${\operatorname{tw}}$, where $M$ is the maximum integer over all
$B_{v}$. By using convolution techniques from van Rooij (2020), we improve
upon the previous $(M+1)^{3{\operatorname{tw}}}n^{\mathcal{O}(1)}$ time
algorithm by Arulselvan et al. from 2018.

We prove that this algorithm is essentially optimal for all cases that are not
trivial or polynomial time solvable for the decision, minimization or
maximization versions. Our lower bounds show that such an improvement is not
even possible for $B$-Factor, which is General Factor on graphs where all sets
$B_{v}$ agree with the fixed set $B$. We show that for every fixed $B$ where
the problem is NP-hard, our $(\max
B+1)^{{\operatorname{tw}}}n^{\mathcal{O}(1)}$ algorithm cannot be
significantly improved: assuming the Strong Exponential Time Hypothesis
(SETH), no algorithm can solve $B$-Factor in time $(\max
B+1-\epsilon)^{\operatorname{tw}}n^{\mathcal{O}(1)}$ for any $\epsilon>0$. We
extend this bound to the counting version of $B$-Factor for arbitrary, non-
trivial sets $B$, assuming #SETH.

We also investigate the parameterization of the problem by cutwidth. Unlike
for treewidth, having a larger set $B$ does not appear to make the problem
harder: we give a $2^{\operatorname{cutw}}n^{\mathcal{O}(1)}$ algorithm for
any $B$ and provide a matching lower bound that this is optimal for the NP-
hard cases.

###### keywords:

General Factor, General Matching, Treewidth, Cutwidth

##  1 Introduction

Matching problems for graphs are widely studied in computer science [1, 9, 13,
21, 22, 28, 32, 37, 39, 41]. The most prominent ones are Perfect Matching
(PerfMatch) and Maximum-Weight Matching. Both problems have long known
polynomial-time algorithms [22, 39] and various generalizations were
investigated in the graph-theory literature. These range from simple
extensions such as the $k$-factor problem for a positive integer $k$ (every
vertex has to be incident to exactly $k$ edges) [2, 32], to more complex ones,
where the vertices are assigned intervals [41]. These problems are generally
solved by a reduction to PerfMatch by replacing the vertices of the original
instance with suitable gadgets. Lovász introduced a general version of these
problems which we call General Factor [37]:

######  Definition 1.1 (General Factor (GenFac)).

Let $G=(V,E)$ be an undirected node labeled graph where the label of a vertex
$v$ is a set $B_{v}\subseteq{\mathbb{N}}$. We say $S\subseteq E$ is a
_solution_ if $\deg_{S}(v)\in B_{v}$ for all $v\in V$. GenFac is the problem
of deciding whether $G$ has a solution.

The minimization and maximization versions of GenFac are the problems of
finding the size of the solution with smallest and largest cardinality,
respectively.

###### Polynomial-Time Solvable Cases.

For several cases (e.g. $k$-factor, sets are intervals) reductions to
PerfMatch are known, leading directly to polynomial-time algorithms.
Cornuéjols analyzed the complexity of the general problem to identify
properties of the sets that make the problem easier to solve [9]. For this he
introduced the _gap_ of a set: A gap is a finite sequence of consecutive
integers not contained in the set but whose boundaries are contained in the
set (cf. Definition 2.2). For example, the set $\\{1,5,6,8\\}$ has gaps of
size $3$ and $1$. For a set $S$, $\operatorname{max-gap}S$ denotes the size of
its largest gap. Cornuéjols showed that if the max-gaps of all sets are at
most $1$, then the problem is polynomial-time solvable. Later this result was
extended to the maximization and minimization (optimization) versions of
GenFac.

######  Theorem 1.2 ([9, 21]).

The decision, maximization, and minimization version of GenFac can be solved
in polynomial time on arbitrary graphs if for all nodes $v$,
$\operatorname{max-gap}B_{v}\leq 1$.

On the other side Cornuéjols proved GenFac to be NP-complete if there are
nodes with a gap of size two, namely $\\{1\\}$ and $\\{0,3\\}$, by a reduction
from _exact $3$-cover_. More generally, it can be deduced from the work of
Feder [25] that GenFac becomes NP-complete whenever every set $B_{v}$ is
restricted to be the same fixed set $B$ having gap size at least two.

###### Treewidth.

This paper is part of a long sequence of works studying problems parameterized
by treewidth and related metrics like cutwidth or cliquewidth. Treewidth
received significant attention as many NP-hard problems like Colouring,
Independent Set, or Dominating Set (see [4] for a survey) are polynomial-time
solvable on bounded-treewidth graphs. Courcelle’s Theorem [10, 11] shows that
a large class of graph problems can be solved in linear time on graphs of
bounded treewidth. Recent developments on the algorithmic side include various
techniques such as Cut & Count [17, 40], rank-based dynamic programming [3,
16, 26] and fast subset convolution [45, 46]. On the negative side, there have
been a large number of results showing lower bounds based on complexity
assumptions such as the Exponential Time Hypothesis (ETH) and the Strong
Exponential Time Hypothesis (SETH) [7, 14, 35, 36]. For many such problems,
their optimal algorithms utilize some form of dynamic programming, where a
“state” is stored for every node in the tree decomposition. The number of such
states determines the running time of the algorithms, seemingly suggesting
that this number is a natural barrier to the running time of any algorithm.
Typically, the conditional lower bounds confirm this intuition by showing that
no algorithm can break this barrier.

###### New Faster Algorithms.

One of the first algorithmic results for GenFac parameterized by treewidth was
given by Arulselvan et al. [1]. They present an algorithm for a restricted
version of the problem where the sets contain zero and an interval of
integers. This algorithm can be easily extended to handle arbitrary instances
while preserving the running time of
$(M+1)^{3{\operatorname{tw}}}n^{\mathcal{O}(1)}$ where $M$ is the maximum over
all sets assigned to the vertices. Their algorithm is based on the standard
dynamic programming approach when parameterizing by treewidth, i.e. it
considers all possible states for each node of the tree decomposition. The
number of states in the dynamic programming is about
$(M+1)^{{\operatorname{tw}}+1}$: one needs to keep track of the degree of the
partial solution at each of the at most ${\operatorname{tw}}+1$ vertices of a
bag of the tree decomposition, and this degree can be between 0 and $M$.
Therefore, a natural question is whether the algorithm can be improved to
obtain an $(M+1)^{\operatorname{tw}}n^{\mathcal{O}(1)}$ running time, matching
the number of states. Such improvements are known for other problems, for
example for Dominating Set and #PerfMatch in [46]. We base our algorithm on
the same dynamic programming idea, but instead of processing all combination
of states at join nodes, we make use of the technique of van Rooij [45] to
compute fast convolutions, avoiding this bottle-neck of the computation. The
algorithm can be easily generalized to the optimization and counting versions
as well; to unify the results, we present the algorithm in a way that counts
all solutions of a certain given size.

######  Theorem 1.3.

Given a GenFac instance $G$ and a tree decomposition of width
${\operatorname{tw}}$. Let $M=\max_{v\in V(G)}\max B_{v}$. Then for all $s$,
we can count the solutions of size exactly $s$ in time
$(M+1)^{{\operatorname{tw}}}n^{\mathcal{O}(1)}$.

As we shall see, this algorithm is essentially optimal for every fixed $B$
where $B$-Factor is NP-hard. Note that in order to obtain this optimal running
time, we have to use a well-known, but non-trivial technique; beyond that, our
algorithm does not provide new insights into the problem.

###### Tight Lower Bounds for the Decision Version.

To investigate how the properties of the sets $B_{v}$ influence the complexity
of the problem, we give conditional lower bounds based on SETH for the
restrictive $B$-Factor problem, where all sets have to be the same fixed set
$B$. By a careful design our lower bounds also hold for a parameterization by
_pathwidth_. Note that if the set is not fixed, Arulselvan et al. showed that
GenFac is W$[1]$-hard when parameterizing only by treewidth [1]. Thus, it is
reasonable to focus only on the cases with fixed sets to prove tight lower
bounds.

######  Theorem 1.4 (Lower Bound for Decision Version).

Let $B\subseteq{\mathbb{N}}$ be a fixed, finite set with $0\notin B$ and
$\operatorname{max-gap}B>1$. If, given a path decomposition of width
${\operatorname{pw}}$, $B$-Factor can be solved in time $(\max
B+1-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$ for some $\epsilon>0$
even on graphs with degree at most $2\max B$, then SETH is false.

The same result immediately follows for treewidth as for all graphs the
pathwidth forms an upper-bound for the treewidth [15]. Hence, our algorithm is
optimal not only for GenFac but also for $B$-Factor parameterized by treewidth
and does not allow major improvements.

###### Tight Lower Bounds for the Optimization Version.

It suffices to consider the maximization version with $\operatorname{max-
gap}B>1$ and $0\in B$ for the optimization version. The other cases are either
polynomial-time solvable ($\operatorname{max-gap}B\leq 1$ or $0\in B$ for
Min-$B$-Factor) [21] or the hardness directly follows from the lower bound for
the decision version. Observe that the assumption $0\in B$ does not make the
problem trivially solvable. For these cases, we give essentially the same
lower bound as for the decision version. Again the bound rules out that we can
improve the given algorithm substantially; the running time is essentially
optimal.

######  Theorem 1.5 (Lower Bound for Maximization Version).

Let $B\subseteq{\mathbb{N}}$ be a fixed, finite set with $\operatorname{max-
gap}B>1$. If, given a path decomposition of width ${\operatorname{pw}}$,
Max-$B$-Factor can be solved in time $(\max
B+1-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$ for some $\epsilon>0$
even on graphs with degree at most $2\max B$, then SETH is false.

###### Counting.

It is well known that PerfMatch can be solved in polynomial time [22].
Surprisingly, Valiant showed in [42] that _counting_ the number of perfect
matchings of a graph is as hard as counting satisfying assignment of a boolean
formula. This is curious as (presumably) no polynomial-time algorithm for the
decision version of the latter problem exists. The observation then led to the
definition of the complexity class #P containing the counting problems whose
corresponding decision version lies in NP. Indeed, this feature that some
structures are easy to find but hard to count appears in our work as well.
Apart from #PerfMatch, which itself is #$\\{1\\}$-Factor, our results imply
that #$B$-Factor is #P-hard for any finite, fixed $B$. This contrasts with the
decision version, where the problem is easy when $\operatorname{max-gap}B\leq
1$. Over and above showing #P-hardness, we show a tight lower bound for
#$B$-Factor, assuming #SETH, the counting version of SETH. There have been
several results [12, 13, 20] based on #SETH and #ETH. Some of our
constructions were inspired by one such work by Curticapean and Marx [13],
where they show a lower bound of
$(2-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$ for #PerfMatch on
graphs assuming #SETH. We prove a wide generalization of this result by
providing a tight lower bound for every #$B$-Factor problem. As for the
optimization and decision version, our algorithm shows the tightness of this
lower bound.

######  Theorem 1.6 (Lower Bound for Counting Version).

Let $B\subseteq{\mathbb{N}}$ be a nonempty, fixed, and finite set such that
$B\neq\\{0\\}$. If, given a path decomposition of width ${\operatorname{pw}}$,
#$B$-Factor can be solved in time $(\max
B+1-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$ for some $\epsilon>0$
even on graphs with degree at most $2\max B+6$, then #SETH is false.

We also investigate #Max-$B$-Factor, the problem of counting maximum-sized
solutions. The following argument shows that #$\\{\max B\\}$-Factor can be
reduced to #Max-$B$-Factor without increasing pathwidth, hence Theorem 1.6
gives a lower bound of $(\max
B+1-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$. Consider an instance
of #$\\{\max B\\}$-Factor on a graph $G$ of pathwidth ${\operatorname{pw}}$.
In polynomial time, check if $G$ has some $\\{\max B\\}$-Factor [9]. If it
does not, then output 0. If it does, then solve #Max-$B$-Factor on $G$. As now
every maximum-sized $B$-Factor is actually a $\\{\max B\\}$-Factor, this
indeed solves the #$\\{\max B\\}$-Factor problem.

######  Corollary 1.7.

Let $B\subseteq{\mathbb{N}}$ be a fixed, finite set such that $B\neq\\{0\\}$.
If, given a path decomposition of width ${\operatorname{pw}}$, #Max-$B$-Factor
can be solved in time $(\max
B+1-\epsilon)^{{\operatorname{pw}}}n^{\mathcal{O}(1)}$ for some $\epsilon>0$
even on graphs with degree at most $2\max B+6$, then SETH is false.

We leave open the question of a tight lower bound for the minimization
version.

###### Parameterizing by Cutwidth.

As previously mentioned, pathwidth and treewidth are not the only parameters
used in parameterized complexity. Cutwidth, cliquewidth, genus, and crossing
number are only a few more examples of a vast class of possible parameters.
For cutwidth, we consider linear layouts of graphs with $n$ vertices, which
are just enumerations $v_{1},\dots,v_{n}$ of all graph vertices. Then the cut
after vertex $v_{i}$ consists of all edges in $G$ with one end in
$\\{v_{1},\dots,v_{i}\\}$ and the other end in $\\{v_{i+1},\dots,v_{n}\\}$.
The _cutwidth_ of a linear layout is the maximum over the size of the cut
after every $v_{i}$. The cutwidth ${\operatorname{cutw}}$ of a graph is the
minimum over the cutwidths of all possible linear layouts. As
${\operatorname{tw}}\leq{\operatorname{pw}}\leq{\operatorname{cutw}}$, it is
not completely surprising that we get different upper bounds for cutwidth. But
now a simple dynamic program suffices to prove the upper bound for this case.
Further, the running time of the algorithm is independent from the maximum of
the set $B$.

######  Theorem 1.8.

Given a linear layout of a GenFac instance $G$ with width
${\operatorname{cutw}}$, for all $s$ we can count the number of solutions of
size exactly $s$ in time $2^{\operatorname{cutw}}n^{\mathcal{O}(1)}$,.

This again matches the number of states for each cut of the linear layout.
Like before, we omit the algorithm here and refer the reader to the full
version. Note that the running times appearing in Theorems 1.3 and 1.8 cannot
be directly compared: the base is lower when parameterized by cutwidth, but
cutwidth can be larger than treewidth.

By a modified high-level construction, we show matching lower bounds based on
SETH for the decision and optimization versions, and, based on #SETH, for the
counting version.

######  Theorem 1.9 (Lower Bounds for Cutwidth).

Let $B\subseteq{\mathbb{N}}$ be a fixed, nonempty set of finite size. If,
given a linear layout of width ${\operatorname{cutw}}$, the following problems
can be solved in time $(2-\epsilon)^{{\operatorname{cutw}}}n^{\mathcal{O}(1)}$
for any $\epsilon>0$ even on graphs with degree at most $2\max B+6$, then SETH
(resp. #SETH) fails: (1) $B$-Factor and Min-$B$-Factor if $0\notin B$ and
$\operatorname{max-gap}B>1$, (2) Max-$B$-Factor if $\operatorname{max-
gap}B>1$, and (3) #$B$-Factor if $B\neq\\{0\\}$.

###  1.1 Techniques

######  NP-Hardness.

Existing results that explicitly show hardness for the GenFac (or $B$-Factor)
problem have been limited. For example, Cornuéjols showed in [9] the hardness
only for the case when the lists are either $\\{0,3\\}$ or $\\{1\\}$. However,
as we discuss below, the results from Feder in [25] implicitly show that the
$B$-Factor problem is NP-hard when the allowed lists have a gap of size more
than 1. Feder [25] considered the complexity of Boolean CSP instances where
each variable appears in two constraint and each constraint enforces a
relation $R$. As pointed out by Dalmau and Ford in [19], the results in [25]
show that when $R$ does not form a $\Delta$-matroid, then the problem is NP-
hard.

We say that the relation $R$ is symmetric if membership of a tuple in $R$
depends only on the Hamming weight of the tuple, i.e., $R$ contains exactly
those tuples that have Hamming weight from a set $B$. In this case, a CSP
instance where each variable appears in two $R$-constraints can be naturally
represented as a $B$-Factor instance: the vertices correspond to the
constraints and the edges correspond to the variables.111There is a minor
technicality here: the resulting graph can be a multigraph. This can be
resolved by placing vertices with list $\\{0,2\\}$ on the parallel edges. For
the case where $\operatorname{max-gap}B>1$, such vertices can be _realized_
(see Lemma 1.10) by vertices with list $B$.  It can be observed that if $B$
has gaps of size more than 1, then the corresponding symmetric relation $R$
cannot form a $\Delta$-matroid. This, combined with the results from [25] show
the NP-completeness of $B$-Factor when $\operatorname{max-gap}B>1$.

###### High-level Structure.

The known NP-hardness proofs do not fully utilize the capacity for GenFac to
represent relations. For example, [25] argues that just being able to
represent the relation $\\{(x,y,z)\mathrel{\mathop{\mathchar
58\relax}}x=y=z\\}$ is enough to ensure NP-hardness. Our lower bounds use the
fact that GenFac (and even $B$-Factor) can represent almost _any_ relation. We
have two main steps. We first reduce from SAT to the intermediate problem
$B$-Factor with Relations ($B$-FactorR). This is an extension of $B$-Factor
where we can additionally assign (almost) arbitrary relations to the vertices
of the graph and not only the set $B$ (cf. Definition 4.1). This reduction
step is similar to previous lower bound constructions [36]. In the second
step, we reduce from $B$-FactorR to $B$-Factor by replacing each relation and
its node by a graph expressing the required relation.

For both the pathwidth and cutwidth lower bounds, our broad-strokes idea is
the same. See Figure 1 for an illustration. For a given SAT instance, we use
vertical columns of high-degree vertices to store the assignment (or “state”)
of the variables. This state is stored as the number of edges to its left that
are selected in any solution. When parameterizing by cutwidth, this process is
easier; we can afford one vertex for each variable of the SAT instance since
we are only looking for a lower bound of
$(2-\epsilon)^{{\operatorname{cutw}}}n^{\mathcal{O}(1)}$. However, in the
pathwidth case, we want to show a lowerbound of $(\max
B+1-\epsilon)^{\operatorname{pw}}n^{\mathcal{O}(1)}$. This means that our
constructed graph should have pathwidth $\frac{n}{\log(\max
B+1)}+\mathcal{O}(1)$. We achieve this by grouping $q$ variables together and
associate a set of $g$ vertices with each group, where $2^{q}$ is roughly
$(\max B+1)^{g}$. By this the lower bound we get is the number of assignments
or states that we can store for a given pathwidth. This directly connects to
the dynamic-programming algorithms on path decompositions, where the running
time is determined by how many states each node has to store. Thus, our
vertical columns represent several of the bags of the path decomposition.

Figure 1: Pink boxes represent the vertical columns of vertices that store the
state of the variables. Blue boxes labelled $R_{i}$ verify that the $i$th
clause is satisfied. Here, $m$ is the number of clauses.

Once we are able to propagate the information about the assignments through
these vertical columns, we use some relations placed between them to verify
that the assignment satisfies all the clauses. Afterwards, we exploit the
(large) gap of the set $B$ and replace the relations by vertices with list $B$
such that we finally get a $B$-Factor instance.

###### Realizations for the Decision Version.

We do this step from $B$-FactorR to $B$-Factor through what we call
_realizations_. We say that we can realize a relation
$R\subseteq{\\{0,1\\}}^{d}$ if we have a gadget $G$ with $d$ _dangling edges_
, exactly one corresponding to each coordinate of the relation, such that $G$
behaves in some special way. These dangling edges (say $D$) have one endpoint
in $G$ and another endpoint outside of $G$. These edges act as inputs to the
function $f$. We say that the function is realized iff the only solutions are
those that pick $D^{\prime}\subseteq D$ such that $D^{\prime}\in R$. For a
more rigorous definition, see Section 5. For example, when showing the
hardness for the decision version of the problem, we use the following key
result. We say that a Boolean function is _even_ if it is zero for all inputs
with odd Hamming weight.

######  Lemma 1.10.

Let $R\subseteq 2^{[d]}$ be an even Boolean relation. Then for every fixed,
finite set $B\subseteq{\mathbb{N}}$ with $\operatorname{max-gap}B>1$ and
$0\notin B$, there is a $B$-Factor instance $G$ with a set $D$ of $d$ dangling
edges identified with $[d]$ such that for all $D^{\prime}\subseteq D$ it holds
that $D^{\prime}\in R$ if and only if there is a solution $S\subseteq E$ with
$S\cap D=D^{\prime}$.

See our later sections for a more formal treatment of this statement. This
method of realizing relations was originally introduced in [13] to show tight
lower bounds for #PerfMatch. We also show similar lemmas for the optimization
and counting versions.

###### Realizations for the Optimization Version.

As mentioned earlier, for the maximization version we have to deal with $0\in
B$ which implies that we cannot rule out solutions in all cases. Therefore, we
relax the condition “no solution” for the realization and allow the existence
of “small” solutions. This gap between largest (as we are considering the
maximization version) and small solutions will be the _penalty_ of the
realizations. To understand how we implement this penalty, first observe that
the crucial difference between the decision and the optimization version is
that we cannot force edges. Hence, it almost suffices to find a way to force
edges to a vertex and obtain a large solution. Otherwise, if the edges we want
to force are not selected, the solution should be small. For this we exploit
the large gap of the set $B$ and combine it with regular graphs of high
girth.222The girth of a graph is the length of the shortest cycle of a graph.
The idea is now the following: If the forced edge is selected, we can select
all edges. Otherwise, another (internal) edge is not selected, because we
cannot have a degree not contained in $B$. As the girth of the graph is large,
this will lead to many not selected edges and hence the penalty of this
realization is large.

###### Holants.

For the counting version, we first describe the Holant problem for (possibly
weighted) graphs. Introduced by Valiant in [44], Holants captures a large
class of graph problems including coloring problems, vertex cover, and
matchings [33]. The input to the problem is a graph and relations over the
incident edges of each vertex. The Holant problem on unweighted graphs asks to
count the number of subgraphs such that each such relation is satisfied. This
can be seen as a general version of #$B$-FactorR where all vertices are
assigned a relation. Hence, #GenFac can be seen as the restriction of the
Holant problem on unweighted graphs where all relations are _symmetric_. See
Section 7 for a formal introduction.

There has been a significant amount of work on the Holant framework in the
past two decades [5, 6, 27, 38]. A few of these works directly imply a
#P-hardness for some cases of #$B$-Factor. For example, we can use the
dichotomy theorem from Cai, Huang, and Lu [5] in the following way when $B$
contains 0, 1 and 2: Let $x$ be the smallest number not in $B$. To a vertex of
list $B$, attach $x-3$ vertices with list $B$ and attach three dangling edges.
This gadget can be seen as one node with three dangling edges. It can be shown
via the dichotomy theorem by Cai et al. that the Holant problem is #P-hard
when only such nodes are allowed. However, it is not immediate how to realize
relations with this approach, nor is it clear how the treewidth of the graphs
change through the holographic reductions that are common in showing
#P-hardness with Holant problems. We circumvent these problems by showing the
realizations through polynomial interpolation instead of holographic
reductions. To our knowledge, this technique was introduced by Valiant in
[43], where the problem of counting _all_ matchings was shown to be as hard as
counting _perfect_ matchings. In our notation, this would correspond to an
interpolation argument between #$\\{1\\}$-Factor and #$\\{0,1\\}$-Factor.

###### Techniques for Cutwidth Lower Bound.

As mentioned earlier, we additionally show a matching lower bound
parameterized by cutwidth. For this it is crucial to see that the construction
for the pathwidth lower bound has large cutwidth. Hence, instead of having
several variables per vertex, each vertex now corresponds to exactly one
variable. Although this construction does not work for the pathwidth bound as
it produced large pathwidth, it is sufficient in this setting. The graph will
be a grid-like structure where the edges of the rows encode the assignment to
the variables and the edges of the columns simulate whether we have already
satisfied the clause. We start with every clause being unsatisfied in the
first row. Then for each row we check at the crossing points if the variable
and the corresponding assignment satisfy the clause. We define relations of
constant degree to simulate this behaviour. Then we make use of the previous
realization results and replace all relations by their realization. This
almost immediately gives us the lower bounds when parameterized by cutwidth.

###  1.2 Structure of the Paper

Section 2 introduces useful notation and definitions we use in the paper. The
two algorithms for parameterization by treewidth and cutwidth are given in
Section 3. In Section 4 we show the reduction from SAT to our intermediate
problem $B$-FactorR. The version-dependent constructions of the realizations
and the corresponding lower bounds are shown in Section 5 for the decision
version, in Section 6 for the optimization version, and for the counting
version in Section 7. Section 8 is dedicated to the lower bound construction
when parameterizing by cutwidth.

##  2 Preliminaries

We introduce homogeneous graphs to formally define $B$-Factor.

######  Definition 2.1 (Homogeneous Graphs and $B$-Factor).

Let $B\subseteq{\mathbb{N}}$ be some fixed, finite set. We say a node-labeled
graph is _$B$ -homogeneous_ if for each node $v\in V$ it holds that $B_{v}=B$.
Then $B$-Factor is the restriction of GenFac to $B$-homogeneous graphs.

This definition directly transfers to the optimization and counting version.
We now formally introduce the max-gap of integer sets along with some other
properties.

######  Definition 2.2.

Let $B\subseteq{\mathbb{N}}$ be finite. We define $\operatorname{max-gap}B$ as
the largest non-negative integer $d$ such that there is an $a\in B$ with
$[a,a+d+1]\cap B=\\{a,a+d+1\\}$.

In this paper we regularly insert graphs into other graphs. To make this
operation formal, we make use of _dangling edges_ : these are edges that have
only one endpoint. We denote a dangling edge with endpoint $v$ by $(?,v)$. For
the sake of completeness we now formally define this procedure of replacing
the relations, i.e. the insertion of a graph into another graph.

######  Definition 2.3 (Insertion).

Let $G=(V,E)$ be a graph and $v\in V$ be of degree $k$, with incident edges
$e_{1}=(v_{1},v),\dots,e_{k}=(v_{k},v)$ that are ordered in some fixed way.
Let $H=(W,F)$ be a graph with dangling edges
$d_{1}=(?,u_{1}),\dots,d_{k}=(?,u_{k})$ where the $u_{i}$ are not necessarily
pairwise distinct. _Inserting_ $H$ in $G$ at $v$ gives us a new graph
$G^{\prime}=(V^{\prime},E^{\prime})$ where:

$V^{\prime}=(V\cup W)\setminus\\{v\\}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}E^{\prime}=(E\cup
F)\setminus\\{e_{1},\dots,e_{k},d_{1},\dots,d_{k}\\}\cup\\{(v_{1},u_{1}),\dots,(v_{k},u_{k})\\}$

All lower bounds we prove in this paper are based on the Strong Exponential
Time Hypothesis. But instead of using the original statement we use a
formulation which is more useful to work with.

######  Conjecture 2.4 (Strong Exponential Time Hypothesis (SETH) [8, 29]).

For all $\delta>0$, there is a $k\geq 3$ such that satisfiability of $k$-CNF
formulas on $n$ variables requires more than $(2-\delta)^{n}$ time.

###### Treewidth and Pathwidth.

We use the standard definition of a tree decomposition to define treewidth, as
for example given in Chapter 7 of [15]. A tree decomposition of a undirected
graph $G$ is a pair $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$, where $T$ is a
tree, and every node $t$ of $T$ 333We refer to the vertices of $T$ as _nodes_
, to distinguish them from the vertices of $G$. is assigned a _bag_
$X_{t}\subseteq V(G)$, such that

  * •

Every vertex of $G$ is contained in at least one bag: $\bigcup_{t\in
V(T)}X_{t}=V(G)$.

  * •

For every $(u,v)\in E(G)$, there exists a node $t$ of $T$ such that $X_{t}$
contains both $u$ and $v$.

  * •

For every $u\in V(G)$, the nodes whose corresponding bags contain $u$, i.e.
$T_{u}=\\{t\in V(T)\mid u\in X_{t}\\}$, induces a connected subtree of $T$.

The _width_ of the tree decomposition is $\max_{t\in V(T)}\lvert
X_{t}\rvert-1$, i.e. the maximum size of the bags minus 1. The minimum
possible width of a tree decomposition of a graph $G$ defines the _treewidth_
${\operatorname{tw}}(G)$ of $G$. The path decomposition leading to pathwidth
${\operatorname{pw}}(G)$ uses the same definition, except that we require that
$T$ is a path.

We use nice tree decompositions as they help in simplifying algorithms; more
precisely, we use a variant of nice decompositions with introduce edge nodes.
They are defined by a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ and additionally one vertex $r$ of $T$ which serves as the root of
$T$. This rooted tree decomposition $\mathcal{T}$ is _nice_ if the bag of the
root is empty, i.e. $X_{r}=\emptyset$, and all nodes $t$ of $T$ have one of
the following types:

  * •

Leaf node: $t$ has no children and the bag is empty, i.e. $X_{t}=\emptyset$.

  * •

Introduce vertex node: $t$ has a unique child $t^{\prime}$ with
$X_{t}=X_{t^{\prime}}\cup\\{v\\}$ for some vertex $v\notin X_{t^{\prime}}$.

  * •

Introduce edge node: $t$ is labeled with an edge $(u,v)\in E(G)$ where $u,v\in
X_{t}$. Further $t$ has a unique child $t^{\prime}$ such that
$X_{t}=X_{t^{\prime}}$. We say, edge $(u,v)$ is introduced at $t$.

  * •

Forget node: $t$ has a unique child $t^{\prime}$ with
$X_{t}=X_{t^{\prime}}\setminus\\{w\\}$ for some vertex $w\in X_{t^{\prime}}$.

  * •

Join node: $t$ has exactly two children $t_{1}$ and $t_{2}$ such that
$X_{t}=X_{t_{1}}=X_{t_{2}}$.

Given a tree decomposition, it can efficiently be transformed into a nice tree
decomposition by increasing its size at most polynomially, [31]. Hence, we
always assume w.l.o.g. that a given tree decomposition is nice.

###### About Relations.

A relation $R\mathrel{\mathop{\mathchar
58\relax}}{\\{0,1\\}}^{k}\to{\\{0,1\\}}$ can also be seen as a set
$R^{\prime}\subseteq{\\{0,1\\}}^{k}$ such that $x\in R^{\prime}$ iff $R(x)=1$.
We can also identify $R$ with a set $R^{\prime\prime}\subseteq 2^{[k]}$, where
each element of $R^{\prime\prime}$ contains the positions of the 1s of an
accepted input. Precisely, $x^{\prime}=\\{i\mid x[i]=1\\}\in R^{\prime\prime}$
iff $R(x)=1$. We switch between these definitions depending on the context.
Recall, a relation is _symmetric_ if its output only depends on the Hamming
weight of its input.

To simplify notation, we introduce the following generic classes of symmetric
relations.

######  Definition 2.5.

For a vector $x\in{\\{0,1\\}}^{k}$, we define $\operatorname{hw}(x)$ as the
number of 1s in $x$, i.e. the Hamming weight of $x$. We define the following
for $S\subseteq{\mathbb{N}}$, and $i,j\in{\mathbb{N}}$:

$\mathtt{HW}_{\in
S}^{(j)}\coloneqq\\{x\in{\\{0,1\\}}^{j}\mid\operatorname{hw}(x)\in
S\\}\qquad\mathtt{EQ}_{j}\coloneqq\mathtt{HW}_{\in\\{0,j\\}}^{(j)}\qquad\mathtt{HW}_{=i}^{(j)}\coloneqq\mathtt{HW}_{\in\\{i\\}}^{(j)}$

$\mathtt{EQ}_{j}$ is the _equality_ relation on $j$ inputs. We use
$\mathtt{HW}_{\in S}$ to denote $\mathtt{HW}_{\in S}^{(j)}$ when the arity $j$
of the relation is implicit. We also use this as the set of the relations
$\mathtt{HW}_{\in S}^{(j)}$ for all $j\in{\mathbb{N}}$. We transfer this abuse
of notation to $\mathtt{HW}_{=i}$.

Note that assigning the relations $\mathtt{HW}_{\in B}$ to a vertex
corresponds to assigning the set $B$ to the vertex. Which notation is used
depends on the context we are in.

##  3 Algorithms

In this section we present two algorithms for GenFac parameterized by
treewidth and cutwidth, respectively. By our lower bounds for $B$-Factor we
know that these algorithms are (conditionally) optimal for both problems. This
is somewhat surprising as the intuitive feeling would be that we can exploit
that the graphs are $B$-homogeneous for $B$-Factor.

Let $G$ be the given graph in the following and let
$B_{v}\subseteq{\mathbb{N}}$ be the label of vertices $v\in V(G)$. We can
assume $B_{v}\subseteq\\{0,\dots,\lvert V(G)\rvert\\}$. Then, let
$M=\max_{v\in V}\max B_{v}$ in the following.

###  3.1 Algorithm when Parameterizing by Treewidth

Assuming a tree decomposition of width ${\operatorname{tw}}$ is given,
Arulselvan et al. showed implicitly that GenFac can be solved in time
$(M+1)^{3{\operatorname{tw}}}n^{\mathcal{O}(1)}$ [1]. We base our optimal
$(M+1)^{{\operatorname{tw}}}n^{\mathcal{O}(1)}$ algorithm for counting
solutions of a certain size on this approach and combine it with a more
precise runtime analysis and fast convolution techniques. As for other
algorithms parameterized by treewidth we also assume that a tree decomposition
is given as input. This is reasonable as it allows studying the problem
independently from finding a decomposition.

####  3.1.1 Algorithm

Let $k$ be the width of the given tree decomposition where every edge is
introduced exactly once. For a node $t$ in the tree decomposition let $X_{t}$
be the corresponding bag of vertices. We define $V_{t}$ to be the set of
vertices and $E_{t}$ to be the set of edges introduced in the subtree rooted
at $t$.

For a fixed node $t$ let $f\mathrel{\mathop{\mathchar 58\relax}}X_{t}\to[0,n]$
and $s\in[0,m]$ where $m$ is the number of edges of $G$. We define $c[t,f,s]$
to be the number of sets $F \subseteq E_{t}$ with $\lvert F\rvert=s$ such that
$\deg_{F}(v)=f(v)$ for all $v\in X_{t}$ and $\deg_{F}(v)\in B_{v}$ for all
$v\in V_{t}\setminus X_{t}$.

As the bag of the root $r$ is empty, only the empty assignment is valid and
hence the value of $c[r,\emptyset,s]$ corresponds to the number of solutions
of size exactly $s$ for all $s\in[0,m]$. For all other $s$ the number of
solutions is $0$.

The following dynamic program computes all entries of $c$ and its behavior is
completely determined by the type of the node $t$ it currently visits.

Leaf node

We have $X_{t}=\emptyset$ and set $c[t,\emptyset,0]\coloneqq 1$ and 0 for all
other entries.

Introduce Vertex Node

Let $t^{\prime}$ be the unique child of $t$ such that
$X_{t}=X_{t^{\prime}}\cup\\{v\\}$. Let $f|_{X_{t^{\prime}}}$ be the
restriction of $f$ to domain $X_{t^{\prime}}$. That is
$f|_{X_{t^{\prime}}}\mathrel{\mathop{\mathchar
58\relax}}X_{t^{\prime}}\to[0,n]$ and $f|_{X_{t^{\prime}}}(x)=f(x)$ for all
$x\in X_{t^{\prime}}$. We set

$c[t,f,s]\coloneqq\begin{cases}c[t^{\prime},f|_{X_{t^{\prime}}},s]&\text{if
}f(v)=0\\\ 0&\text{else}\end{cases}$

Introduce Edge Node

Let $(u,v)$ be the edge introduced at node $t$. We have to decide whether to
pick the edge or not. As the edge can only be chosen if the degree of the
vertices $u$ and $v$ is not zero, we define:

$c[t,f,s]\coloneqq c[t^{\prime},f,s]+\begin{cases}c[t^{\prime},f_{u\mapsto
f(u)-1,v\mapsto f(v)-1},s-1]&\text{if }f(u)f(v)>0\\\ 0&\text{else}\end{cases}$

Forget Node

Let $t^{\prime}$ be the child of $t$ such that
$X_{t}=X_{t^{\prime}}\setminus\\{v\\}$. Then we set:

$c[t,f,s]\coloneqq\sum_{d\in B_{v}}c[t^{\prime},f_{v\mapsto d},s]$

Join Node

Let $t_{1}$ and $t_{2}$ be the left and right child of $t$ such that
$X_{t}=X_{t_{1}}=X_{t_{2}}$. For three functions
$f,f_{1},f_{2}\mathrel{\mathop{\mathchar 58\relax}}X_{t}\to[0,n]$ we write
$f_{1}+f_{2}=f$ if we mean $f_{1}(v)+f_{2}(v)=f(v)$ for all $v\in X_{t}$.
Based on this, we can define the values of the table as follows:

$c[t,f,s]\coloneqq\sum_{\begin{subarray}{c}f_{1},f_{2}\text{ s.t.}\\\
f_{1}+f_{2}=f\end{subarray}}\sum_{s_{1}+s_{2}=s}c[t_{1},f_{1},s_{1}]\cdot
c[t_{2},f_{2},s_{2}]$

Observe that for this to work we crucially need that each edge is introduced
exactly once in the whole decomposition. Otherwise the edge could be picked in
both subtrees leading to a wrong solution since it could be counted twice. But
by assumption each edge is either contained in the tree rooted at $t_{1}$ or
$t_{2}$ or neither of them and thus above $t$.

###### Running Time.

One can simply observe that each entry of the table can be computed in time
$\max\\{\mathcal{O}(1),M,(n+1)^{2k+2}m^{2}\\}$. But we can actually restrict
the codomain of $f$ to $[0,M]$ and it suffices for the join node to pick
$f_{1}$ and $s_{1}$ as $f_{2}$ and $s_{2}$ then follow from the equations
$f_{1}+f_{2}=f$ and $s_{1}+s_{2}=s$, respectively. Hence, each cell can be
computed in time $\mathcal{O}((M+1)^{k+1}m)$. Since for each node there are at
most $(M+1)^{k+1}$ many valid functions $f$, the problem can be solved in time
$(M+1)^{2k}n^{\mathcal{O}(1)}$. In the next section we show how to improve the
running time of the join node by computing all values in parallel.

####  3.1.2 Improving the Running Time

For the improved computation of the join node we make use of the concepts and
ideas from van Rooij [45] including the following lemma:

######  Lemma 3.1 (Lemma 3 in [45] (cyclic and non-cyclic convolution)).

Let
$N={\mathbb{N}}_{<q_{1}}\times{\mathbb{N}}_{<q_{2}}\times\dots\times{\mathbb{N}}_{<q_{l}}$,
and let $Q=\prod_{i=1}^{l}q_{i}$. 444We set
${\mathbb{N}}_{<r}=\\{0,\dots,r-1\\}$. Let
$Z={\mathbb{Z}}_{r_{1}}\times{\mathbb{Z}}_{r_{1}}\times\dots\times{\mathbb{Z}}_{r_{k}}$,
and let $R=\prod_{i=1}^{k}r_{i}$.

Let $f,g\mathrel{\mathop{\mathchar 58\relax}}Z\times N\to{\mathbb{F}}_{p}$,
where $p$ is chosen appropriately. And, let $h\mathrel{\mathop{\mathchar
58\relax}}Z\times N\to{\mathbb{F}}_{p}$ be the combined (partially cyclic and
partially non-cyclic) convolution of $f$ and $g$ defined as:

$h(x,i)=\sum_{y_{1}+y_{2}\equiv
x}\sum_{j_{1}+j_{2}=i}f(y_{1},j_{1})g(y_{2},j_{2})$

where the sum $y_{1}+y_{2}\equiv x$ is evaluated component-wise modulo $r_{i}$
at coordinate $i$ (sum in $Z$), and the sum $j_{1}+j_{2}=i$ is evaluated
component-wise without modulus (sum in $N$). Then, the combined convolution
$h$ can be computed in $\mathcal{O}(RQ2^{l}(\log(R)+\log(Q)+l))$ arithmetic
operations.

The obvious way of using the lemma would be to directly use the non-cyclic
part of the convolution. But this would result in $Q=(M+1)^{k+1}(m+1)$ and
$l=k+2$, which gives us a bound of $(M+1)^{k}2^{k}n^{\mathcal{O}(1)}$. Instead
we mainly use the cyclic part of the convolution and add a degree bound in the
non-cyclic part such that we only consider correct combinations of values.

######  Lemma 3.2.

For each join-node $t$ of the tree decomposition, we can compute $c[t,f,s]$
for all valid $f$ and all $s\in[0,m]$ with
$\mathcal{O}((M+1)^{k}k^{2}Mm\log(Mm))$ arithmetic operations.

######  Proof 3.3.

We follow the ideas of the proof of Lemma 10 in [45]. Let $t_{1}$ and $t_{2}$
be the two children of node $t$. Since $\lvert X_{t}\rvert\leq k+1$, we can
transform each function $f\mathrel{\mathop{\mathchar 58\relax}}X_{t}\to[0,M]$
into a vector in $[0,M]^{k+1}$ (and vice versa if we add dummy vertices to
$X_{t}$).

Based on this we define $a,b\mathrel{\mathop{\mathchar
58\relax}}[0,M]^{k+1}\times{\mathbb{N}}\times[0,m]\to{\mathbb{F}}_{p}$ where
$p>2^{\lvert E\rvert}$ since there can be at most that many edge subsets of
the graph $G$. We define:

$a(f,F,s)\coloneqq\begin{cases}c[t_{1},f,s]&\text{if
}\mathinner{\\!\mathopen{}\left\lVert f\right\rVert\mathclose{}}_{1}=F\\\
0&\text{else}\end{cases}\quad\text{ and }\quad
b(f,F,s)\coloneqq\begin{cases}c[t_{2},f,s]&\text{if
}\mathinner{\\!\mathopen{}\left\lVert f\right\rVert\mathclose{}}_{1}=F\\\
0&\text{else}\end{cases}$

Where we set $\mathinner{\\!\mathopen{}\left\lVert
f\right\rVert\mathclose{}}_{1}=\sum_{v\in X_{t}}f(v)$, where the sum is over
the integers (without modulo). Hence, it actually suffices to restrict
${\mathbb{N}}$ in the definition of $a$ and $b$ to
${\mathbb{N}}_{\leq(k+1)M}$. We use this to compute the following convolution
for all $f\in[0,M]^{k+1}$, $F\in[0,(k+1)M]$, and $s\in[0,m]$.

$c(f,F,s)=\sum_{f_{1}+f_{2}\equiv f}\sum_{\begin{subarray}{c}F_{1}+F_{2}=F\\\
s_{1}+s_{2}=s\end{subarray}}a(f_{1},F_{1},s_{1})b(f_{2},F_{2},s_{2})$

Then we set $c[t,f,s]=c(f,\mathinner{\\!\mathopen{}\left\lVert
f\right\rVert\mathclose{}}_{1},s)$ for all $f$ and $s$ to complete the
computation for this join-node.

Again the computation of $f_{1}+f_{2}\equiv f$ is component wise modulo $M+1$
and for $F_{1}+F_{2}=F$ and $s_{1}+s_{2}=s$ over the integers without modulo.
By the definition of $a$ and $b$ we only sum values if
$\mathinner{\\!\mathopen{}\left\lVert f_{i}\right\rVert\mathclose{}}=F_{i}$.
Thus we actually just sum over all values $f_{1},f_{2}$ such that
$f_{1}+f_{2}\bm{=}f$ because otherwise we would get that
$\mathinner{\\!\mathopen{}\left\lVert
f_{1}\right\rVert\mathclose{}}_{1}+\mathinner{\\!\mathopen{}\left\lVert
f_{2}\right\rVert\mathclose{}}_{1}>\mathinner{\\!\mathopen{}\left\lVert
f\right\rVert\mathclose{}}_{1}$. We can directly apply Lemma 3.1 with $l=2$,
$q_{1}=(k+1)M+1$, $q_{2}=m+1$, and $r_{1}=\dots=r_{k+1}=M+1$. As
$Q=(kM+M+1)(m+1)$ and $R=(M+1)^{k+1}$ the claimed running time follows.

It is easy to see that the computation of the join nodes dominates the running
time. Therefore, the proof of this lemma finishes the proof of Theorem 1.3.

###  3.2 Algorithm when Parameterizing by Cutwidth

Assume we are given a linear layout of the GenFac instance $G$. We relabel the
vertices such that their index corresponds to this layout. Let $C_{i}$ be the
edges of the graph that cross the cut after vertex $v_{i}$, that is
$C_{i}=E\cap(\\{v_{1},\dots,v_{i}\\}\times\\{v_{i+1},\dots,v_{n}\\})$. We
define $\delta^{+}_{i}=C_{i}\cap I(v_{i})$ as the forwards edges of $v_{i}$,
i.e. the edges to vertices in $\\{v_{i+1},\dots,v_{n}\\}$ and likewise
$\delta^{-}_{i}=C_{i-1}\cap I(v_{i})$ as the backwards edges of $v_{i}$. Let
$E_{i}=E|_{v_{1},\dots,v_{i}}$ be the edges induced by the vertices
$v_{1},\dots,v_{i}$. We additionally define $\widehat{C}_{i}$ as the set of
edges in the cuts $C_{i-1}$ and $C_{i}$ that are not incident to $v_{i}$, i.e.
$\widehat{C}_{i}=C_{i-1}\setminus\delta^{-}_{i}=C_{i}\setminus\delta^{+}_{i}$.
See Figure 2 for an illustration of the setting.

Figure 2: Illustration how the different sets are related to each other.

The idea of the algorithm is to fill a three-dimensional table $c$ such that
for all $i\in[0,n]$, $s\in[0,m]$, and $C\subseteq 2^{C_{i}}$ we have that
$c[i,C,s]$ is the number of sets $S\subseteq E_{i}$ with $\lvert S\rvert=s$
such that $\deg_{S}(v_{j})+\deg_{C}(v_{j})\in B_{v_{j}}$ for all $j\in[i]$.
Phrased differently: the number of possibilities to extend the selected edges
of the cut to a valid partial solution for the first $i$ vertices.

As the cut after $v_{n}$ does not contain any edges, we only have to consider
the empty set. Hence, the output of the algorithm is the value of
$c[n,\emptyset,s]$ for $s\in[0,m]$ and 0 otherwise.

It remains to show how we can compute the values of the table efficiently. We
initialize the table with $c[0,\emptyset,0]=1$ and 0 at all other positions.
Then we design a step function that computes the values of $c[i,\cdot,\cdot]$
given the values of $c[i-1,\cdot,\cdot]$. We first show a naive way for this
and then improve the computation to get the algorithm with optimal running
time.

####  3.2.1 Naive Step Function

For all $C\subseteq C_{i}$ and $s\in[0,m]$ we compute the value sequentially
as follows:

$c[i,C,s]=\sum_{\begin{subarray}{c}S^{-}\subseteq\delta^{-}_{i}\text{ s.t.}\\\
\lvert S^{-}\rvert+\deg_{C}(v_{i})\in
B_{v_{i}}\end{subarray}}c[i-1,C\setminus\delta^{+}_{i}\cup S^{-},s-\lvert
S^{-}\rvert]$

For each $i$ we have to compute $\mathcal{O}(2^{\operatorname{cutw}}(m+1))$
table entries. Each of the entries can be computed in time
$2^{\operatorname{cutw}}n^{\mathcal{O}(1)}$ as we iterate over all subsets of
$\delta^{-}_{i}$. This gives us a total running time of
$4^{\operatorname{cutw}}n^{\mathcal{O}(1)}$.

####  3.2.2 Improved Step Function

For the improved algorithm we make use of the fact that for the computation of
$c[i,\cdot,\cdot]$ only the selected edges in $\delta^{-}_{i}$ and the
_number_ of selected edges from $\delta^{+}_{i}$ are of interest. The edges in
$\widehat{C}_{i}$ are not affected as $v_{i}$ moves to the other side of the
cut. Further observe that we can partition $C\subseteq C_{i}$ into
$C=\widehat{C}\mathrel{\dot{\cup}}S^{+}$ for $S^{+}\subseteq\delta^{+}_{i}$
and $\widehat{C}\subseteq\widehat{C}_{i}$. We transform the naive formula from
above as follows:

$\displaystyle c[i,C,s]$
$\displaystyle=c[i,\widehat{C}\mathrel{\dot{\cup}}S^{+},s]$
$\displaystyle=\sum_{\begin{subarray}{c}S^{-}\subseteq\delta^{-}_{i}\text{
s.t.}\\\ \lvert
S^{-}\rvert+\deg_{\widehat{C}\mathrel{\dot{\cup}}S^{+}}(v_{i})\in
B_{v_{i}}\end{subarray}}c[i-1,(\widehat{C}\mathrel{\dot{\cup}}S^{+})\setminus\delta^{+}_{i}\cup
S^{-},s-\lvert S^{-}\rvert]$
$\displaystyle=\sum_{\begin{subarray}{c}S^{-}\subseteq\delta^{-}_{i}\text{
s.t.}\\\ \lvert S^{-}\rvert+\lvert S^{+}\rvert\in
B_{v_{i}}\end{subarray}}c[i-1,\widehat{C}\cup S^{-},s-\lvert S^{-}\rvert]$
$\displaystyle=h[\lvert S^{+}\rvert,\widehat{C},s]$ where: $\displaystyle
h[\ell,\widehat{C},s]$
$\displaystyle=\sum_{\begin{subarray}{c}S^{-}\subseteq\delta^{-}_{i}\text{
s.t.}\\\ \lvert S^{-}\rvert+\ell\in
B_{v_{i}}\end{subarray}}c[i-1,\widehat{C}\cup S^{-},s-\lvert S^{-}\rvert]$

The improved step function now works as follows:

  1. 1.

Initialize the auxiliary table $h$ with 0s.

  2. 2.

Use the above formula to fill $h$ for all
$\widehat{C}\subseteq\widehat{C}_{i}$, $s\in[0,m]$, and $\ell\in[0,M]$. This
takes time
$2^{\lvert\widehat{C}_{i}\rvert}(M+1)2^{\lvert\delta^{-}_{i}\rvert}n^{\mathcal{O}(1)}\leq
2^{\lvert C_{i-1}\rvert}n^{\mathcal{O}(1)}$.

  3. 3.

For all $\widehat{C}\subseteq\widehat{C}_{i}$, $s\in[0,m]$, and
$S^{+}\subseteq\delta^{+}_{i}$, we set $c[i,\widehat{C}\cup S^{+},s]\coloneqq
h[\lvert S^{+}\rvert,\widehat{C},s]$. This takes time
$2^{\lvert\widehat{C}_{i}\rvert}2^{\lvert\delta^{+}_{i}\rvert}n^{\mathcal{O}(1)}\leq
2^{\lvert C_{i}\rvert}n^{\mathcal{O}(1)}$.

Hence, we can bound the running time of each round by
$2^{\operatorname{cutw}}Mn^{\mathcal{O}(1)}$.

##  4 Lower Bound when Parameterizing by Pathwidth

We show the lower bounds in two steps. The first step is a reduction from CNF-
SAT to the intermediate problem $B$-Factor with Relations. In the second step,
we reduce to the actual version of $B$-Factor for which we want to show the
lower bound. As the lower bounds are for pathwidth they immediately hold for
treewidth as it can be upper-bounded by pathwidth for all graphs.

######  Definition 4.1 ($B$-Factor with Relations ($B$-FactorR)).

Let $B\subseteq{\mathbb{N}}$ be fixed of finite size.
$G=(V_{S}\mathrel{\dot{\cup}}V_{C},E)$ is an instance of _$B$ -Factor with
Relations_ if all nodes in $V_{S}$ are labeled with set $B$ and all nodes
$v\in V_{C}$ are labeled with a relation $R_{v}$ that is given as a truth
table such that the following holds:

  1. 1.

Let $I(v)$ be the set of edges incident to $v$ in $G$. Then $R_{v}\subseteq
2^{I(v)}$.

  2. 2.

There is an even $c_{v}>0$ such that for all $x\in R_{v}$ we have
$\operatorname{hw}(x)=c_{v}$.

A set $\widehat{E}\subseteq E$ is a _solution_ for $G$ if (1) for $v\in
V_{S}$: $\deg_{\widehat{E}}(v)\in B$ and (2) for $v\in V_{C}$:
$I(v)\cap\widehat{E}\in R_{v}$. $B$-FactorR is the problem of deciding if such
an instance has a solution.
We call $V_{S}$ the set of _simple_ nodes and $V_{C}$ the set of _complex_
nodes.

Using this intermediate problem, we can formally state the first part of the
reduction. The lower bound needs a careful formulation: when we reduce
$B$-FactorR to $B$-Factor by inserting gadgets realizing the relations at the
complex nodes, the size and pathwidth of the graph can increase significantly.
Therefore, we state a stronger lower bound that can tolerate additional terms
to take care of such increases. The key point is that this increase is mainly
influenced by the total degree of the complex nodes in a bag of the path
decomposition.

######  Theorem 4.2.

Let $B\subseteq{\mathbb{N}}$ be a fixed set of finite size with
$B\neq\\{0\\}$. Given a $B$-FactorR instance along with a path decomposition
of width ${\operatorname{pw}}$ such that $\Delta^{*}=\max_{\text{bag
}X}\sum_{v\in X\cap V_{C}}\deg(v)$. Assume $B$-FactorR can be solved in $(\max
B+1-\epsilon)^{{\operatorname{pw}}+f_{B}(\Delta^{*})}n^{\mathcal{O}(1)}$ time
on graphs with $n$ vertices for some $\epsilon>0$ and some function
$f_{B}\mathrel{\mathop{\mathchar 58\relax}}{\mathbb{N}}\to{\mathbb{R}}^{+}$
that may depend on the set $B$. Then SETH fails.

###### High Level Idea.

We follow the ideas of previous lower bound reductions from [36] and combine
them with the concept of using relations from [13]. From now on let
$M\coloneqq\max B$. Let $\phi$ be the given CNF formula with $n$ variables and
clauses $C_{1},\dots,C_{m}$. Instead of encoding each variable separately, we
group $q$ variables together and encode (partial) assignments to these groups.
For each partial assignment, we define a vector in $[0,M]^{g}$, where $g$ is
chosen such that $2^{q}\leq(M+1)^{g}$. For each group we define a _layer_ with
$g$ parallel _rows_ , where each row corresponds to one dimension of the
vector. The layers consist of an alternation of $g$ parallel simple nodes and
a complex node that is related to a clause. All simple nodes are connected to
their neighboring complex nodes by $M$ parallel edges. The vector from above
then corresponds to the number of selected edges from a simple node to the
following shared complex node. The complex nodes check whether the assignment
represented by the selected edges of a layer satisfies the related clause. For
each clause we connect the related complex nodes by a path. This path is used
to propagate the information whether the clause is already satisfied by some
partial assignment or whether it still needs to be satisfied. We ensure that
each clause is initially not satisfied and eventually all clauses must be
satisfied.

Figure 3: An example illustrating the construction from the proof of Theorem
4.2. The simple nodes are represented by circles while the complex nodes are
represented by boxes.

###### Constructing the $B$-FactorR Instance.

See Figure 3 for an example of the following construction. Split the variables
of $\phi$ into $t\coloneqq\lceil n/q\rceil$ groups $F_{1},\dots,F_{t}$ of size
at most $q$, where $q$ is chosen later. For each of the $t$ groups we encode
the $2^{q}$ partial assignments by vectors from $[0,M]^{g}$ for some $g$
chosen later. Instead of using all $(M+1)^{g}$ possible encodings we only use
those vectors where the total weight of the coordinates is equal to $gM/2$ (we
will choose $g$ as a multiple of 4, hence $gM/2$ is an even number). It can
easily be shown that there are more than $(M+1)^{g}/(gM+1)$ vectors with
exactly this weight. Thus, after setting
$q=\lfloor\log((M+1)^{g})-\log(gM+1)\rfloor$, we can map each of the $2^{q}$
assignments of a group $F_{i}$ to a distinct vector $[0,M]^{g}$ with weight
exactly $gM/2$. We say that an partial assignment $\tau$ to a group $F_{i}$
satisfies a clause $C_{j}$ if at least one literal in the clause is satisfied
under the assignment $\tau$. Note, that a group $F_{i}$ does not have to cover
all variables of $C_{j}$ to satisfy the clause.

We define the graph now as follows:

  1. 1.

For all $i\in[t]$, $\ell\in[g]$, and $j\in[m]$: create a simple node
$J_{i,\ell}^{j}$.

  2. 2.

For all $i\in[t]$ and $j\in[m]$: create complex nodes $r_{i}^{j}$ with
relation $R_{i}^{j}$ to be defined later.

  3. 3.

For all $i\in[t]$: create complex nodes $r_{i}^{0}$ and $r_{i}^{m+1}$ with
relation $R^{0}$.

  4. 4.

For all $j\in[m]$: create complex nodes $r_{0}^{j}$ (resp. $r_{t+1}^{j}$) with
relation $\mathtt{HW}_{=0}$ (resp. $\mathtt{HW}_{=1}$).

  5. 5.

For all $i\in[t]$, $\ell\in[g]$, and $j\in[m]$: make $J_{i,\ell}^{j}$ adjacent
to $r_{i-1}^{j}$ and $r_{i}^{j}$ by $M$ parallel edges each. We call these
edges backwards and forwards edges, respectively.

  6. 6.

For all $i\in[t]$ and $j\in[m]$, make $r_{i}^{j}$ additionally adjacent to
$r_{i-1}^{j}$ and $r_{i+1}^{j}$ by one edge each. The degree of the nodes is
now $2gM+2$.

We call the set of nodes $\\{r_{i}^{j},J_{i,\ell}^{j}\\}_{j,\ell}$ the $i$th
_layer_. The set $\\{J_{i,\ell}^{j}\\}_{j}$ forms the $\ell$th _row_ of the
$i$th layer. For a fixed $j\in[m]$, the set of nodes $\\{r_{i}^{j}\\}_{i}$ is
called the $j$th _column_.

The idea is now the following: For each partial assignment $\tau$ to a group
$F_{i}$, we define a vector $v_{\tau}\in[0,M]^{g}$ of weight $gM/2$ as its
_encoding_.555Note that for different groups the encoding of the same partial
assignment do not need to be the same. Then $v_{\tau}[\ell]$ corresponds to
the number of selected forward edges of the simple nodes in the $\ell$th row
of the $i$th layer. The vertical edges encode whether a clause was already
satisfied. That is, if the edge between $r_{i}^{j}$ and $r_{i+1}^{j}$ is
selected, then there is some group $F_{k}$ with $k\leq i$ where the
corresponding assignment satisfies the clause $C_{j}$. By the relation of the
nodes $r_{0}^{j}$ every clause is initially not satisfied. But the relation of
the $r_{t+1}^{j}$ nodes ensures that every clause is eventually satisfied.

###### Defining the Relations.

$R^{0}$ accepts exactly those inputs of Hamming weight exactly $gM/2$, an even
number by assumption, where the selected edges for each row must precede the
unselected edges, i.e. the first $k$ edges are selected, the next $M-k$ are
not selected.

The relation $R_{i}^{j}\subseteq{\\{0,1\\}}^{2Mg+2}$ of node $r_{i}^{j}$ is
defined as follows:

  * •

For $\ell\in[g]$, let $x_{\ell}$ (resp. $y_{\ell}$) be the number of selected
incident edges to $J_{i,\ell}^{j}$ (resp. $J_{i,\ell}^{j+1}$).

  * •

$\sum_{\ell\in[g]}x_{\ell}=gM/2=\sum_{\ell\in[g]}y_{\ell}$.

  * •

$\langle x_{1},\dots,x_{g}\rangle$ describes a valid encoding, i.e. it
corresponds to a partial assignment for $F_{i}$.

  * •

$x_{\ell}+y_{\ell}=M$. Further, the $x_{\ell}$ (resp. $y_{\ell}$) selected
edges precede the $M-x_{\ell}$ (resp. $M-y_{\ell}$) unselected edges of the
$M$ parallel edges going to a simple node.

  * •

If the ingoing top edge is selected, then the outgoing bottom edge is also
selected.

  * •

If the ingoing top edge is not selected:

    * –

If $C_{j}$ does not contain a variable of $F_{i}$, then the outgoing bottom
edge is not selected.

    * –

If $C_{j}$ contains at least one variable of $F_{i}$, then the outgoing bottom
edge is selected if and only if the selected edges correspond to a valid
partial assignment satisfying $C_{j}$.

###### Final Modifications.

Unfortunately the previous construction is not a $B$-FactorR instance. One
reason is that the Hamming weight of the accepted inputs of the relations
$R_{i}^{j}$ is not always the same even number. The misbalance is caused by
the edges encoding the evaluation of the clause. To avoid this problem, we add
another edge between all $r_{i}^{j}$ and $r_{i+1}^{j}$ nodes. We refer to this
new edge as the negated edge and to the original edge as the positive edge. We
further introduce nodes $\hat{r}_{0}^{j}$ and $\hat{r}_{t+1}^{j}$ with
relations $\mathtt{HW}_{=1}$ and $\mathtt{HW}_{=0}$ which are connected to
$r_{1}^{j}$ and $r_{t}^{j}$, respectively. Observe that the relations are
exactly opposite to the ones for the nodes $r_{0}^{j}$ and $r_{t+1}^{j}$. We
extend all relations $R_{i}^{j}$ by two new inputs and require that the
negated edge is selected if and only if the corresponding positive edge is not
selected. Then, the Hamming weight of the accepted inputs of the relations
$R_{i}^{j}$ is always the same, namely $gM+2$, which is an even number as
$gM/2$ is even by assumption. In a second step we merge the four nodes
$r_{0}^{j}$, $r_{t+1}^{j}$, $\hat{r}_{0}^{j}$, and $\hat{r}_{t+1}^{j}$ into a
single node $r^{j}$ of degree 4, for all $j\in[m]$. The relation of $r^{j}$
accepts only the unique input of weight 2 which agrees with the relations of
all four replaced nodes. We later show that the parallel edges disappear when
replacing the complex nodes by their realizations (the portal nodes of the
realization will be pairwise different). Nevertheless, if one wants to get a
simple graph, one can use five appropriately connected
$\mathtt{HW}_{=2}^{(4)}$ nodes to replace one such edge. We leave it to the
reader to find the gadget. Almost all of these modification are only necessary
due to parity issues. As they are in most cases not relevant for the
correctness of the construction, we mostly ignore them in our proofs in the
following.

######  Lemma 4.3.

If $\phi$ is satisfiable, then there is a solution to the $B$-FactorR
instance.

######  Proof 4.4.

Let $\sigma$ be a satisfying assignment to the variables of $\phi$. For fixed
variable group $F_{i}$, let $v_{i}\in[0,M]^{g}$ be the encoding that
corresponds to $\sigma$ when restricted to $F_{i}$. For the solution we select
the edges as follows: In the $\ell$th row of the $i$th layer we select the
$v_{i}[\ell]$ top most forwards edges of the simple nodes and the
$M-v_{i}[\ell]$ top most backwards edges. By this obviously every simple node
is incident to $M$ selected edges and the conditions of the relations $R^{0}$
are satisfied.

Now consider a fixed clause $C_{j}$. Let $F_{k}$ be the first (with regard to
$k$) group of variables whose partial assignment satisfies the clause. Then we
do not select the edges between $r_{i-1}^{j}$ and $r_{i}^{j}$ for all
$i\in[k]$. Combined with the valid encoding from above, the relations of these
nodes are now satisfied. As the encoding precisely corresponds to the
assignment satisfying the clause, we select the edges between the nodes
$r_{i}^{j}$ and $r_{i+1}^{j}$ for all $i\geq k$. Then all relations are
satisfied and the claim follows.

######  Lemma 4.5.

If there is a solution to the $B$-FactorR instance, then $\phi$ is
satisfiable.

######  Proof 4.6.

Let $S\subseteq E$ be a solution. We construct an assignment $\sigma$ by
assigning values to the variables of each group $F_{i}$ independently. For
this fix some $i\in[t]$.

For $\ell\in[g]$, let $x_{\ell}^{1},\dots,x_{\ell}^{m+1}$ and
$y_{\ell}^{1},\dots,y_{\ell}^{m+1}$ be the number of selected forwards and
backwards edges of the nodes $J_{i,\ell}^{j}$, respectively. We claim that the
number of selected forwards edges does not change for a fixed row
$\ell\in[g]$:

######  Claim 1.

$x_{\ell}^{1}=\dots=x_{\ell}^{m+1}$ and $y_{\ell}^{1}=\dots=y_{\ell}^{m+1}$.

By the construction of the graph and the definition of the relations we get:

$\displaystyle y_{\ell}^{j+1}+x_{\ell}^{j}$ $\displaystyle=M$
$\displaystyle\forall\ell\in[g],j\in[m]$ (1) $\displaystyle
y_{\ell}^{j}+x_{\ell}^{j}$ $\displaystyle\leq M$
$\displaystyle\forall\ell\in[g],j\in[m+1]$ (2)
$\displaystyle\sum_{\ell=1}^{g}x_{\ell}^{m+1}$
$\displaystyle=\frac{gM}{2}=\sum_{\ell=1}^{g}y_{\ell}^{1}$ (3) Combining (1)
and (2) gives us: $\displaystyle x_{\ell}^{j}$ $\displaystyle\geq
x_{\ell}^{j+1}$ $\displaystyle\forall j\in[m]$ (4) $\displaystyle
y_{\ell}^{j}$ $\displaystyle\leq y_{\ell}^{j+1}$ $\displaystyle\forall
j\in[m]$ (5)

Now assume for contradictions sake that there is some $j^{\prime}$ with
$x_{\ell}^{j^{\prime}}>x_{\ell}^{j^{\prime}+1}$:

$\frac{gM}{2}\overset{(3)}{=}\sum_{\ell=1}^{g}x_{\ell}^{m+1}\overset{(4)}{\leq}\sum_{\ell=1}^{g}x_{\ell}^{j^{\prime}+1}<\sum_{\ell=1}^{g}x_{\ell}^{j^{\prime}}\overset{(4)}{\leq}\sum_{\ell=1}^{g}x_{\ell}^{1}\overset{(2)}{\leq}\sum_{\ell=1}^{g}(M-y_{\ell}^{1})=gM-\sum_{\ell=1}^{g}y_{\ell}^{1}\overset{(3)}{=}\frac{gM}{2}$

which is obviously a contradiction. This proves the claim as we can use the
analogous argument for the backwards edges. Observe that this implies that all
simple nodes have degree exactly $M$ in the solution.

Since $S$ is a solution, the relation $R_{i}^{j}$ must be satisfied. Thus,
$\langle x_{1}^{1},\dots,x_{g}^{1}\rangle$ must correspond to a valid encoding
of some assignment for $F_{i}$. We use this partial assignment for $\sigma$.

To show that $\sigma$ satisfies all clauses let $C_{j}$ be an arbitrary
clause. As $S$ is a solution, the relations of the nodes $r_{0}^{j}$ and
$r_{t+1}^{j}$ must be satisfied by $S$. By definition of the relations
$R_{i}^{j}$, there must be a $i_{j}$ and a node $r_{i_{j}}^{j}$ where the top
edge is not selected but the bottom edge is selected. By definition of the
relation, this change can only happen if the selected incident forwards edges
describe an encoding which corresponds to an assignment satisfying $C_{j}$. By
1 this number of selected edges is always the same. Hence, the assignment
represented by the selected edges that are incident to $r_{i}^{j}$ agrees with
the assignment we chose for $\sigma$.

To obtain a tight lower bound, we need to analyze the pathwidth of our
construction and have to bound the degree of the complex nodes.

######  Lemma 4.7.

The graph has $\mathcal{O}(tgm)$ simple and $\mathcal{O}(tm)$ complex nodes.
The degree of the complex nodes is bounded by $2gM+4$. The degree of the
simple nodes is bounded by $2M$. We can efficiently construct a path
decomposition of width $tg+\mathcal{O}(1)$ where at most three complex nodes
are simultaneously in one bag.

######  Proof 4.8.

The number of nodes and their degree bound follows immediately from the
construction. We give a mixed search strategy as shown in [15] to create a
path decomposition of the graph.

We start by placing searchers on each node $J_{i,\ell}^{1}$ for $i\in[t]$ and
$\ell\in[g]$. We place a searcher on each $r_{i}^{0}$ and remove it
immediately afterwards. Then we clean the rest of the graph in stages,
starting with stage 1. Stage $j$ starts if the searchers are placed on the
nodes $J_{i,\ell}^{j}$. First place two searcher on $r^{j}$ and $r_{1}^{j}$.
Then we move the searchers placed on the adjacent simple nodes of $r_{1}^{j}$
to the next simple node of the row. Then place one searcher on $r_{2}^{j}$ and
repeat the process after removing the one from $r_{1}^{j}$. Repeat this
procedure for all other nodes $r_{i}^{j}$. When removing the searcher from
$r_{t}^{j}$, we also remove the searcher from $r^{j}$. By this we eventually
arrive at a point where all searchers are located at the nodes
$J_{i,\ell}^{m+1}$. Then we use one additional searchers to clean the
remaining $r_{i}^{m+1}$ nodes.

Now we have everything ready to prove the lower bound for the intermediate
problem $B$-FactorR based on the previous construction. Recall, we defined
$\Delta^{*}$ as the maximum total degree of the complex nodes appearing in one
bag, that is $\Delta^{*}=\max_{\text{bag }X}\sum_{v\in X\cap V_{C}}\deg(v)$.

######  Proof 4.9 (Proof of Theorem 4.2).

Assume an
$(M+1-\epsilon)^{{\operatorname{pw}}+f(\Delta^{*})}N^{\mathcal{O}(1)}$ time
algorithm for $B$-FactorR on graphs with $N$ nodes exists for some function
$f$. Due to rounding issues and the fact that we only use even relations, the
parameters must be chosen quite carefully. We set
$\lambda\coloneqq\log_{M+1}(M+1-\epsilon)<1$. Choose an $\alpha>1$ such that
$\alpha\cdot\lambda=\delta^{\prime}=\log(2-\delta)<1$ for some $\delta>0$.
This is always possible since $\lambda<1$. Choose $g$ large enough such that
$g\log(M+1)\leq\alpha\lfloor g\log(M+1)-\log(gM+1)\rfloor$ and $g$ is
divisible by 4. By Lemma 4.7 and our choice of parameters ($t=\lceil
n/q\rceil$ and $q=\lfloor g\log(M+1)-\log(gM+1)\rfloor$) we get:

$\displaystyle(M+1-\epsilon)^{{\operatorname{pw}}+f(\Delta^{*})}N^{\mathcal{O}(1)}=(M+1-\epsilon)^{tg+\mathcal{O}(1)+f(\Delta^{*})}N^{\mathcal{O}(1)}$
$\displaystyle=(M+1-\epsilon)^{\lceil\frac{n}{q}\rceil
g+f(\Delta^{*})}N^{\mathcal{O}(1)}=(M+1-\epsilon)^{\frac{n\cdot g}{\lfloor
g\log(M+1)-\log(gM+1)\rfloor}+g+\mathcal{O}(1)+f(\Delta^{*})}N^{\mathcal{O}(1)}$

Since $B$ is fixed, $M$ is constant. Further, $g$ only depends on $M$ and
$\epsilon$ and $N$ only depends on the number of variables $n$ and number of
clauses $m$ of the SAT instance. As $\Delta^{*}\in\mathcal{O}(gM)$, the factor
of $(M+1-\epsilon)^{\mathcal{O}(1)+g+f(\Delta^{*})}$ contributes only a large
constant (depending only on $M$ and $\epsilon$) to the overall running time
which can be hidden by the $n^{\mathcal{O}(1)}$ term:

$\displaystyle\leq(M+1-\epsilon)^{\frac{\alpha
n}{\log(M+1)}}(n+m)^{\mathcal{O}(1)}$
$\displaystyle=2^{\log(M+1-\epsilon)\frac{\alpha
n}{\log(M+1)}}(n+m)^{\mathcal{O}(1)}=2^{\lambda\alpha
n}(n+m)^{\mathcal{O}(1)}=2^{\delta^{\prime}n}(n+m)^{\mathcal{O}(1)}$
$\displaystyle=(2-\delta)^{n}(n+m)^{\mathcal{O}(1)}.$

This violates SETH (2.4) since this gives an algorithm to solve $k$-SAT with
$n$ variables and $m$ clauses in time $(2-\delta)^{n}(n+m)^{\mathcal{O}(1)}$
for some constant $\delta>0$ for all $k$.

For the lower bound for the counting version, we need a one-to-one
correspondence between valid assignments and solutions to the graph problem.
This is why we need that the selected edges are at specific positions, i.e.
above the not-selected edges.

######  Corollary 4.10.

The reduction in Theorem 4.2 is parsimonious, i.e. it preserves the number of
solutions. Therefore, the statement also holds for the counting versions of
$B$-FactorR and SETH.

We also make the following observations about the constructed $B$-FactorR
instances.

######  Corollary 4.11.

The lower bound proved in Theorem 4.2 holds even for $B$-FactorR instances
where

  1. 1.

the vertices in $V_{S}$ form an independent set,

  2. 2.

every vertex in $V_{S}$ is adjacent to exactly two vertices from $V_{C}$ by
$\max B$ edges each,

  3. 3.

and every vertex in $V_{S}$ will have degree exactly $\max B$ in the solution.

##  5 Decision Version

In this section we prove the lower bound for the decision version of
$B$-Factor by a reduction from the intermediate $B$-FactorR problem. For this
we formally define the concept of realizations and show that we can realize
all relations of a $B$-FactorR instance. Replacing the nodes and their
relations by these realizations yields the final lower bound.

######  Definition 5.1 (Realization).

Let $R\subseteq{\\{0,1\\}}^{k}$ be a relation. Let $G$ be a node-labeled graph
with dangling edges $D=\\{d_{1},\dots,d_{k}\\}\subseteq E(G)$. We say that
graph $G$ _realizes_ $R$ if for all $D^{\prime}\subseteq D$: $D^{\prime}\in R$
if and only if there is a solution $S\subseteq E(G)$ with $S\cap
D=D^{\prime}$. We say that $G$ _$B$ -realizes_ $R$ if $G$ is $B$-homogeneous.
The endpoints of the dangling edges are called _portals_.

The crucial part of the reduction is the proof of the following theorem. We
postpone its proof and first show the lower bound.

######  Theorem 5.2.

Let $B\subseteq{\mathbb{N}}$ be a fixed set of finite size with
$\operatorname{max-gap}B>1$ and $0\notin B$. There is a
$f\mathrel{\mathop{\mathchar 58\relax}}{\mathbb{N}}\to{\mathbb{N}}$ such that
the following holds. Let $R\subseteq{\\{0,1\\}}^{e}$ be an even relation (i.e.
$\operatorname{hw}(x)$ is even for all $x\in R$). Then we can $B$-realize $R$
by a simple graph with $f(e)$ vertices of degree at most $\max B+2$, the
portal nodes are pairwise distinct.

Recall the formal statement of the insertion from Definition 2.3. The
following lemma follows directly from this definition and the definition of
the realization. We use it to replace the relations by their realization.

######  Lemma 5.3.

Let $G$ be a node labeled graph, $R$ the relation of node $v\in V(G)$, and let
$H$ realize $R$. Assume inserting $H$ in $G$ at $v$ gives us a new graph
$G^{\prime}$. Then there is a solution for $G$ if and only if there is a
solution for $G^{\prime}$.

Now we can prove the lower bound under SETH. We assume that
$B\subseteq{\mathbb{N}}$ is a fixed, finite set such that $0\notin B$ and
$\operatorname{max-gap}B>1$.

######  Proof 5.4 (Proof of Theorem 1.4).

Let $H$ be a $B$-FactorR instance with $n_{S}$ simple nodes, $n_{C}$ complex
nodes, pathwidth ${\operatorname{pw}}_{H}$, and $\Delta^{*}=\max_{\text{bag
}X}\sum_{v\in V_{C}\cap X}\deg(v)$.

Replace every complex node $v$ and its relation $R_{v}$ by a $B$-homogeneous
graph of size at most $f(\deg(v))$ according to Theorem 5.2 to get the graph
$G$ with $n_{G}\in\mathcal{O}(n_{S}+n_{C}\cdot f(\Delta^{*}))$ vertices.
Obviously we can bound the pathwidth of the inserted graphs by their size. We
transform each bag $X$ of the path decomposition of $H$ into a bag
$X^{\prime}$ of the path decomposition of $G$ by replacing all complex nodes
with the nodes of their realization.

$\lvert X^{\prime}\rvert\leq\lvert X\rvert+\sum_{v\in X\cap
V_{C}}f(\deg(v))\leq\lvert X\rvert+\sum_{v\in X\cap
V_{C}}f(\Delta^{*})\leq\lvert X\rvert+\Delta^{*}f(\Delta^{*})=\lvert
X\rvert+f^{\prime}(\Delta^{*})$

for some function $f^{\prime}$. Hence, the pathwidth of $G$ is bounded by
${\operatorname{pw}}_{G}\leq{\operatorname{pw}}_{H}+f^{\prime}(\Delta^{*})$.

Now assume we can solve $B$-Factor in the claimed running time:

$\displaystyle(\max B+1-\epsilon)^{{\operatorname{pw}}_{G}}\cdot
n_{G}^{\mathcal{O}(1)}$ $\displaystyle\leq(\max
B+1-\epsilon)^{{\operatorname{pw}}_{H}+f^{\prime}(\Delta^{*})}\cdot(n_{S}+n_{C}\cdot
f^{\prime}(\Delta^{*}))^{\mathcal{O}(1)}$ $\displaystyle\leq(\max
B+1-\epsilon)^{{\operatorname{pw}}_{H}+f^{\prime}(\Delta^{*})}\cdot
f^{\prime\prime}(\Delta^{*})\cdot(n_{S}+n_{C})^{\mathcal{O}(1)}$
$\displaystyle\leq(\max
B+1-\epsilon)^{{\operatorname{pw}}_{H}+f^{\prime\prime\prime}(\Delta^{*})}\cdot(n_{S}+n_{C})^{\mathcal{O}(1)}$

for some $f^{\prime\prime}$ and $f^{\prime\prime\prime}$. But this would
immediately contradict SETH by Theorem 4.2.

###  5.1 Realizing Relations

From now on let $B\subseteq{\mathbb{N}}$ be our fixed, finite set with $\min
B\geq 1$ and $\operatorname{max-gap}B=d>1$ such that $[a,a+d+1]\cap
B=\\{a,a+d+1\\}$ for some $a\geq 1$. We first realize three quite basic
relations which we use later to realize the more complex relations.

######  Lemma 5.5.

We can $B$-realize each of the relations $\mathtt{HW}_{=2}^{(2)}$,
$\mathtt{EQ}_{d+1}$, and $\mathtt{EQ}_{2}$ by a simple graph with
$\mathcal{O}(\operatorname{poly}(\max B))$ vertices of degree at most $\max
B$.

######  Proof 5.6.

  1. 1.

Define a $\min B+1$-clique with new vertices. Split an arbitrary edge $(u,v)$
into two dangling edges $(?,u)$ and $(?,v)$. The construction of the clique
and the fact that we chose $\min B$ as degree forces the two dangling edges to
be selected in any solution.

  2. 2.

We start with two new vertices $u,v$ and connect each to $a$ many common
$\mathtt{HW}_{=2}^{(2)}$ nodes. We add $d+1$ dangling edges to $u$ and zero to
$v$. Finally the nodes are replaced by their realization. Observe that $u$ has
$a$ forced edges and $d+1$ dangling edges. Thus we must select none or all of
the dangling edges since $[a,a+d+1]\cap B=\\{a,a+d+1\\}$.

  3. 3.

Define a $d+2$-clique with $\mathtt{EQ}_{d+1}$ nodes. Split an arbitrary edge
$(u,v)$ into two dangling edges $(?,u)$ and $(?,v)$. Replace the nodes by
their realization.

Either both dangling edges are selected in which case all nodes have $d+1$
incident edges in the solution, or neither is selected in which case every
node has zero incident edges in the solution.

The following lemma helps us to keep the later constructions simple. Instead
of constructing the relations for arbitrary degree, only the very low degree
cases are necessary.

######  Lemma 5.7.

If we can realize $\mathtt{HW}_{=1}^{(a)}$ for $a\in\\{1,2,3\\}$ by a simple
graph with at most $N$ vertices of degree at most $D$, then we can realize
$\mathtt{HW}_{=1}^{(k)}$ for all $k\geq 1$ by a simple graph using
$\mathcal{O}(kN)$ nodes of degree at most $D$.

######  Proof 5.8.

We construct the graph for the realization inductively starting with the basis
for $k=1,2,3$. See Figure 4 for an example.

For the inductive step from $k$ to $k+1$ we start with a node $u$ with
relation $\mathtt{HW}_{=1}^{(k)}$. Connect one dangling edge of $u$ to a new
node $v$ with $\mathtt{HW}_{=1}^{(2)}$. Connect the other dangling edge of $v$
to a node $w$ with relation $\mathtt{HW}_{=1}^{(3)}$. Observe that the final
graph has $k+1$ dangling edges.

Assume one dangling edge of $u$ is selected, then the edge between $u$ and $v$
is not selected but the edge from $v$ to $w$ is. Hence, no dangling edge of
$w$ can be selected. The analogue holds if one of the dangling edges of $w$ is
selected. It cannot be the case that more than one or zero dangling edges are
selected, as then the relation of one of the three nodes $u$, $v$, or $w$
would not be satisfied.

Figure 4:  Example of the inductive construction from Lemma 5.7 for
$\mathtt{HW}_{=1}^{(6)}$ using $\mathtt{HW}_{=1}^{(3)}$ and
$\mathtt{HW}_{=1}^{(2)}$.

Due to parity issues, the construction of the realizations depends on the set
$B$. For each of the possible cases ($B$ contains only even numbers, only odd
number, or even and odd numbers) we state the result separately in Lemmas 5.9,
5.11 and 5.13.

######  Lemma 5.9.

If $B$ contains only even numbers, we can $B$-realize the following relations
by simple graphs:

  1. 1.

$\mathtt{EQ}_{k}$ for even $k\geq 2$ using
$\mathcal{O}(k\operatorname{poly}(\max B))$ vertices of degree at most $\max
B$.

  2. 2.

$\mathtt{HW}_{=1}^{(k)}$ together with $\mathtt{HW}_{=1}^{(\ell)}$ for all
$k,\ell\geq 1$ using $\mathcal{O}((k+\ell)\operatorname{poly}(\max B))$
vertices of degree at most $\max B+2$.

######  Proof 5.10.

  1. 1.

For $k=2$ we can use the construction of Lemma 5.5. For the other case we
first realize $\mathtt{EQ}_{4}$. Then we use a chain of these relations to
realize $\mathtt{EQ}_{k}$ for even $k\geq 6$.

Start with a $\mathtt{EQ}_{d+1}$ node $u$ and make it adjacent to
$\frac{d+1-4}{2}$ many $\mathtt{EQ}_{2}$ nodes (note that an even $B$ can have
only gaps of odd size, hence $d$ is odd). Then we add four dangling edges to
$u$. hence the construction actually works. The graph is simple as the
dangling edges in the realization of $\mathtt{EQ}_{2}$ are different.

  2. 2.

To use Lemma 5.7 for the general construction, observe that the number of
$\mathtt{HW}_{=1}$ nodes used in the construction is odd. Hence, we will
always realize two nodes. For this we show how to realize
$\mathtt{HW}_{=1}^{(k)}$ together with $\mathtt{HW}_{=1}^{(\ell)}$ for all
$k,\ell\in\\{1,2,3\\}$.

Start with two vertices $u,v$. Make $u$ and $v$ adjacent to $\max B-1$ common
$\mathtt{HW}_{=2}^{(2)}$ nodes. We add $k$ dangling edges to $u$ and $\ell$
dangling edges to $v$. As $B$ does not contain $\max B-1$, the correctness
follows.

Despite the fact, that the parity of the elements is still the same when all
elements in $B$ are odd, it is possible to show a stronger result, which
allows us to realize single $\mathtt{HW}_{=1}$ nodes.

######  Lemma 5.11.

If $B$ contains only odd numbers, we can $B$-realize the following relations
by simple graphs:

  1. 1.

$\mathtt{EQ}_{k}$ for even $k\geq 2$ using
$\mathcal{O}(k\operatorname{poly}(\max B))$ vertices of degree at most $\max
B$.

  2. 2.

$\mathtt{HW}_{=1}^{(k)}$ for $k\geq 1$ using
$\mathcal{O}(k\operatorname{poly}(\max B))$ vertices of degree at most $\max
B+2$.

######  Proof 5.12.

  1. 1.

The construction from Lemma 5.9 for $\mathtt{EQ}_{k}$ works here too.

  2. 2.

We again use Lemma 5.7 and only realize $\mathtt{HW}_{=1}^{(k)}$ for
$k=1,2,3$. We start with just one node $u$ to which we force $\max B-1$ edges
by making it adjacent to $\frac{\max B-1}{2}$ nodes of type
$\mathtt{HW}_{=2}^{(2)}$. This is possible as $\max B-1$ is even. We add $k$
dangling edges to $u$ and replace all nodes by their realizations. As before
the correctness follows since $B$ does not contain $\max B-1$.

For the last case, where even and odd numbers are in $B$, we can additionally
drop the remaining restriction that the equality nodes must have even degree.
This is rather natural as a gap of size $2$ already gives us a
$\mathtt{EQ}_{3}$ node by Lemma 5.5.

######  Lemma 5.13.

If $B$ contains even and odd numbers, we can $B$-realize the following
relations by simple graphs:

  1. 1.

$\mathtt{EQ}_{k}$ for $k\geq 1$ using $\mathcal{O}(k\operatorname{poly}(\max
B))$ vertices of degree at most $\max B$.

  2. 2.

$\mathtt{HW}_{=1}^{(k)}$ for $k\geq 1$ using
$\mathcal{O}(k\operatorname{poly}(\max B))$ vertices of degree at most $\max
B+2$.

######  Proof 5.14.

  1. 1.

The case $k=2$ follows by Lemma 5.5.

For the remaining cases it suffices to $B$-realize $\mathtt{EQ}_{1}$. Then we
make $d-2\geq 0$ many of these nodes adjacent to one $\mathtt{EQ}_{d+1}$ node.
Adding three dangling edges and replacing all nodes recursively by their
$B$-realization realizes $\mathtt{EQ}_{3}$. Then we can use a chain of these
relations to realize $\mathtt{EQ}_{k}$ for all $k\geq 4$.

Let $b,c\in B$ such that $b<c$ with different parity. Force $b$ edges on two
new nodes $u,v$ by making both adjacent to $b$ many common nodes of type
$\mathtt{HW}_{=2}^{(2)}$. Then we make $\frac{c-b-1}{2}$ many
$\mathtt{EQ}_{2}$ nodes adjacent to $u$ and add one dangling edge to it. The
vertex $v$ does not get any dangling edges but is always in a valid state, as
all incident edges are selected. If the dangling edge incident to $u$ is
selected, then we also select the edges to the $\mathtt{EQ}_{2}$ nodes.
Otherwise no edge is selected except for the ones forced by the
$\mathtt{HW}_{=2}^{(2)}$ nodes.

  2. 2.

We first realize $\mathtt{HW}_{=1}^{(1)}$ to force single edges. For this let
$o\in B$ be an odd number. Start with a new vertex and force $o-1$ edges to it
by making it adjacent to $\frac{o-1}{2}$ nodes of type
$\mathtt{HW}_{=2}^{(2)}$. Then we make this vertex adjacent to one more node
of that type and add one dangling edge to it.

We only show the construction for $k=2,3$ and make use of Lemma 5.7 for larger
$k$. Start by “duplicating” all ingoing edges using $\mathtt{EQ}_{3}$ nodes
from the first step. Force $a+d$ edges on a new vertex $u$ and make it
adjacent to one copy of each ingoing edge. Vertex $u$ ensures that at least
one of the ingoing edges is selected. The other copy of each ingoing edge is
connected to a new vertex $v$. We force $\max B-1$ edges to $v$. By this at
most one of the ingoing edges has to be selected.

Now we have everything ready to prove that even relations can be realized.

Figure 5: An example illustrating the construction from the proof of Theorem
5.2 for the relation $R$ with $R(000011)=R(110011)=R(111001)=R(111100)=1$ and
zero otherwise.

######  Proof 5.15 (Proof of Theorem 5.2).

See Figure 5 for an example of the following construction. We use essentially
the construction from Lemma 3.3 in [13]. Let
$R=\\{x_{1},\dots,x_{r}\\}\subseteq{\\{0,1\\}}^{e}$ be the even relation for
some $r$. Let further $P=\\{(1+e\mod 2),0\\}$.

  1. 1.

Create nodes $o_{1},\dots,o_{e}$ with relation $\mathtt{HW}_{=1}$.

  2. 2.

Create vertices $a_{j}$ for all $j\in P$ with relation $\mathtt{HW}_{=1}$.

  3. 3.

For all $i\in[r]$:

    1. (a)

Let $O_{i}=\\{n^{(i)}_{1},\dots,n^{(i)}_{h_{i}}\\}=\\{k\in[e]\mid
x_{i}[k]=0\\}$ for $h_{i}=e-\operatorname{hw}(x_{i})$.

    2. (b)

Create the node $v_{i}$ with relation $\mathtt{EQ}$ and connect it to
$o_{n^{(i)}_{j}}$ for all $j\in[h_{i}]$.

    3. (c)

Connect $v_{i}$ to all $a_{j}$.

  4. 4.

Replace all nodes by their realization.

There are $\lvert P\rvert+e$ many $\mathtt{HW}_{=1}$ nodes. Since $\lvert
P\rvert=1+(1+e\mod 2)$, we can replace pairs of these nodes by their
realization. Every $v_{i}$ is connected to $\lvert P\rvert+\lvert O_{i}\rvert$
nodes, where $\lvert O_{i}\rvert=e-\operatorname{hw}(x_{i})$. Thus, $v_{i}$
has even degree as the relation $R$ is even, i.e. $\operatorname{hw}(x)$ is
even. Hence, we can replace these nodes by their realization according to the
previous lemmas.

To show that the construction actually realizes the relation, assume the
selected dangling edges corresponds to some element $x\in R$, let it w.l.o.g.
be $x_{1}$. Then we can select all edges incident to $x_{1}$, the dangling
edges, and the extension of this to all nodes as a solution. As $x_{1}$ is
incident to all $a_{j}$ they are in a valid state. Further $x_{1}$ is adjacent
to those $o_{k}$ where $x_{1}[k]=0$ and hence every $o_{k}$ is incident to
exactly one edge in the solution.

Now assume we are given a solution. As the nodes $a_{j}$ have exactly one
incident edge in the solution, there is exactly one node $v_{i}$ where all
incident edges are in the solution. Let $O$ be the set of nodes $o_{k}$ to
which $v_{i}$ is incident. By construction $v_{i}$ corresponds to some $x\in
R$ with $x[k]=0$ iff $k\in O$. As all selected dangling edges must be in the
solution, let $O^{\prime}$ be the set of nodes incident to the selected
dangling edges. But as we are given a solution we get
$O\mathrel{\dot{\cup}}O^{\prime}=\\{o_{1},\dots,o_{e}\\}$. Hence, the dangling
edges corresponds to $x$.

##  6 Optimization Version

In the previous section we have seen the realization of the relations for the
decision version. As we are interested in the largest solution for
Max-$B$-Factor, we also allow $0\in B$ since this does not make the problem
trivially solvable. This makes it necessary to change the definition of a
realization, as the pure existence of a solution is not sufficient anymore. We
change it such that if the relation is satisfied (i.e. the dangling edges are
selected in a good way), then there is a _large_ solution. Otherwise, there
must be a gap by which any solution is _smaller_ compared to the solutions in
the good cases. We call this gap the penalty (of the realization).

######  Definition 6.1 (Realization).

Let $R\subseteq{\\{0,1\\}}^{k}$ be a relation. Let $G$ be a node labeled
graph, with dangling edges $D=\\{d_{1},\dots,d_{k}\\}$. We say that graph $G$
_realizes_ $R$ with _penalty_ $\beta$ if we can efficiently construct/find a
target value $\alpha>0$ such that for all $D^{\prime}\subseteq D$:

  * •

If $D^{\prime}\in R$, then there is a solution $S\subseteq E(G)$ with $S\cap
D=D^{\prime}$ and $\lvert S\rvert=\alpha$.

  * •

If $D^{\prime}\notin R$, then for all solutions $S\subseteq E(G)$ with $S\cap
D=D^{\prime}$ we have $\lvert S\rvert\leq\alpha-\beta$.

We say that $G$ $B$-realizes $R$ if $G$ is additionally $B$-homogeneous. We
call the endpoints of the dangling edges _portal nodes_.

In the main part of this section we show how to realize the relations of
$B$-FactorR. The following theorem corresponds to Theorem 5.2 for the decision
version.

######  Theorem 6.2 (Realization of Relations).

Let $B\subseteq{\mathbb{N}}$ be a fixed, finite set with $\operatorname{max-
gap}B>1$ and $0\in B$. There is a $f\mathrel{\mathop{\mathchar
58\relax}}{\mathbb{N}}^{2}\to{\mathbb{N}}$ such that the following holds. Let
$R\subseteq{\\{0,1\\}}^{e}$ be a relation with a constant $c_{R}\in
2{\mathbb{N}}$ such that for all $x\in R$ we have
$\operatorname{hw}(x)=c_{R}$.

We can $B$-realize the relation $R$ with arbitrary penalty $\beta>0$ by a
simple graph with $f(e,\beta)$ vertices of degree at most $\max B+2$.

Consider a graph $G$ where we replaced nodes and their relations by
realizations to get a graph $G^{\prime}$. Then we say that a solution $S$ for
$G^{\prime}$ is _valid or good_ if $S\cap E(G)$ is a solution for $G$.
Otherwise the solution is _invalid or bad_. Consider a node $v$ in $G$. Let
$I$ be the incident edges and $E_{v}$ be the edges in $G^{\prime}$ resulting
from replacing $v$ by its realization. When considering a solution $S$ for
$G$, we say that $S\cap(I(v)\cup E_{v})$ is the partial solution for the
realization of $v$, i.e. all selected edges from the inserted graph and the
incident edges.

It remains to compute the target value by which we decide if the $B$-FactorR
instance has a solution or not.

######  Lemma 6.3.

Let $G$ be a $B$-FactorR instance from Section 4. Let $G^{\prime}$ be a
$B$-Factor instance resulting from $G$ by replacing every complex nodes with
degree $\delta$ by its realization with penalty $2\delta$. Then, there is an
efficiently computable constant $\alpha$ such that $G$ has a solution if and
only if the largest solution for $G^{\prime}$ has size $\alpha$.

######  Proof 6.4.

By Corollary 4.11 the complex nodes form a vertex cover for the graph. Further
note, that two complex nodes share at most two edges and by our definition of
the relations exactly one edge from each such pair of edges is selected in a
valid solution. Let $X$ be the number of these pairs of edges.

Let $\alpha_{v}$ be the target value for the realization of complex node $v$.
Then we define $\alpha\coloneqq\sum_{v\in V_{c}}\alpha_{v}-X$. The negative
term accounts for the edges between the complex nodes, as they are counted
twice.

The “only if” direction of the claim follows directly by the definition of
$\alpha$. For the “if” direction assume $G^{\prime}$ has a solution of size at
least $\alpha$.

It suffices to show that this solution is valid, i.e. the relation of all
complex nodes are satisfied. Then the solution for $G$ follows directly by
choosing the edges incident to the realizations of the complex node. Assume
otherwise and let $W$ be the set of complex nodes whose relation is not
satisfied. As the relation of each $v\in W$ is not satisfied, we lose at least
a factor of $\beta_{v}$. But as all incident edges of $v$ could be selected,
the size of the partial solution for $v$ is at most
$\alpha_{v}-\beta_{v}+\deg(v)$. But as we chose $\beta_{v}=2\deg(v)$, this
solution has size at most $\alpha_{v}-\deg(v)$.

For $i\in\\{0,1,2\\}$, let $Y_{i}$ be the number of selected _edges_ between
complex nodes, where $i$ endpoints are in $W$. Then $Y_{0}+Y_{1}+Y_{2}$
corresponds to the total number of selected edges between complex nodes. As
these edges are counted twice, they appear negative in the following bound for
the total size:

$\sum_{v\in W}\alpha_{v}-\deg(v)+\sum_{v\in V_{c}\setminus
W}\alpha_{v}-Y_{0}-Y_{1}-Y_{2}$

If we can show that this is strictly smaller than $\alpha$, we get a
contradiction to the assumption that the size of the solution is at least
$\alpha$ and the solution is valid.

For $i\in\\{0,1,2\\}$, let $X_{i}$ be the number of _pairs_ of edges between
complex nodes where $i$ endpoints are contained in $W$. Observe that
$X_{0}+X_{1}+X_{2}=X$. Now it suffices to show:

$-\sum_{x\in W}\deg(v)-Y_{0}-Y_{1}-Y_{2}<-X_{0}-X_{1}-X_{2}$

For each pair of edges contributing to $X_{0}$, there is exactly one edge
selected, as the relation of both endpoints is satisfied. This implies
$X_{0}=Y_{0}$. Further, for all pairs of edges contributing to $X_{1}$, we
know that exactly one edge of this pair is selected. Otherwise, the relation
of both nodes would not be satisfied and both nodes would be in $W$, thus
$X_{1}=Y_{1}$. Hence, it remains to show

$X_{2}<\sum_{x\in W}\deg(v)+Y_{2}$

Each pair of edges contributing to $X_{2}$ has two endpoints in $W$. We could
split $X_{2}$ according to the contribution of each node in $W$. As each node
in $W$ can definitely contribute only to at most $\deg(v)/2$ pairs (strictly
speaking actually only 2), this finishes the proof.

Now we are ready to prove the conditional lower bound for Max-$B$-Factor when
$0\in B$.

######  Proof 6.5 (Proof of Theorem 1.5).

Use Lemma 6.3 to construct the final graph and the target value. Then the
proof goes analogous to the proof for the decision version (cf. Theorem 1.4).

###  6.1 High Girth Graphs

Our definition of realizations includes the dangling edges in the solution
size. We also define a slight variation where the dangling edges are not
included. While both definitions are equivalent for $\mathtt{HW}_{=k}$ nodes,
they differ for $\mathtt{HW}_{\in S}$ nodes. The _internal realization_ of a
node can be seen as a realization, where we do not adjust the solution size
according to the number of selected dangling edges, i.e. only the internal
edges are considered for the solution size.

######  Definition 6.6 (Internal Realization).

Let $R\subseteq{\\{0,1\\}}^{k}$ be a relation. Let $G$ be a node labeled
graph, with dangling edges $D=\\{d_{1},\dots,d_{k}\\}\subseteq E(G)$. $G$
_internally realizes_ $R$ with _penalty_ $\beta$ if we can efficiently
construct/find an $\alpha>0$ such that for all $D^{\prime}\subseteq D$:

  * •

If $D^{\prime}\in R$, then there is a solution $S\subseteq E(G)$ with $S\cap
D=D^{\prime}$ and $\lvert S\setminus D\rvert=\alpha$.

  * •

If $D^{\prime}\notin R$, then for all solutions $S\subseteq E(G)$ with $S\cap
D=D^{\prime}$ we have $\lvert S\setminus D\rvert\leq\alpha-\beta$.

We say that $G$ internally $B$-realizes $R$ if $G$ is additionally
$B$-homogeneous.

We know that there is a gap of size at least two between $a$ and $a+d+1$ in
$B$. This allows us to define relatively simple conditions of the form “if one
incident edge of a vertex with degree $a+d+1$ is not selected, then another
edge is also not selected”. In other words, this propagates the penalty to a
neighboring vertex. We combine this with high girth graphs to introduce an
arbitrary large penalty for not selecting an edge.

The construction of $r$ regular graphs with girth $g$ is a long studied
problem in graph theory. Erdős and Sachs proved the existence of such graphs
for all combinations of $r$ and $g$.

######  Lemma 6.7 (Theorem 1 in [23]).

For all $r\geq 2$ and $g\geq 3$, there is a $r$-regular graph $G_{r,g}$ of
girth $g$ with at most $4gr^{g}$ vertices.

Finding the smallest graph for each $r,g$ is a non-trivial task and known as
the $(r,g)$-cage problem. For several cases (e.g. $r$ is a prime power)
constructions are known reducing the number of vertices in the graph. See [18,
24, 30, 34] for more results.

###  6.2 Realizing Relations

From now on let $d\coloneqq\operatorname{max-gap}B>1$ such that $[a,a+d+1]\cap
B=\\{a,a+d+1\\}$ for some $a\geq 0$. As we allow $0\in B$, we can always find
a trivial solution. Thus, we cannot force edges as we did for the decision
version. Instead we construct a gadget where we can select many edges when the
“forced” edges are selected. Otherwise we ensure that the solution is small.
We use the graphs with high girth for this.

######  Lemma 6.8.

There is a $f\mathrel{\mathop{\mathchar 58\relax}}{\mathbb{N}}\to{\mathbb{N}}$
such that the following holds. We can $B$-realize $\mathtt{HW}_{=2}^{(2)}$
(with distinct portal vertices) and internally $B$-realize $\mathtt{EQ}_{d+1}$
with arbitrary penalty $\beta$ by simple graphs using at most $f(\beta)$
vertices of degree at most $\max B$.

######  Proof 6.9.

  1. 1.

For ${\mathtt{HW}_{=2}^{(2)}}$ we use Lemma 6.7 to get an $a+d+1$-regular
graph $G_{a+d+1,\beta}$ of girth at least $\beta$. Split an arbitrary edge
$(u,v)$ into two dangling edges for $u$ and $v$ each and assign the set $B$ to
every vertex.

The graph has the claimed properties: If both dangling edges are selected,
then we can use the set of all edges in the graph as a solution since
$a+d+1\in B$.

It remains to check the case when at least one dangling edge is not selected,
let it w.l.o.g. be the one incident to $u$. Assume $S$ is the optimal
solution. We show that this solution does not contain more than $\lvert
E_{a+d+1,\beta}\rvert-\beta$ edges.

By assumption $\deg_{S}(u)\leq a$. Hence, there must be at least one other
incident edge to $u$ that is not in the solution, because $a+d-1\geq a+1\notin
B$. Then we can apply this argument always to the next vertex. Observe that
this sequence can only stop if we reach another vertex $w$ we have already
visited because for this vertex we already know that two incident edges were
not selected in the solution. The length of this path, i.e. the number of not
selected edges from $w$ to $w$, is at least the girth of the graph. Hence the
number of edges that are not selected in the solution is at least the girth of
the graph which is at least $\beta$.

  2. 2.

For $\mathtt{EQ}_{d+1}$ we start with two vertices $u$ and $v$ and make both
adjacent to $a$ many common $\mathtt{HW}_{=2}^{(2)}$ nodes with penalty
$\beta+2$. Add $d+1$ dangling edges to one of the vertices and zero to the
other. As the vertices connected to the dangling edges in the realization of
the $\mathtt{HW}_{=2}^{(2)}$ nodes are different, the graph is simple.

If $d+1$ or $0$ dangling edges are selected, we can choose all internal edges
for the optimal solution $S$, as $a+d+1,a\in B$. The size of the solution is
in both cases optimal.

Now assume $0<\ell<d+1$ dangling edges are selected. From $a+\ell\notin B$ it
follows that there must be at least one $\mathtt{HW}_{=2}^{(2)}$ node where at
least one incident edge is not selected. By this we lose at least $\beta+1$
compared to the optimal solution.

As for the decision version, we now realize relations used for the general
construction.

######  Lemma 6.10.

There is a $f\mathrel{\mathop{\mathchar
58\relax}}{\mathbb{N}}^{2}\to{\mathbb{N}}$ such that the following holds. We
can $B$-realize a pair of $\mathtt{HW}_{=1}^{(k)}$ and
$\mathtt{HW}_{=1}^{(\ell)}$ for any $k,\ell\geq 1$ with arbitrary penalty
$\beta$ with simple graphs using at most $f(k+\ell,\beta)$ vertices of degree
at most $\max B+2$.

For the proof of the lemma we reuse the construction we have already seen for
the decision version, by which an explicit construction of these nodes for
$k,\ell\in\\{1,2,3\\}$ is sufficient. To realize these relations we
distinguish between the cases $\max B-1\in B$ or not. By this the proof of
Lemma 6.10 follows from Lemmas 6.11, 6.13 and 6.15.

######  Lemma 6.11.

If we can $B$-realize $\mathtt{HW}_{=1}^{(a)}$ together with
$\mathtt{HW}_{=1}^{(b)}$ for $a,b\in\\{1,2,3\\}$, with arbitrary penalty
$\beta$ using simple graphs with at most $N$ vertices of degree at most $D$,
then we can $B$-realize $\mathtt{HW}_{=1}^{(k)}$ together with
$\mathtt{HW}_{=1}^{(\ell)}$ for all $k,\ell\geq 1$ with arbitrary penalty
$\beta$ using simple graphs using $\mathcal{O}((k+\ell)N)$ vertices of degree
at most $D$.

######  Proof 6.12.

We use the same construction as for the decision version as stated in Lemma
5.7. We use $\beta+3$ as penalty for the realizations. The target value is the
sum of the $\alpha$s of all involved nodes minus the number of
$\mathtt{HW}_{=1}^{(2)}$ nodes used to connect the other nodes. This negative
term takes care that we do not count edges twice.

For the correctness we observe that there could be solutions that do not
satisfy the relations of all nodes. Note that each node has degree at most 3
and is incident to exactly one selected edge for a valid solution. Hence, for
every such pair of additionally selected edges, there is at least one node not
in a valid state. By its penalty of $\beta+3$, it can compensate for these
additional edges. Hence, these solutions are smaller by at least $\beta$.

For the case $\max B-1\notin B$, we use the same approach as for the decision
version when all elements of $B$ are even.

######  Lemma 6.13.

There is a $f\mathrel{\mathop{\mathchar 58\relax}}{\mathbb{N}}\to{\mathbb{N}}$
such that the following holds. If $\max B-1\notin B$, we can $B$-realize a
pair of $\mathtt{HW}_{=1}^{(k)}$ and $\mathtt{HW}_{=1}^{(\ell)}$ for
$k,\ell\in\\{1,2,3\\}$ with arbitrary penalty $\beta$ with simple graphs using
at most $f(\beta)$ vertices of degree at most $\max B+2$.

######  Proof 6.14.

Start with two vertices $u,v$. Connect both to $\max B-1$ common nodes of type
$\mathtt{HW}_{=2}^{(2)}$. Add $k$ dangling edges to $u$ and $\ell$ dangling
edges to $v$. Replace all nodes by their realization with penalty
$\beta+k+\ell$. The target value $\alpha$ is the sum of target values of the
$\mathtt{HW}_{=2}^{(2)}$ plus 2 for two selected dangling edges.

Assume exactly one dangling edge to each $u$ and $v$ is selected. Then we can
extend this to a solution for the $\mathtt{HW}_{=2}^{(2)}$ nodes, by selecting
all internal edges.

If for $u$ or $v$ no dangling edge is selected, then there must be at least
one $\mathtt{HW}_{=2}^{(2)}$ node which is not incident to two edges in the
optimal solution as $\max B-1\notin B$. Hence, we lose a penalty of
$\beta+k+\ell\geq\beta$. Now let $\hat{k},\hat{\ell}$ dangling edges of $u,v$
be selected, respectively, such that $\hat{k}>1$ or $\hat{\ell}>1$. W.l.o.g.
assume $\hat{k}>1$. Then at least one edge between $u$ and a
$\mathtt{HW}_{=2}^{(2)}$ node is not selected, as $\max B-1+\hat{k}>\max B$.
Hence, the $\mathtt{HW}_{=2}^{(2)}$ node is not incident to two edges and we
lose a factor of $\beta+k+\ell$. As $\hat{k}+\hat{\ell}\leq k+\ell$, we still
lose $\beta$ compared to the optimal solution in the good case.

For the case $\max B-1\in B$, we use an approach that is similar to the
decision version, when $B$ contains even and odd numbers. But as we cannot use
an $\mathtt{EQ}_{3}$ node, the construction gets slightly more complicated as
we have to handle the additional edges of a $\mathtt{EQ}_{d+1}$ node.

######  Lemma 6.15.

There is a $f\mathrel{\mathop{\mathchar 58\relax}}{\mathbb{N}}\to{\mathbb{N}}$
such that the following holds. If $\max B-1\in B$, we can $B$-realize a node
$\mathtt{HW}_{=1}^{(k)}$ for $k\in\\{1,2,3\\}$ with arbitrary penalty $\beta$
with simple graphs using at most $f(\beta)$ vertices of degree at most $\max
B+2$.

######  Proof 6.16.

We first prove the claim for $k=1$, which we need for the proof of the other
cases.

######  Claim 2.

There is a $f^{\prime}\mathrel{\mathop{\mathchar
58\relax}}{\mathbb{N}}\to{\mathbb{N}}$ such that we can $B$-realize
$\mathtt{HW}_{=1}^{(1)}$ with arbitrary penalty $\beta$ with simple graphs
using at most $f^{\prime}(\beta)$ vertices of degree at most $\max B$.

We use the same approach as for the decision version and let $v$ be a new
vertex. Let $o$ be the odd number of $\max B-1$ and $\max B$. We force $o-1$
edges to the vertex by adding $\frac{o-1}{2}$ $\mathtt{HW}_{=2}^{(2)}$ nodes
to it. We introduce one more $\mathtt{HW}_{=2}^{(2)}$ node $u$. We add one
edge between $u$ and $v$ and add one dangling edge to $u$. We replace all
nodes by their realization according to Lemma 6.8 with penalty $\beta+1$. The
target value is the sum of all target values of the $\mathtt{HW}_{=2}^{(2)}$
nodes.

If the dangling edge is selected, then we can select all other edges. Vertex
$v$ is then incident to $2\cdot\frac{o-1}{2}+1=o\in B$ edges. But if the
dangling edge is not selected, the node $u$ cannot be in a valid state and we
lose at least $\beta$ compared to the optimal solution.

Now we prove the construction for $k=2,3$. See Figure 6(a) for an example of
the construction. We create vertices $u_{1},\dots,u_{d-1}$ and $v$. We force
$\max B-1$ edges on $u_{j}$ for all $j\in[d-1]$ and $a+d$ edges on $v$ with
nodes from the previous claim. We further introduce nodes $s_{1},\dots,s_{k}$
with relation $\mathtt{EQ}_{d+1}$. We make each of the $s_{i}$ adjacent to the
vertices $u_{1},\dots,u_{d-1},v$. Finally, we add one dangling edge to each
$s_{i}$. The vertices $u_{j}$ ensure that _at most one_ dangling edge is
selected while $v$ makes sure that _at least one_ is selected. We replace all
nodes by their realization with a penalty of $\beta+3$. The target values is
the sum of all target values of the realizations for the nodes, plus $d+1$
accounting for the selected edges, when one dangling edge is selected. Observe
that the edges forced by the $\mathtt{HW}_{=1}^{(1)}$ nodes are usually part
of any solution. Hence, we only have to focus on the edges incident to the
nodes with $\mathtt{EQ}_{d+1}$, as they are only internally realized. Note,
this simplification can lead to solutions of negative size, when considering
the penalty.

Assume only the dangling edge of $s_{i}$ is selected. Then we select the edges
incident to $s_{i}$ as a solution of size $d+1$.

If no dangling edge is selected, then the vertex $v$ cannot be in a valid
state or one of the $s_{i}$ is not in a valid state. This bounds the solution
size by $d-(\beta+3)\leq d+1-\beta$.

Now assume $\ell>1$ dangling edges are selected. W.l.o.g. we can assume that
none of the $s_{i}$ is in an invalid state, as this would lead to a solution
smaller than for some appropriate $\ell^{\prime}$. As each of the $d-1$
vertices $u_{j}$ cannot be incident to more than $\max B$ edges in any
solution, for each selected dangling edge except the first one there must be
an edge to an adjacent $\mathtt{HW}_{=1}^{(1)}$ node that is not in the
solution, i.e. the $\mathtt{HW}_{=1}^{(1)}$ node is not in a valid state. This
bounds the solution size by: $\ell(d+1)-(d-1)(\ell-1)(\beta+3)$. If we can
bound this by $d+1-\beta$, the claim follows. But this is equivalent to show
$(\ell-1)(d+1)+\beta\leq(d-1)(\ell-1)(\beta+3)$. As $\ell>1$ and $d>1$, it is
easy to check that this claim holds true.

(a) Example construction for the proof of Lemma 6.15.

(b) Graph for the relation $R$ with
$R(000111)=R(010011)=R(110001)=R(111000)=1$ and zero otherwise.

Figure 6:  Blue nodes have $\mathtt{EQ}_{k(d+1)}$ as relation, light blue
nodes have $\mathtt{EQ}_{1}$, black ones $\mathtt{HW}_{\in B}$, and orange
nodes have $\mathtt{HW}_{=1}$.

Following the approach from the decision version, it remains to realize
$\mathtt{EQ}_{k}$ nodes for even $k$. But the construction for the decision
version cannot be transferred directly as it does not give us a realization.
Recall, that we use a $d+2$-clique of $\mathtt{EQ}_{d+1}$ nodes and split one
edge into two dangling edges to realize $\mathtt{EQ}_{2}$. But if both
dangling edges are selected, the solution has $\Theta(d^{2})$ more edges
compared to the solution when no dangling edge is selected. But surprisingly
for $\mathtt{EQ}_{k(d+1)}$ nodes a realization can be constructed. So we use
them for our construction.

######  Lemma 6.17.

There is a function $f\mathrel{\mathop{\mathchar
58\relax}}{\mathbb{N}}^{2}\to{\mathbb{N}}$ such that the following holds. For
arbitrary $k\geq 1$ we can $B$-realize $\mathtt{EQ}_{k(d+1)}$ with arbitrary
penalty $\beta$ by simple graphs using $f(k,\beta)$ vertices of degree at most
$\max B+2$.

######  Proof 6.18.

Construct a $d$-regular connected bipartite graph with $k(d+1)$ nodes of type
$\mathtt{EQ}_{d+1}$ on each side. Let $L$ be the set of nodes on the left side
and $R$ of the right side. Subdivide each edge by placing one
$\mathtt{HW}_{=1}^{(2)}$ node on each edge. Add one dangling edge to each node
in $L$. On the right side we introduce $k$ new nodes of type
$\mathtt{EQ}_{d+1}$. Make each node in $R$ adjacent to exactly one of these
nodes such that every node has degree $d+1$. Finally, replace all nodes by
their (internal) realization that are guaranteed to exist as $d(d+1)$ is
always even. Use $\beta+2k(d+1)^{2}$ as penalty for all nodes. The target
value is the sum of all target values of the realizations plus $k(d+1)$.

If all $k(d+1)$ dangling edges are selected, we can select all $k(d+1)^{2}$
edges on the left side of the graph and none of the edges on the right side as
optimal solution. The converse holds for the case when no dangling edges are
selected. No solution can select more edges than this, as each additionally
selected edge, leads to one additional node in an invalid state, whose penalty
can compensate that edge.

Now assume $0<\ell<k(d+1)$ dangling edges are selected for some solution.
Assume for contradictions sake that all nodes in $L$ are in a valid state. But
then there is a node in $L$ that is in the 0-state and one node is in the
$d+1$-state. As our bipartite graph is connected, there are two such nodes
that are additionally connected to the same node in $R$ (by two subdivided
edges). This implies that this node on the right side is not in a valid state.
Hence, its penalty can even compensate the selection of all edges.

Now we have everything together to realize almost arbitrary relations and
prove the main theorem for the maximization version. See Figure 6(b) for an
example of the construction.

######  Proof 6.19 (Proof of Theorem 6.2).

We use a slight variation of our construction for the decision version in
Theorem 5.2 and hence the construction in [13] as we cannot realize
$\mathtt{EQ}_{k}$ for arbitrary even $k$. We resolve this issue by using nodes
with larger degree and add nodes that take care of the additional edges.

Let $R=\\{x_{1},\dots,x_{r}\\}\subseteq{\\{0,1\\}}^{e}$ be a relation,
$c_{R}\in 2{\mathbb{N}}$ be the constant such that for all $x\in R$ we have
$\operatorname{hw}(x)=c_{R}$, and let $h\coloneqq e-c_{R}$ be the number of 0s
of each $x_{i}$. There is a unique integer $\ell>0$ such that
$2(\ell-1)(d+1)<h+1\leq 2\ell(d+1)$. Let $s\coloneqq 2\ell(d+1)-h$. We define
the graph realizing $R$ as follows:

  1. 1.

Create nodes $o_{k}$ for all $k\in[e]$ and assign the relation
$\mathtt{HW}_{=1}$ to them. Their degree is determined later, and by Lemma
6.10 not relevant for us.

  2. 2.

Create nodes $a_{j}$ for all $j\in[s]$ with relation $\mathtt{HW}_{=1}$.

  3. 3.

For all $i\in[r]$:

    1. (a)

Create a node $v_{i}$ with relation $\mathtt{EQ}_{2\ell(d+1)}$.

    2. (b)

Make $v_{i}$ adjacent to $a_{j}$ for all $j\in[s]$.

    3. (c)

Let $O_{i}=\\{n^{(i)}_{1},\dots,n^{(i)}_{h}\\}=\\{k\in[e]\mid x_{i}[k]=0\\}$
and connect $v_{i}$ to $o_{n^{(i)}_{j}}$ for all $j\in[h]$.

To get a $B$-homogeneous graph, we replace the nodes $v_{i}$ by the
realization from Lemma 6.17 which is possible since $h+s=2\ell(d+1)$. All
$\mathtt{HW}_{=1}$ nodes, i.e. $a_{i}$ and $o_{k}$, are replaced by their
realization from Lemma 6.10. This is possible as
$s+e=2\ell(d+1)-h+e=2\ell(d+1)+c_{R}$ is an even number. For all realizations
we define the penalty to be $\beta$. Observe that we can see the nodes with
$\mathtt{HW}_{=1}$ as internal realizations. That is the target value for
their realization does not include the incident edges in the count. Then the
target value is the sum of all target values of the realizations plus $c_{R}$
to account for the dangling edges.

When the selected dangling edges correspond to some element $x_{i}\in R$, we
select all edges incident to $v_{i}$ and the extension to the realizations of
the nodes. Then all nodes are in a valid state. There is no larger solution,
as then one of the $\mathtt{HW}_{=1}$ nodes would be in an invalid state.
Further, for the $\mathtt{EQ}_{2\ell(d+1)}$ nodes it makes no difference if
all incident edges are selected or not, as they are realized. As the number of
selected dangling edges is always the same, the solution size is always the
same.

Now assume we are given a solution, where the dangling edges do not
corresponds to some $x\in R$. We show that this solution must be smaller by at
least $\beta$ compared to the optimal solution size. We can assume that all
$v_{i}$ nodes are in a valid state. Otherwise we would directly lose a factor
of $\beta$ for each of these node in an invalid state, as these are realized.
Assume there is no $v_{i}$ where all dangling edges are selected. Then all
nodes $a_{j}$ are in an invalid state, as each $a_{j}$ is connected to all
$v_{i}$. Hence, we lose a factor of at least $\beta$. If there is more than
one $v_{i}$ where all incident edges are selected, then by the same argument
all $a_{j}$ are in an invalid state as they are connected to at least two
edges and we lose $\beta$. Hence, there must be exactly one $v_{i}$ where all
incident edges are selected. Then all nodes $a_{j}$ are in a valid state. Let
$O^{\prime}$ be the set of the remaining nodes adjacent to $v_{i}$ in the
solution. By design, this corresponds to a $x\in R$ with $x[k]=0$ iff $k\in
O^{\prime}$. Let $O^{\prime\prime}$ be the nodes incident to a dangling edge
in the solution. Assume there is a $o\in O^{\prime}\cap O^{\prime\prime}$.
Then this node would be incident to two edges and we lose $\beta$. The same
argument holds for nodes $o\notin O^{\prime}\cup O^{\prime\prime}$. Hence,
$O^{\prime}$ is the complement of $O^{\prime\prime}$ and the dangling edges
correspond to an element of $R$, a contradiction. Thus, some node must be in
an invalid state and the solution is smaller by at least $\beta$.

##  7 Counting Version

From a certain perspective the optimization version can be seen as a
relaxation of the decision version: The assumption $\min B>0$ is dropped while
still assuming $\operatorname{max-gap}B>1$. For the counting version we now
even drop this last assumption such that there might be no gap at all in $B$.
Thus the only polynomial-time solvable cases for the counting version are
$B=\\{0\\}$ and $B=\emptyset$ with one and zero solutions, respectively. This
implies that we additionally must realize equality relations. Surprisingly
this also reduces to realizing $\mathtt{HW}_{=1}^{(1)}$ nodes in the end, i.e.
forcing edges.

We use the Holant framework and lemmas and definitions analogous to those from
[13]. A signature graph $\Omega$ is a graph with weights $w_{e}$ for all edges
$e$ and all vertices are labeled by _signatures_
$f_{v}\mathrel{\mathop{\mathchar 58\relax}}{\\{0,1\\}}^{I(v)}\to\mathbb{Q}$,
which are rational functions on the incidence vector $I(v)$ of the edges
adjacent to $v$. We define $\operatorname{Holant}(\Omega)$ to be the quantity

$\displaystyle\sum_{x\in\\{0,1\\}^{E(\Omega)}}\prod_{e\in x}w_{e}\prod_{v\in
V(\Omega)}f_{v}(x|_{I(v)}).$

The Holant framework can be seen as a natural generalization of GenFac. If
each signature $f_{v}$ is a symmetric Boolean function and each edge weight is
1, then it is exactly #GenFac. If additionally each vertex has signature
$\mathtt{HW}_{\in B}$, this corresponds to #$B$-Factor.

######  Definition 7.1 ($\operatorname{\mathtt{Holant}}(F)$).

If $F$ is a set of rational functions, we say that
$\operatorname{\mathtt{Holant}}(F)$ is the set of all Holant problems where
the signature graph has signatures only from $F$.

######  Definition 7.2 (Gate).

A gate is a signature graph $\Gamma$, possibly containing a set $D\subseteq
E(\Gamma)$ of dangling edges, all of which have edge weight 1. The signature
realized by $\Gamma$ is the function
$\textup{{SIG}}(\Gamma)\mathrel{\mathop{\mathchar
58\relax}}{\\{0,1\\}}^{D}\to\mathbb{Q}$ that maps an assignment of dangling
edges $x\in{\\{0,1\\}}^{D}$ to

$\displaystyle\textup{{SIG}}(\Gamma,x)=\sum_{y\in{\\{0,1\\}}^{E(\Gamma)\setminus
D}}\mathopen{}\left(\prod_{e\in E(\Gamma)}w(e)\prod_{v\in
V(\Gamma)}f_{v}\mathopen{}\left((x\cup
y)|_{I(v)}\right)\mathclose{}\right)\mathclose{}$

Note that unless mentioned otherwise, we restrict ourselves to signature
graphs with unit edge weights and hence they are usually omitted.

In essence, gates in the Holant framework play the role of realizations in the
previous sections. Given these definitions, we are now ready to state our main
theorem, which can then be used to prove Theorem 1.6.

######  Theorem 7.3.

For all fixed, finite $B\subseteq{\mathbb{N}}$ with $B\neq\\{0\\}$ there is a
$f\mathrel{\mathop{\mathchar 58\relax}}{\mathbb{N}}\to{\mathbb{N}}$ such that
the following holds. Let $G=(V_{S}\mathrel{\dot{\cup}}V_{C},E)$ be an instance
of #$B$-FactorR with a path decomposition of width ${\operatorname{pw}}$ such
that $\Delta^{*}=\max_{\text{bag }X}\sum_{v\in X\cap V_{C}}\deg(v)$. Then
there is a $f(\Delta^{*})n^{\mathcal{O}(1)}$ time Turing reduction from
#$B$-FactorR to #$B$-Factor such that for every constructed instance of
#$B$-Factor pathwidth and cutwidth increase at most by $f(\Delta^{*})$.

We postpone the proof of this reduction and first show the lower bound for the
counting version.

######  Proof 7.4 (Proof of Theorem 1.6).

Let $H$ be a #$B$-FactorR instance with $n_{H}$ nodes, pathwidth
${\operatorname{pw}}_{H}$, and $\Delta^{*}=\max_{\text{bag }X}\sum_{v\in
V_{C}\cap X}\deg(v)$. Then by Theorem 7.3, we get polynomially many instances
of #$B$-Factor such that
$n_{G}\in(n_{H}+\Delta^{*}+f(\Delta^{*}))^{\mathcal{O}(1)}$ with the $f$ from
the above theorem where
${\operatorname{pw}}_{G}\leq{\operatorname{pw}}_{H}+f(\Delta^{*})$. Now,
suppose that we can solve #$B$-Factor in the claimed running time. Then we can
solve #$B$-FactorR in time

$\displaystyle(\max B+1-\epsilon)^{{\operatorname{pw}}_{G}}\cdot
n_{G}^{\mathcal{O}(1)}$ $\displaystyle\leq(\max
B+1-\epsilon)^{{\operatorname{pw}}_{H}+f(\Delta^{*})}\cdot(n_{H}+f(\Delta^{*}))^{\mathcal{O}(1)}$
$\displaystyle\leq(\max
B+1-\epsilon)^{{\operatorname{pw}}_{H}+f(\Delta^{*})}\cdot
f^{\prime}(\Delta^{*})\cdot n_{H}^{\mathcal{O}(1)}$ $\displaystyle\leq(\max
B+1-\epsilon)^{{\operatorname{pw}}_{H}+f^{\prime\prime}(\Delta^{*})}\cdot
n_{H}^{\mathcal{O}(1)}$

for some $f^{\prime}$ and $f^{\prime\prime}$. But this immediately contradicts
#SETH by Corollary 4.10.

We can think of #$B$-FactorR as a Holant problem where the allowed signatures
are either $\mathtt{HW}_{\in B}$ or restricted even relations. We first use a
lemma from [13] to realize these relations through nodes with signature
$\mathtt{HW}_{=1}$. Since their constructions are in the perfect matching
setting, they can equivalently be seen as gates that use vertices with
signature $\mathtt{HW}_{=1}$. After using this lemma to reduce from
#$B$-FactorR to a Holant problem, we give a chain of reductions (see Figure 7)
that ends at #$B$-Factor and preserves the pathwidth up to an additive
constant.

Figure 7: The chain of reductions that starts with #$B$-FactorR and ends at
#$B$-Factor (i.e. $\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B})$).
Arrows show the direction of Turing or many-one reductions.

######  Lemma 7.5 (Lemma 3.3 from [13]).

Let $R\subseteq{\\{0,1\\}}^{e}$ be an even relation. Then there is a gate
$\Gamma$ that can realize it such that

  * •

$\Gamma$ only uses vertices with signature $\mathtt{HW}_{=1}$.

  * •

$\Gamma$ has $\mathcal{O}(\lvert R\rvert\cdot e)$ vertices and edges.

  * •

$\Gamma$ has maximum degree at most $\lvert R\rvert+\mathcal{O}(1)$.

  * •

the edges of $\Gamma$ have weights from $\\{-1,\frac{1}{2},1\\}$.

  * •

given $R$ as input, we can construct $\Gamma$ in time $\mathcal{O}(\lvert
R\rvert\cdot e)$.

######  Lemma 7.6.

#$B$-FactorR reduces in polynomial time to
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$ with
edge weights from $\\{-1,\frac{1}{2},1\\}$ such that the pathwidth and
cutwidth increase at most by a constant $c_{\Delta^{*}}$ depending only on
$\Delta^{*}$, where ${\Delta^{*}}$ is the maximum total degree of the complex
nodes in any bag of the path decomposition, and the maximum degree is
unaffected, or increases to 6.

######  Proof 7.7.

We replace the complex nodes with the appropriate gates from Lemma 7.5. This
gives us an instance of $\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in
B},\mathtt{HW}_{=1})$ with edge weights from $\\{-1,\frac{1}{2},1\\}$.
Further, this only alters the pathwidth and cutwidth by an additive factor
depending only on $\Delta^{*}$. However, the construction via Lemma 7.5 can
result in large degree $\mathtt{HW}_{=1}$ nodes. These can be replaced by
smaller degree $\mathtt{HW}_{=1}$ nodes (see the construction for the decision
version in Figure 4).

Since #$B$-Factor does not have edge weights, removing them is the next step
in our chain of reductions. We do this through polynomial interpolation. This
technique was first used by Valiant [43]. We will also use this idea further
down our chain of reductions, and give a general statement Proposition 7.10 to
aid us in this process. The idea is that we can recover the coefficients of a
polynomial $P(\cdot)$ if we know the value of $P(x)$ for sufficiently many
$x$. We represent the solution of one problem as the value of a polynomial
$P(\cdot)$ and represent the value of a second problem as some function $f(P)$
of the polynomial itself. Then, we can recover the value of the second problem
through sufficiently many invocations to an oracle of the first problem. This
gives us a Turing reduction from the second problem to the first.

######  Lemma 7.8.

There is a polynomial time Turing reduction from
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$ with
edge weights from $\\{-1,\frac{1}{2},1\\}$ to
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$ on
unweighted graphs such that the pathwidth and cutwidth increase only by a
fixed constant and the maximum degree increases to at least three.

######  Proof 7.9.

We follow the arguments from Theorem 4.1 of [13]. We replace $-1,\frac{1}{2}$
weight edges with weights $x,y$ and treat $\operatorname{Holant}(\Omega)$ as a
polynomial in $x,y$. Then, we can recover this polynomial by interpolating
with various values of $x,y$. We can choose the values for $x,y$ from
$\\{2^{i}\mid i\in{\mathbb{N}}\\}$ through the constructions from [13]: We
replace the edges with weight $2^{i}$ by a path with $2i+3$ edges where edges
number $3,5,\dots,2i+1$ have weight $2$ and the other edges have weight $1$.
Then we replace these edges with weight $2$ by two parallel edges and divide
both edges by two nodes. All new nodes are labeled with $\mathtt{HW}_{=1}$.
Observe that this construction increases pathwidth and cutwidth only by a
constant factor and the degree increases to at least $3$.

######  Proposition 7.10.

Suppose we have two non-zero sequences
$\\{A_{n}\\}_{n\in{\mathbb{N}}},\\{B_{n}\\}_{n\in{\mathbb{N}}}$ that are
related as

$\displaystyle\begin{bmatrix}A_{n}\\\
B_{n}\end{bmatrix}=M\begin{bmatrix}A_{n-1}\\\
B_{n-1}\end{bmatrix}=M^{n}U\qquad\text{, where }U=\begin{bmatrix}A_{0}\\\
B_{0}\end{bmatrix}$

and $M$ is a symmetric and invertible $2\times 2$ matrix such that $U$ is not
an eigenvector of $M$. Then $\\{\frac{B_{n}}{A_{n}}\\}_{n\in{\mathbb{N}}}$ is
a sequence which does not contain any repetitions.

######  Proof 7.11.

Suppose not. Then we have $\frac{B_{n}}{A_{n}}=\frac{B_{n+r}}{A_{n+r}}$ for
some positive integers $n,r$. Then since $\\{A_{n}\\},\\{B_{n}\\}$, are both
non-zero sequences we have

$\displaystyle k\begin{bmatrix}A_{n}\\\
B_{n}\end{bmatrix}=\begin{bmatrix}A_{n+r}\\\ B_{n+r}\end{bmatrix}$

for some $k$. Then we have

$\displaystyle k\begin{bmatrix}A_{n}\\\ B_{n}\end{bmatrix}$
$\displaystyle=kM^{n}U=M^{n+r}U=\begin{bmatrix}A_{n+r}\\\
B_{n+r}\end{bmatrix}\qquad\overset{M\text{ invertible}}{\implies}\qquad
kU=M^{r}U$

implying that $U$ is an eigenvector of $M^{r}$. Now, since $M$ is symmetric,
it has two eigenvectors that are linearly independent. Since these are also
eigenvectors of $M^{r}$ and they are linearly independent, these are the only
eigenvectors of $M^{r}$. Thus, $U$ must also be an eigenvector of $M$, giving
a contradiction.

We will see why we need the following lemma in Lemma 7.14. Observe that a
$\mathtt{HW}_{=1}$ node can be thought of as a vertex with list $\\{1\\}$. To
see the problem, consider the case when the list does not have gaps, for
example like in $\\{0,1,2,3,4\\}$. Then it is not immediate how to get a node
whose list has 1 but does not have 0. We avoid this by doing interpolation.

######  Lemma 7.12.

There is a polynomial time Turing reduction from
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$ to
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in
B},\mathtt{HW}_{\in\\{0,1\\}})$ such that pathwidth and cutwidth increase at
most by 1.

######  Proof 7.13.

Suppose we have an instance $\Omega$ of
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$. We
construct a new signature grid $\Omega^{\prime}$ by replacing all
$\mathtt{HW}_{=1}$ vertices with $\mathtt{HW}_{\in\\{0,1\\}}$ vertices. Let
this set of $\mathtt{HW}_{\in\\{0,1\\}}$ vertices be $U$. We note that
$\operatorname{Holant}(\Omega^{\prime})$ can be thought of as the summation of
$2^{\lvert U\rvert}$ Holants, where each vertex in $U$ is assigned to either
$\mathtt{HW}_{=0}$ or $\mathtt{HW}_{=1}$. Define $A_{i}$ as the partial
summation of the Holants on $\Omega^{\prime}$ where $i$ vertices from $U$ are
assigned $\mathtt{HW}_{=1}$ and the rest are assigned $\mathtt{HW}_{=0}$. That
is, we have that $\operatorname{Holant}(\Omega^{\prime})=\sum_{i=0}^{\lvert
U\rvert}A_{i}.$

Now for an integer $d\geq 1$, we construct a new graph $\Omega^{\prime}_{d}$
by attaching a length-$d$ path of $\mathtt{HW}_{\in\\{0,1\\}}$ to every node
in $U$. Let $P_{1}(d)$ be the number of solutions when the leading edge of the
path is selected, and similarly let $P_{0}(d)$ be the number of solutions when
the leading edge of the path is not selected. Then we have

$\operatorname{Holant}(\Omega^{\prime}_{d})=\sum_{i=0}^{\lvert
U\rvert}A_{i}(P_{0}(d))^{i}(P_{0}(d)+P_{1}(d))^{\lvert
U\rvert-i}=(P_{0}(d))^{\lvert U\rvert}\sum_{i=0}^{\lvert U\rvert}A_{\lvert
U\rvert-i}\biggl{(}\frac{P_{0}(d)+P_{1}(d)}{P_{0}(d)}\biggr{)}^{\\!\\!i}.$

We claim that by interpolation on $d$, we can recover the values of $A_{i}$
for any $i$. In particular, $A_{\lvert U\rvert}$ will correspond to
$\operatorname{Holant}(\Omega)$. To show this, we only need to argue that
$\frac{P_{0}(d)+P_{1}(d)}{P_{0}(d)}$ will take at least $\lvert U\rvert$
unique values, and that these are computable in polynomial time. Now, since
$P_{0},P_{1}$ can be defined for any integral path length $d$, we have the
relation

$P_{0}(d)=P_{1}(d-1)+P_{0}(d-1)\qquad\text{and}\qquad P_{1}(d)=P_{0}(d-1).$

Then, applying Proposition 7.10 with $M=\bigl{[}\begin{smallmatrix}1&1\\\
1&0\end{smallmatrix}\bigr{]}$ and $U=\bigl{[}\begin{smallmatrix}1\\\
1\end{smallmatrix}\bigr{]}$, and since $P_{0}(d),P_{1}(d)>0$ for every $d$, we
get the required statement. Since we are only attaching a path to certain
vertices, this does not alter the pathwidth or cutwidth by more than 1.

######  Lemma 7.14.

For every finite list $B\subseteq{\mathbb{N}}$, there is a polynomial time
many-one reduction from

  * •

$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in
B},\mathtt{HW}_{\in\\{0,1\\}})$ if $\max B-1\in B$,

  * •

$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$ if
$\max B-1\not\in B$,

to $\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in
B},\mathtt{HW}_{=1}^{(1)})$ increasing pathwidth and cutwidth by a fixed
constant and increasing the degrees of the $\mathtt{HW}_{\in\\{0,1\\}}$ or
$\mathtt{HW}_{=1}$ nodes by at most $\max B$.

######  Proof 7.15.

Consider any instance $\Omega$ of
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=1})$ or
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in
B},\mathtt{HW}_{\in\\{0,1\\}})$. It suffices to alter the nodes labeled with
$\mathtt{HW}_{=1}$ or $\mathtt{HW}_{\in\\{0,1\\}}$: We replace each of them by
a new node with relation $\mathtt{HW}_{\in B}$ and force $\max B-1$ edges by
adding the same number of pendant nodes with relation
$\mathtt{HW}_{=1}^{(1)}$. Depending on whether $\max B-1\in B$ or not, we get
a $\mathtt{HW}_{\in\\{0,1\\}}$ or a $\mathtt{HW}_{=1}$ node. Since we are
adding $\max B-1$ pendant nodes to certain vertices, the pathwidth increases
at most by 1 and the cutwidth increases by at most $\max B-1$.

At this stage, we only need to realize $\mathtt{HW}_{=1}^{(1)}$ nodes. We will
see that this is possible, but that there are some caveats. Like before, in
the case where $B$ only has even integers, some parity issues force us to be
able to realize only an even number of $\mathtt{HW}_{=1}^{(1)}$ nodes. This
can be seen as realizing $\mathtt{HW}_{=2}^{(2)}$ nodes instead.

######  Lemma 7.16.

For every fixed, finite list $B\subseteq{\mathbb{N}}$, there is a polynomial
time many-one reduction from $\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in
B},\mathtt{HW}_{=1}^{(1)})$ to
$\operatorname{\mathtt{Holant}}(\mathtt{HW}_{\in B},\mathtt{HW}_{=2}^{(2)})$
increasing pathwidth and cutwidth only by a fixed constant and leaving the
maximum degree unaffected, or increasing it to at most $\max B$.

######  Proof 7.17.

We claim that without loss of generality, we can assume that we have an even
number of $\mathtt{HW}_{=1}^{(1)}$ nodes. Suppose not. Then we consider two
cases.

  * •

If $B$ has some odd number $k$, then we add a separate component with one
$\mathtt{HW}_{\in B}$ node connected to $k$ $\mathtt{HW}_{=1}^{(1)}$ nodes.
This brings the total number of $\mathtt{HW}_{=1}^{(1)}$ nodes to be even. As
this component is a star graph, pathwidth does not change. Cutwidth increases
by at most $\max B$.

  * •

If $B$ only has even numbers, then we claim that $\operatorname{Holant}(G)$ is
zero. Consider the sum of the degrees of the nodes in any solution. The nodes
with relation $\mathtt{HW}_{=1}^{(1)}$ contribute an odd number, whereas the
other nodes with relation $\mathtt{HW}_{\in B}$ can only contribute an even
number. Thus, their sum must be odd. This contradicts the fact that the sum of
the degrees of the vertices in any graph must be even.