# Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction

Dániel Marx<EMAIL_ADDRESS>0000-0002-5686-8314 CISPA Helmholtz Center for
Information SecuritySaarland Informatics CampusSaarbrückenGermany

(2021)

###### Abstract.

Conditional lower bounds based on $\textup{P}\neq\textup{NP}$, the
Exponential-Time Hypothesis (ETH), or similar complexity assumptions can
provide very useful information about what type of algorithms are likely to be
possible. Ideally, such lower bounds would be able to demonstrate that the
best known algorithms are essentially optimal and cannot be improved further.
In this tutorial, we overview different types of lower bounds, and see how
they can be applied to problems in database theory and constraint
satisfaction.

computational complexity; conditional lower bounds; exponential-time
hypothesis; parameterized complexity; database queries; constraint
satisfaction problems

††journalyear: 2021††copyright: acmlicensed††conference: Proceedings of the
40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems; June
20–25, 2021; Virtual Event, China††booktitle: Proceedings of the 40th ACM
SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’21),
June 20–25, 2021, Virtual Event, China††price: 15.00††isbn:
978-1-4503-8381-3/21/06††doi: 10.1145/3452021.3458814††ccs: Theory of
computation Problems, reductions and completeness††ccs: Theory of computation
Database theory

##  1\. Introduction

The design of efficient algorithms is in the focus of a large part of
theoretical computer science research. The practical need to solve
computational problems efficiently makes the systematic study of algorithmic
efficiency highly motivated. Decades of research in algorithm design
discovered mathematically beautiful and sometimes very practical algorithmic
techniques that gave us deep insights into efficient computation in a wide
range of contexts and application domains. The field of computational
complexity treats algorithmic problems and computation as formal mathematical
objects and tries to prove relationships between them (Papadimitriou, 1994;
Arora and Barak, 2009).

Given the abundance of computation in our modern word, it is justified to
consider algorithms and computation as a fundamental mathematical objects, on
par with basic objects in geometry, algebra, and combinatorics. Researchers in
computational complexity try to learn as much as possible about the
mathematical nature of computation. But more pragmatically, computational
complexity can give very important messages to algorithm designers. By giving
information about limits of computation, it can prevent researchers from
wasting time in dead ends of study: trying to design algorithm for problems
that cannot be efficiently solved.

Having techniques to prove negative results can profoundly change the way
research in algorithms is done. For example, the theory of NP-hardness changed
the search for polynomial-time algorithms from a hit and miss effort to a more
systematically doable project. Without NP-hardness, we would not be able to
distinguish problems that do not admit polynomial-time algorithms from
problems where we just were not yet successful in finding algorithms. But with
the possibility of giving negative evidence in the form of NP-hardness, the
lack of a known answer means that the question is still an active research
problem: we typically expect that the algorithmic problem at hand can be
eventually classified as either polynomial-time solvable or NP-hard, and it is
worth trying to resolve the question one way or the other.

In a sense, computation complexity has not progressed much in the past 50
years despite intense efforts: the core questions underlying the hardness of
computation, such as the celebrated $\textup{P}\neq\textup{NP}$ problem, are
still wide open. However, by accepting certain well-chosen complexity
assumptions, such as the $\textup{P}\neq\textup{NP}$ hypothesis, we can obtain
_conditional lower bounds_ explaining the apparent complexity of a large
number of problems. As a general theme in computational complexity research,
we can see a proliferation of new assumptions. These assumptions typical
postulate that a certain type of algorithm does not exist for a particular
fundamental problem (e.g., for Boolean satisfiability). The assumptions are
chosen to be both plausible and have strong explanatory power: in many cases,
they are able to show that the algorithms that we currently have are optimal
and cannot be improved any further. Indeed, from the viewpoint of algorithm
design, this is precisely the role of computation complexity: to separate
problems where our current knowledge is complete from problems where there are
still algorithmic ideas waiting to be discovered.

Some of the complexity assumptions are standard (such as
$\textup{P}\neq\textup{NP}$), while others may be more controversial (such as
the Strong Exponential-Time Hypothesis (SETH)). Therefore, the reader may
wonder about the usefulness of proving conditional lower bounds based on
unproven assumptions. It is important to point out that these conditional
lower bounds are valuable even if we have doubts about the validity of the
assumptions. Suppose we use a complexity assumption $X$ to prove that a
certain type of algorithm does not exists for a specialized problem $P$,
perhaps in an application domain such as database theory. Even if we do not
believe in the validity of the assumption $X$, this conditional lower bound
shows that the difficulties we face when attacking problem $P$ have nothing to
do with the specific details of problem $X$ or the application area: we are
really facing assumption $X$ in disguise and we need to disprove that first
before any progress can be made on problem $P$. In other words, the
conditional lower bound shows that we can stop trying to obtain the desired
algorithm for problem $P$, as any such effort would be better spent on trying
to disprove the (typically more fundamental) assumption $X$.

The purpose of this article is to highlight some of the lower bound techniques
and show what kind of results they can deliver in the context of database
theory. We will introduce a number of assumptions, contrast them, and show
examples of their use. It has to be emphasized that this article does not aim
to be an up to date survey of lower bounds in the area of database theory. The
focus is more on the diverse set of assumptions and lower bound techniques
that exist, rather than on presenting an exhaustive list of applications for
each technique. Some of these example applications come directly from the
literature on database query evaluation, but others were stated in essentially
equivalent forms in other domains: for constraint satisfaction problems (CSP)
or for graph-theoretic problems. Therefore, we begin with introducing the
terminology for all these domains and then discuss the results using the most
appropriate terminology.

##  2\. The four domains

Conjunctive query evaluation is a fundamental problem in database theory. This
problem can be equivalently seen as a CSP instance and therefore some of the
results in the CSP literature are directly relevant. A large part of the CSP
literature uses a formulation using the homomorphism of relational structures,
which in some special cases degenerate to traditional graph problems. In this
section, we introduce the terminology for all these domains and show how they
are connected to each other.

###  2.1. Database queries

A _join query_ $Q$ is an expression of the form

$R_{1}(a_{11},\ldots,a_{1r_{1}})\bowtie\cdots\bowtie
R_{m}(a_{m1},\ldots,a_{mr_{m}}),$

where the $R_{i}$ are _relation names_ with _attributes_
$a_{i1},\ldots,a_{ir_{i}}$. Let $A$ be the set of all attributes occurring in
$Q$ and $n=|A|$. A _database instance_ D for $Q$ consists of a domain
$\textup{dom}(\textbf{D})$ and relations
$R_{i}(\textbf{D})\subseteq\textup{dom}(\textbf{D})^{r_{i}}$ of arity $r_{i}$.
It is common to think of the relation $R_{i}(\textbf{D})$ as a table whose
columns are labeled by the attributes $a_{i1},\ldots,a_{ir_{i}}$ and whose
rows are the tuples in the relation. The _answer_ , or _set of solutions_ , of
the query $Q$ in D is the $n$-ary relation $Q(\textbf{D})$ with attributes $A$
consisting of all tuples $t$ whose projection on the attributes of $R_{i}$
belongs to the relation $R_{i}(\textbf{D})$, for all $i$. Given the query $Q$
and the database $D$, the task in the Join Query problem is to compute the set
$Q(\textbf{D})$. In the Boolean Join Query problem, we only need to decide if
$Q(\textbf{D})$ is empty or not. One can also define the counting version of
the problem (i.e, compute $|Q(\textbf{D})|$).

The primal graph of the query has the set $A$ of attributes as vertex set and
two variables are adjacent if there is a relation containing both of them. The
hypergraph of the instance is defined similarly: the vertex set is $A$, and
each relation $R_{i}(a_{i1},\dots,a_{ir_{i}})$ is represented by a hyperedge
$\\{a_{i1},\dots,a_{ir_{i}}\\}$.

###  2.2. Constraint satisfaction problems

Constraint satisfaction is a general framework that includes many standard
algorithmic problems such as satisfiability, graph coloring, database queries,
etc. A constraint satisfaction problem (CSP) instance consists of a set $V$ of
variables, a domain $D$, and a set $C$ of constraints, where each constraint
is a relation on a subset of the variables. The task is to assign a value from
$D$ to each variable in such a way that every constraint is satisfied. For
example, 3SAT can be interpreted as a CSP instance where the domain is
$\\{0,1\\}$ and the constraints in $C$ correspond to the clauses (thus the
arity of each constraint is 3).

Formally, an instance $I$ of a constraint satisfaction problem is a triple
$I=(V,D,C)$, where:

  * •

$V$ is a set of variables,

  * •

$D$ is a domain of values,

  * •

$C$ is a set of constraints, $\\{c_{1},c_{2},\dots,c_{q}\\}$. Each constraint
$c_{i}\in C$ is a pair $\langle s_{i},R_{i}\rangle$, where:

    * –

$s_{i}$ is a tuple of variables of length $m_{i}$, called the constraint
scope, and

    * –

$R_{i}$ is an $m_{i}$-ary relation over $D$, called the constraint relation.

For each constraint $\langle s_{i},R_{i}\rangle$ the tuples of $R_{i}$
indicate the allowed combinations of simultaneous values for the variables in
$s_{i}$. The length $m_{i}$ of the tuple $s_{i}$ is called the arity of the
constraint. A solution to a constraint satisfaction problem instance is a
function $f$ from the set of variables $V$ to the domain $D$ of values such
that for each constraint $\langle s_{i},R_{i}\rangle$ with
$s_{i}=(v_{i_{1}},v_{i_{2}},\dots,v_{i_{m}})$, the tuple
$(f(v_{i_{1}}),f(v_{i_{2}}),\dots,f(v_{i_{m}}))$ is a member of $R_{i}$. Given
a CSP instance $I$, we can consider the problem of deciding if a solution
exists, the problem of finding all solutions, or the problem of counting the
number of solutions.

We say that an instance is binary if each constraint relation is binary, that
is, $m_{i}=2$ for every constraint111It is unfortunate that while some
communities use the term “binary CSP” in the sense that each constraint is
binary (as does this dissertation), others use it in the sense that the
variables are 0-1, that is, the domain size is 2.. The primal graph (or
Gaifman graph) of a CSP instance $I=(V,D,C)$ is a graph $G$ with vertex set
$V$, where $x,y\in V$ form an edge if and only if there is a constraint
$\langle s_{i},R_{i}\rangle\in C$ with $x,y\in s_{i}$. The _hypergraph_ of an
instance $I=(V,D,C)$ has $V$ as its vertex set and for every constraint in $C$
a hyperedge that consists of all variables occurring in the constraint.

Given a join query $Q$ and a database D, we can turn the query problem into a
CSP instance $I$ in a straightforward way: the domain of $I$ is
$\textup{dom}(\textbf{D})$, the set of variables correspond to the attributes
$A$ of $Q$, and for each relation $R_{i}$, there is a corresponding constraint
$c_{i}$ on the variables $a_{i1}$, $\dots$, $a_{ir_{i}}$. It is clear that the
tuples in the answer set of $Q$ in D are in one to one correspondence with the
solutions of the CSP instance $I$. This establishes a correspondence between
the basic algorithmic problems of the two domains.

It is worth pointing out that even though the two problems are equivalent, a
large part of CSP research focuses on problem instances where the domain has
small constant size and the number of constraints is large (for example, 3SAT
is such a problem). This has to be contrasted with the typical setting in
database theory research where we assume that there are only a small number of
attributes and relations have low arity, but the domain can be large and the
number of tuples in a relation can be large.

###  2.3. Graph problems

Given a binary CSP instance $I=(V,D,C)$, we can equivalently formulate it as a
graph problem. We construct a graph $G$ the following way: let us introduce
$|V|\cdot|D|$ vertices $w_{v,d}$ ($v\in V$, $d\in D$) and for ever constraint
$c_{i}=\langle(u,v),R_{i}\rangle$, let us make $w_{u,d_{1}}$ and $w_{v,d_{2}}$
adjacent if and only if $(d_{1},d_{2})\in R_{i}$. Let $W_{i}=\\{w_{i,d}\mid
d\in D\\}$ and consider the partition $\mathcal{P}=\\{W_{1},\dots,W_{|V|}\\}$.
We say that a subgraph $H$ of $G$ respects the partition $\mathcal{P}$ if
every class of the partition $\mathcal{P}$ contains exactly one vertex of $H$.

Let $f:V\to D$ be a solution of $I$. If we consider the vertices
$\\{w_{v,f(v)}\mid v\in V\\}$, then it is easy to see that they induce a
subgraph $H$ that respects $\mathcal{P}$ and isomorphic to the primal graph of
$I$. Conversely, it is not difficult to see that if $G$ has a subgraph that
respects $\mathcal{P}$ and is isomorphic to the primal graph of $I$, the it
describes a solution of $I$. Therefore, the CSP instance can be described by
an instance of partitioned subgraph isomorphism: given graphs $H$ and $G$, and
partition $\mathcal{P}$ of $V(G)$ into $|V(H)|$ classes, find a subgraph of
$V$ that respects $\mathcal{P}$ and is isomorphic to $H$. This problem is a
natural variant of the standard subgraph isomorphism problem (find a subgraph
of $G$ isomorphic to $H$) and, as we have seen, its complexity is tightly
connected to the complexity of CSP instances where the primal graph is $H$.

There is another way in which graph-theoretic notions can describe the
solutions of a CSP instance. Consider a binary CSP instance $I=(V,D,C)$ where
every constraint $c_{i}=\langle(u,v),R_{i}\rangle$ contains the same binary
relation $R_{i}=R$, which we further assume to be symmetric (that is,
$(d_{1},d_{2})\in R$ if and only $(d_{2},d_{1})\in R$). Let $H$ be the primal
graph of $I$ and let $G$ be a graph with vertex set $D$ where $d_{1},d_{2}\in
D$ are adjacent if and only if $(d_{1},d_{2})\in R$. A homomorphism from $H$
to $G$ is a mapping $f:V(H)\to V(G)$ such that if $u$ and $v$ are adjacent in
$H$, then $f(u)$ and $f(v)$ are adjacent in $G$. Note that $f$ does not have
to be injective (i.e., $f(u_{1})=f(u_{2})$ is possible) and if $u$ and $v$ are
not adjacent, then we do not require that $f(u)$ and $f(v)$ be nonadjacent as
well. It is easy to see that every solution $f:V\to D$ of $I$ describes a
homomophism from $H$ to $G$, in fact, these homomorphisms are in one to one
correspondence with the solutions of $I$. Therefore, the complexity of finding
a homomorphism from a fixed graph $H$ to the input graph $G$ is tightly
connected to the complexity of CSP for instances with primal graph $H$ where
the same symmetric relation $R$ appears in every constraint. If the relation
$R$ is not symmetric, then a similar connection can be made to the
homomorphism problem in directed graphs.

###  2.4. Relational structures

The connection between CSP and graph homomorphisms that we have seen in the
previous section has two major limitations: it worked only for binary CSP
instances and only if every constraint contained the same relation $R$. These
limitations can be removed if we move from graphs to the much more general
setting of relational structures.

A vocabulary $\tau$ is a finite set of relation symbols of specified arities.
The arity of $\tau$ is the maximum of the arities of all relational symbols it
contains. A $\tau$-structure $\mathbf{A}$ consists of a finite set $A$ called
the universe of $\mathbf{A}$ and for each relation symbol $R\in\tau$, say, of
arity $k$, a $k$-ary relation $R^{\mathbf{A}}\subseteq A^{k}$. A homomorphism
from a $\tau$-structure $\mathbf{A}$ to a $\tau$-structure $\mathbf{B}$ is a
mapping $h:A\to B$ from the universe of $\mathbf{A}$ to the universe of
$\mathbf{B}$ that preserves all relations, that is, for all $R\in\tau$, say,
of arity $k$, and all tuples $(a_{1},\dots,a_{k})\in R^{\mathbf{A}}$ it holds
that $(h(a_{1}),\dots,h(a_{k}))\in R^{\mathbf{B}}$. Note that if $\tau$
contains only a single relational symbol, which has arity $2$, then
$\tau$-structures are essentially directed graphs and the homomorphism problem
between $\tau$-structures is equivalent to the homomorphism problem on
directed graphs.

More generally, we can express every CSP instance $I=(V,D,C)$ as a
homomorphism problem the following way. Let $c=|C|$ be the number of
constraints. Let the vocabulary $\tau$ contain $c$ symbols $Q_{1}$, $\dots$
$Q_{c}$, where symbol $Q_{i}$ has the same arity $m_{i}$ as the constraint
$c_{i}=\langle s_{i},R_{i}\rangle$. We define $\tau$-structure $\mathbf{A}$
over the universe $V$ such that $Q^{\mathbf{A}}_{i}$ contains only the tuple
$s_{i}$. We define $\tau$-structure $\mathbf{B}$ over the universe $D$ such
that $Q^{\mathbf{B}}_{i}$ is precisely the relation $R_{i}$ appearing in
constraint $c_{i}$. Now it can be verified that a mapping $f:V\to D$ is a
solution of $I$ if and only if $f$ is a homomorphism from $\mathbf{A}$ to
$\mathbf{B}$.

##  3\. Unconditional lower bounds

Ideally, we would like to prove negative results and lower bounds that are
incontestably true mathematical statements. However, our inability to prove
the $\textup{P}\neq\textup{NP}$ hypothesis is a major barrier that prevents us
from proving most negative statements of interest. For all we know, it is
still possible that $\textup{P}=\textup{NP}$ and we can solve all database
query and CSP instances in polynomial time, and hence at the moment we cannot
expect to unconditionally prove any result that rules out such algorithms. As
long as we are in the classical setting of computation typically studied in
computational complexity (algorithm is given an input, needs to compute a yes-
no output), there is little hope in proving strong unconditional lower bounds.

We can hope to obtain unconditional lower bounds only if we deviate from the
classical setting: for example, the problem involves the cost of accessing the
input or the cost of communication. We show a particular, very simple setting
in which we have tight unconditional lower bounds. If the task is to compute
the answer to a join query, then the size of the answer is obviously an
unconditional lower bound on the number of steps needed for computing the
answer. This raises the question: what bounds can we give on the size of the
answer and are there query evaluation algorithms that match this lower bound?

Formally, let $Q=R_{1}(a_{11},\ldots,a_{1r_{1}})\bowtie\cdots\bowtie
R_{m}(a_{m1},\ldots,a_{mr_{m}})$ be a join query and let D be a database
instance for $Q$ such that every relation $R_{i}(\textbf{D})$ contains at most
$N$ tuples. What can we say about the size of the answer? It is easy to see
that $N^{m}$ is an obvious upper bound: every tuple appearing in the answer
chooses one of the at most $N$ possibilities in each of the $m$ relations. But
this bound is often very far from being tight. For example, for the query
$Q=R_{1}(a_{1},a_{2})\bowtie R_{2}(a_{1},a_{3})\bowtie R_{3}(a_{2},a_{3})$, it
is known that the upper bound is $N^{3/2}$ instead of $N^{3}$. The fractional
number $3/2$ in the exponent of $N$ suggests that obtaining the bound cannot
be completely obvious. Still, precise bounds can be obtained in a clean way
using known combinatorial techniques.

Let us define the hypergraph $H$ of the query $Q$ the following way: the
vertices are the attributes and we introduce a hyperedge
$\\{a_{i1},\dots,a_{ir_{i}}\\}$ for each relation
$R_{i}(a_{i1},\dots,a_{ir_{i}})$. A fractional cover of a hypergraph $H$ is a
mapping $f:V(H)\to[0,1]$ such that for every vertex $v\in V(H)$, we have
$\sum_{e\in E(H),v\in e}f(e)\geq 1$. That is, $f$ is a weight assignment on
the edges such that the total weight put on each vertex $v$ is at least 1. The
weight of $f$ is $\sum_{e\in E(H)}f(e)$ and the _fractional edge cover number
$\rho^{*}(H)$_ of $H$ is the minimum weight of a fractional edge cover of $H$.
For example, for the query $Q=R_{1}(a_{1},a_{2})\bowtie
R_{2}(a_{1},a_{3})\bowtie R_{3}(a_{2},a_{3})$, the hypergraph $H$ is a
triangle and $\rho^{*}(H)=3/2$ (assigning weight $1/2$ to each edge is a
fractional edge cover and a quick analysis shows that this is optimal).

Using a simple application of Shearer’s Lemma (Chung et al., 1986), which is a
purely combinatorial statement on entropy, one can show that $N^{\rho^{*}(H)}$
is an upper bound on the number of solutions.

###### Theorem 3.1 (Atserias, Grohe, Marx (Atserias et al., 2013)).

Let $Q$ be a join query with hypergraph $H$. Let $\mathbf{D}$ be a database
for $Q$ where every relation has at most $N$ tuples. Then the answer of $Q$ in
$\mathbf{D}$ has size at most $N^{\rho^{*}(H)}$.

Conversely, we can show that $N^{\rho^{*}(H)}$ is essentially a tight lower
bound. As it is usual with lower bound statements, we have to be a bit more
careful with the formulation.

###### Theorem 3.2 (Atserias, Grohe, Marx (Atserias et al., 2013)).

Let $Q$ be a join query with hypergraph $H$. For infinitely many $N\geq 1$,
there is a database $\mathbf{D}_{N}$ for $Q$ where every relation has at most
$N$ tuples and the answer of $Q$ in $\mathbf{D}_{N}$ has size at least
$N^{\rho^{*}(H)}$.

Theorem 3.2 provides an unconditional lower bound for any algorithm computing
the full answer of $Q$ (but of course it does not provide any bound on
algorithms that just decide whether the answer is empty or compute the size of
the answer). Are there algorithms that match this lower bound? The
combinatorial proof of Theorem 3.1 can be turned into an algorithm with a
constant overhead in the exponent, that is, to obtain $N^{\rho^{*}(H)+O(1)}$
running time. With additional techniques, it is possible to give tight
algorithms that tightly match the lower bound.

###### Theorem 3.3 ((Veldhuizen, 2014; Ngo et al., 2018)).

Let $Q$ be a join query with hypergraph $H$. Let $\mathbf{D}$ be a database
for $Q$ where every relation has at most $N$ tuples. Then the answer of $Q$ in
$\mathbf{D}$ can be computed in time $O(N^{\rho^{*}(H)})$.

##  4\. NP-hardness

Since its conception and development in the early 70s (Cook, 1971; Karp, 1972;
Garey and Johnson, 1979), NP-hardness has been the main workhorse of providing
intractability results for computational problems. The class NP contains
decision problems that can be solved in nondeterministic polynomial time. This
robust definition covers (the decision version of) most combinatorial and
optimization problems of interest. If a problem $P$ is NP-hard, then this
means in particular that a polynomial-time algorithm for $P$ would give
polynomial-time algorithms for every problem in NP, which we take as strong
evidence that such an algorithm is unlikely. We prove NP-hardness of $P$ by
giving a _polynomial-time reduction_ from a known NP-hard problem $Q$; this
reduction shows that a polynomial-time algorithm for $P$ would give a
polynomial-time algorithm for $Q$ and hence for every problem in NP.

Most of the problems studied in database theory or in CSP research are
obviously NP-hard, as they contain basic hard problems as special cases.
Therefore, it is not completely obvious how to ask reasonable questions about
NP-hardness where the answer is not trivial. One direction is to consider
restricted parameter values. For example, for CSP problems, one may ask if the
problem remains NP-hard if we restrict the domain size $|D|$ to 2 (yes, as
3SAT is still a special case), or restrict the constraints to binary (yes,
3-Coloring is a special case), or we apply both restrictions (no, with $|D|=2$
and binary constraints the problem becomes the polynomial-time solvable 2SAT).
Restricting the number $|V|$ of variables to any constant, say 10, gives a
polynomial-time solvable special case even if the domain size $|D|$ is
arbitrarily large (as we can try the at most $|D|^{10}$ possible assignments
in polynomial time).

More generally, we can introduce restrictions on the problem in a systematic
way and determine which of the restrictions lead to polynomial-time solvable
and NP-hard special cases. In CSP research, a very well studied family of
special cases arise from restricting the type of relations that are allowed in
the constraints. Formally, let $D$ be a finite domain and let $\mathcal{R}$ be
a finite set of relations over $D$. Then we denote by CSP($\mathcal{R}$) the
special case of the general CSP problem where the instance is allowed to
contain only constraints $c=\langle s,R\rangle$ where $R\in\mathcal{R}$.
Equivalently, we can state this restriction in the language of the
homomorphism problem in a very compact way. Let $\tau$ be a vocabulary and let
$\mathbf{B}$ be a $\tau$-structure. Then $\textsc{HOM}(\\_,\mathbf{B})$ is the
special case of the general homomorphism problem where the input is a pair
$(\mathbf{A},\mathbf{B})$ of $\tau$-structures, where $\mathbf{A}$ is
arbitrary.

A classic result of Schaefer (Schaefer, 1978) characterized the complexity of
$\textsc{CSP}(\mathcal{R})$ for any fixed finite set $\mathcal{R}$ of relation
over the Boolean domain (i.e., $|D|=2$). More precisely, Schaefer’s Dichotomy
Theorem showed that every such $\textsc{CSP}(\mathcal{R})$ problem is either
polynomial-time solvable or NP-hard, and gave a clean characterization of the
two cases. For several years, it was an outstanding open problem to prove an
analog of this result for larger fixed domains (the Feder-Vardi Conjecture
(Feder and Vardi, 1999)). After partial progress, the conjecture was resolved
in 2016 independently by Bulatov (Bulatov, 2017) and Zhuk (Zhuk, 2017).

While these classification results are cornerstones of modern CSP research,
translating them into the language of database theory does not give much
useful insight. Indeed, these characterization results would concern special
cases where the domain of the attributes have constant size and every database
relations is of constant size. From the viewpoint of database theory, a more
relevant family of special cases can be obtained by restricting the structure
of the query. Let us focus on Boolean Join Query, the problem of deciding if
the answer set is empty or not. If we assume, for example, that the primal
graph of the query is a tree (acyclic graph), then it is easy to solve the
problem in polynomial time, while the problem may remain NP-hard under other
restrictions (for example, under the assumption that the primal graph has
maximum degree 3 or is a planar graph etc.). Formally, in the language of
CSPs, if $\mathcal{G}$ is any class of graphs, we may want to understand the
complexity of the problem $\textup{CSP}(\mathcal{G})$, which is CSP under the
restriction that the primal graph belongs to class $\mathcal{G}$.

Can we identify every class $\mathcal{G}$ that leads to polynomial-time
solvable special cases and use NP-hardness to give evidence of hardness for
every other case? It is known that if $\mathcal{G}$ contains only graphs of
bounded treewidth, then $\textup{CSP}(\mathcal{G})$ becomes polynomial-time
solvable. Treewidth is a combinatorial measure of graphs that can be though of
as a number expressing how treelike the graph is: treewidth is 1 if and only
if the graph is an acyclic forest, while other fixed values mean that the
graph is similar to a tree with each node being replaced by a small graph.
While the formal definition of treewidth is technical, it models very
faithfully the requirements that make the algorithmic paradigm “split on small
separators and recurse” work and its mathematical naturality is further
evidenced by the fact that it was independently discovered in equivalent
formulations at least three times (Halin, 1976; Bertelè and Brioschi, 1973;
Robertson and Seymour, 1984). The precise definition of treewidth is not
essential for this paper; we include the definition here only for
completeness.

###### Definition 4.1.

A _tree decomposition_ of a graph $G$ is a pair $(\mathcal{B},T)$ where $T$ is
a tree and $\mathcal{B}=\\{B_{t}\mid t\in V(T)\\}$ is a collection of subsets
of $V(G)$ such that:

  * •

$\bigcup_{t\in V(T)}B_{t}=V(G)$,

  * •

for each edge $xy\in E(G)$, $\\{x,y\\}\subseteq B_{t}$ for some $t\in V(T)$;

  * •

for each $x\in V(G)$ the set $\\{t\mid x\in B_{t}\\}$ induces a connected
subtree of $T$.

The _width_ of the tree decomposition is $\max_{t\in V(T)}\\{|B_{t}|-1\\}$.
The _treewidth_ of a graph $G$ is the minimum width over all tree
decompositions of $G$. We denote by $\textup{tw}(G)$ the treewidth of graph
$G$.

Freuder (Freuder, 1990) showed that if the primal graph has bounded treewidth,
then the instance can be solved in polynomial time. By now, the result can be
obtained by standard dynamic programming techniques on tree decompositions.

###### Theorem 4.2 (Freuder (Freuder, 1990)).

For every fixed $k$, a CSP instance $I=(V,D,C)$ can be solved in time
$O(|V|\cdot|D|^{k+1})$ if the primal graph has treewidth at most $k$.

It follows from Theorem 4.2 that $\textup{CSP}(\mathcal{G})$ is polynomial-
time solvable if $\mathcal{G}$ has bounded treewidth, and it is easy to find
graph classes $\mathcal{G}$ with unbounded treewidth (e.g., cliques) where the
problem remains NP-hard. But, surprisingly, there seem to be cases that are
neither polynomial-time solvable or NP-hard, thus a full classification into
these two categories does not seem to be possible.

In the introduction, we mentioned that typically we expect that the problem at
hand can be eventually classified as either polynomial-time solvable or NP-
hard. While this may be true in most cases, there is no mathematical reason
why this should be true in general. In fact, Ladner’s Theorem (Ladner, 1975)
states that if $\textup{P}\neq\textup{NP}$, then there are NP-intermediate
problems in the class NP: problems that are neither polynomial-time solvable
nor NP-hard. The proof of Ladner’s Theorem produces NP-intermediate problems
that are highly artificial, so it is a different question whether there are
natural problems that are NP-intermediate. There are two problems that are
often highlighted as natural candidates for being NP-intermediate: Graph
Isomorphism and Integer Factorization. These two problems are not expected to
be polynomial-time solvable, and the fact that they can be solved much more
efficiently than brute force (Babai, 2016; Babai and Luks, 1983; Lenstra and
Pomerance, 1992) suggests that they are not NP-hard either.

One could say that the reason why Graph Isomorphism and Integer Factorization
are NP-intermediate is that the deep algebraic and number-theoretic structures
underlying these problems make them occupy a special place in the complexity
landscape of NP problems. However, it is important to point out that problems
can be (probably) NP-intermediate for more pedestrian reasons: it is possible
to scale down an NP-hard problem in a way that it no longer NP-hard, but still
not sufficiently easy to be polynomial-time solvable. We will refer to the
following (artificial) example also in later sections.

###### Definition 4.3.

A graph $G$ is special if it has exactly two connected components: a clique of
size $k$ for some integer $k\geq 1$ and a path of exactly $2^{k}$ vertices.
Special CSP and Special Boolean Join Query are the restricted cases of the
general problems where we assume that the primal graph is special.

Let us give some intuitive arguments why these problems could be NP-
intermediate (we will make this more formal in later sections). First, the
path part can be solved efficiently in polynomial time. Then we need to solve
the clique part, which can certainly be done by brute force in time
$O(n^{k})$, where $n$ is the total length of the input. But as already the
primal graph has size larger than $2^{k}$, we have $n\geq 2^{k}$ and hence
$k\leq\log n$. Thus we can solve the problem in quasipolynomial time
$n^{O(\log n)}$, which would be an exceptionally unusual property of an NP-
hard problem. Moreover, it is not clear what substantial improvements we can
expect on this algorithm: one would need to solve the clique part
significantly faster than brute force. Therefore, it seems that these problems
variants are likely to be NP-intermediate with best possible running time
around $n^{O(\log n)}$.

This example shows that even if we just want to understand which special cases
are polynomial-time solvable, then NP-hardness may not be sufficient for this
purpose. As we shall see in later sections, we need to use other lower bound
techniques for this type of classification. Additionally, these lower bound
techniques can provide stronger lower bounds beyond just ruling out
polynomial-time algorithms, showing the optimality of certain algorithms in a
tighter way.

##  5\. Parameterized Intractability

Parameterized complexity considers algorithmic problems where each input
instance has a parameter $k$ associated with it. This parameter is typically
either the size of the solution we are looking for or some measure of the
input, such as the number of variables in a formula, the dimension of the
input point set, the maximum degree of the input graph, or perhaps the
alphabet size of the input strings. The central goal of parameterized
complexity is to develop algorithms that are efficient on instances where the
value of the parameter is small. Formally, we say that a parameterized problem
is fixed-parameter tractable (FPT) if it can be solved in time $f(k)\cdot
n^{O(1)}$, where $n$ is the size of the input and $f$ is a computable function
depending only on $k$. This form of running time has to be contrasted with the
running time $n^{O(k)}$ of brute force algorithms that are often easily
achievable if $k$ is the size of the solution we are looking for. Research in
the past three decades has shown that many of the natural NP-hard problems are
FPT with various parameterizations, leading to algorithms that are often
highly nontrivial and combinatorially deep (Cygan et al., 2015; Downey and
Fellows, 2013, 1999; Flum and Grohe, 2006).

As an example, let us consider Vertex Cover: given a graph $G$ and an integer
$k$, the task is to find a vertex cover $S$ of size at most $k$, that is, a
set $S$ of at most $k$ vertices such that every edge of $G$ has at least one
endpoint in $S$. Clearly, we can solve the problem by brute force on an
$n$-vertex graph by trying each of the $O(n^{k})$ sets $S$ of size at most
$k$. But more efficient algorithms are available: a standard application of
the bounded-depth search tree technique already delivers a $2^{k}\cdot
n^{O(1)}$ algorithm, which can be further refined with additional techniques
(Chen et al., 2001). This means that Vertex Cover is FPT parameterized by the
size of the solution. For Clique, the trivial $O(n^{k})$ brute force search
can be improved to about $O(n^{\omega k/3})$) (where $\omega<2.3729$ is the
exponent for matrix multiplication (Alman and Williams, 2021; Nešetřil and
Poljak, 1985, 1985)), but no FPT algorithm is known despite significant
efforts.

Motivated by this apparent difference between Vertex Cover and Clique, Downey
and Fellows introduced the notion of W[1]-hardness and the
$\textup{FPT}\neq\textup{W[1]}$ hypothesis (Downey and Fellows, 1999). We omit
here the technical definitions related to the class W[1]; for the purpose of
proving negative evidence, it is sufficient to know that
$\textup{FPT}\neq\textup{W[1]}$ is equivalent to the statement “Clique is not
FPT” (or to “Independent Set is not FPT”, as the two problems are equivalent
by taking the complement of the graph). To define W[1]-hardness, we need first
the following notion of reduction:

###### Definition 5.1.

Let $P$ and $Q$ be two parameterized problems. A parameterized reduction
transforms an instance $x$ of $P$ with parameter $k$ to an instance
$x^{\prime}$ of $Q$ with parameter $k^{\prime}$ such that

  1. (1)

$(x,k)$ is a yes-instance of $P$ if and only if $(x^{\prime},k^{\prime})$ is a
yes-instance of $Q$.

  2. (2)

The running time of the reduction is $f(k)|x|^{O(1)}$ for some computable
function $f$.

  3. (3)

We have $k^{\prime}\leq f(k)$ for some computable function $f$.

The third requirement is what makes this notion very different from usual
polynomial-time reductions: we have to pay extra attention not to blow up too
much the parameter $k$ in the reduction. Parameterized reductions were
designed in a way that they transfer the property of being FPT: it can be
shown that if there is a parameterized reduction from $P$ to $Q$ and $Q$ is
FPT, then $P$ is FPT as well. We can define W[1]-hardness by saying that a
problem $P$ is W[1]-hard if there is a parameterized reduction from Clique to
$P$. We can interpret this as evidence that $P$ is not FPT: an FPT algorithm
for $P$ would show that Clique is FPT, violating the
$\textup{FPT}\neq\textup{W[1]}$ hypothesis.

Let us have a look at the complexity of CSP via the lens of parameterized
complexity. Given a instance $I=(V,D,C)$, we can introduce the number $k=|V|$
of variables as the parameter of the instance. We can decide if there is a
solution by trying each of the $|D|^{k}=O(n^{k})$ possible assignments. The
NP-hardness of the problem implies that this cannot be improved to $n^{O(1)}$
(assuming $\textup{P}\neq\textup{NP}$), but this does not rule out the
possibility that the problem is FPT parameterized by $k$, that is, there is a
$f(k)\cdot n^{O(1)}$ time algorithm. Such an algorithm would be certainly of
interest in contexts where we can assume that $k$ is small, but $D$ is large
(which is typically true in database applications). However, it is easy to see
that the problem of finding a clique of size $k$ in a graph $G$ can be
expressed as a CSP problem with $k$ variables, $\binom{k}{2}$ constraints, and
domain $D=V(G)$. That is, there is a parameterized reduction from Clique to
CSP parameterized by the number of variables, showing that the latter problem
is unlikely to be FPT either.

We can now return to the question left open at the end of Section 4: what are
those classes $\mathcal{G}$ for which $\textsc{CSP}(\mathcal{G})$ is
polynomial-time solvable? As we have seen, NP-hardness does not seem to be
sufficiently strong to highlight all the negative cases. Instead, let us look
at the fixed-parameter tractability of $\textsc{CSP}(\mathcal{G})$,
parameterized by the number $k$ of variables. Now if
$\textsc{CSP}(\mathcal{G})$ can be proved to be W[1]-hard for some
$\mathcal{G}$, then this implies in particular that it is not polynomial-time
solvable, assuming $\textup{FPT}\neq\textup{W[1]}$.

For example, let $\mathcal{G}$ contain every special graph, as defined in
Definition 4.3, and let us consider Special CSP (that is,
$\textsc{CSP}(\mathcal{G})$) parameterized by the number of variables. Given
an instance of Clique (a graph $G$ where it has to be decided if there is a
clique of size $k$), then we can express it as a Special CSP instance as
follows. We introduce $k$ variables connected by $\binom{k}{2}$ binary
constraints to express the problem of finding a $k$-clique, and additionally
we introduce $2^{k}$ dummy variables connected by constraints forming a path.
The primal graph is a $k$-clique plus a path on $2^{k}$ vertices, as required
in Special CSP. The reduction turns the problem of finding a $k$-clique to a
Special CSP instance on $f(k)=k+2^{k}$ variables, hence this is a proper
parameterized reduction. It follows that Special CSP is W[1]-hard
parameterized by the number of variables, and hence unlikely to be polynomial-
time solvable.

More generally, Grohe, Schwentick, and Segoufin (Grohe et al., 2001) proved
that if $\mathcal{G}$ has unbounded treewidth, then
$\textsc{CSP}(\mathcal{G})$ is W[1]-hard, leading to a complete
classification.

###### Theorem 5.2 (Grohe, Schwentick, and Segoufin (Grohe et al., 2001)).

Let $\mathcal{G}$ be a decidable class of graphs. Assuming
$\textup{FPT}\neq\textup{W[1]}$, the following are equivalent:

  1. (1)

$\mathcal{G}$ has bounded treewidth,

  2. (2)

$\textsc{CSP}(\mathcal{G})$ is polynomial-time solvable,

  3. (3)

$\textsc{CSP}(\mathcal{G})$ is FPT parameterized by the number $k$ of
variables.

Observe that there is a major coincidence here: the polynomial-time solvable
cases are exactly the same as the FPT cases (which in principle could have
been a more general class). This coincidence makes it possible to use
W[1]-hardness to identify those cases that are not polynomial-time solvable.

A more general result gives a classification in the framework of homomorphism
problem for relational structures (which can be directly translated to results
for Boolean Join Query). Let $\tau$ be a vocabulary and let $\mathcal{A}$ be a
class of $\tau$-structures. Then $\textsc{HOM}(\mathcal{A},\\_)$ is the
special case of the general homomorphism problem where given two
$\tau$-structures $(\mathbf{A},\mathbf{B})$ with $\mathbf{A}\in\mathcal{A}$
and $\mathbf{B}$ arbitrary, the task is to decide if there is a homomorphism
from $\mathbf{A}$ to $\mathbf{B}$. The polynomial-time solvable cases again
depend on treewidth, but in a slightly more complicated manner. If
$\mathbf{A}^{\prime}$ is a substructure of $\mathbf{A}$ such that there is a
homomorphism from $\mathbf{A}$ to $\mathbf{A^{\prime}}$, then the problem
instances $(\mathbf{A},\mathbf{B})$ and $(\mathbf{A}^{\prime},\mathbf{B})$ are
equivalent. The smallest such substructure $\mathbf{A}^{\prime}$ of
$\mathbf{A}$ is called the core of $\mathbf{A}$ (it is known to be unique up
to isomorphism). It is the treewidth of this core that determines the
complexity of the problem.

###### Theorem 5.3 (Grohe (Grohe, 2007)).

Let $\tau$ be a finite vocabulary and let $\mathcal{A}$ be a decidable class
of $\tau$-structures. Assuming $\textup{FPT}\neq\textup{W[1]}$, the following
are equivalent:

  1. (1)

the cores of the structures in $\mathbf{A}$ have bounded treewidth,

  2. (2)

$\textsc{HOM}(\mathcal{A},\\_)$ is polynomial-time solvable,

  3. (3)

$\textsc{HOM}(\mathcal{A},\\_)$ is FPT parameterized by the size $k$ of the
universe of $\mathbf{A}$.

Again, we have that the polynomial-time solvable and FPT cases coincide,
allowing the use of W[1]-hardness for the classification of both properties.

##  6\. The Exponential-Time Hypothesis

Parameterized complexity gives a finer understanding of the complexity of
problems: for example, the negative results not only tell us that Clique is
not polynomial-time solvable, but they rule out algorithms with running time
$f(k)n^{O(1)}$. However, this is still a qualitative result that rules out a
certain running time, but does not tell us the exact complexity of the
problem: can the $n^{k}$ brute force search be improved to, say,
$n^{\sqrt{k}}$, or to $n^{O(\log k)}$, or to $n^{O(\log\log\log\log k)}$, or
to $\ldots$? For all we know, such algorithms cannot be ruled out based on the
$\textup{P}\neq\textup{NP}$ or $\textup{FPT}\neq\textup{W[1]}$ conjectures.
Similarly, for FPT problems such as Vertex Cover where the best known
algorithms have running time of the form $2^{O(k)}\cdot n^{O(1)}$, we cannot
rule out that these algorithms can be significantly improved to, say,
$2^{O(\sqrt{k})}\cdot n^{O(1)}$.

The Exponential-Time Hypothesis (ETH), formulated by Impagliazzo, Paturi, and
Zane (Impagliazzo and Paturi, 2001; Impagliazzo et al., 2001), makes the
assumption $\textup{P}\neq\textup{NP}$ more quantitative: informally, it not
only tells us that NP-hard problems do not have polynomial-time algorithms,
but it postulates that NP-hard problems really require exponential time and
cannot be solved in subexponential time. The formal statement of the ETH is
somewhat technical and for most applications it is more convenient to use the
following assumption instead, which is an easy consequence of the ETH:

###### Hypothesis 1 (Consequence of the ETH, Impagliazzo, Paturi, and Zane
(Impagliazzo and Paturi, 2001; Impagliazzo et al., 2001)).

3SAT with $n$ variables cannot be solved in time $2^{o(n)}$.

3SAT is the fundamental satisfiability problem where, given a Boolean formula
in conjunctive normal form with at most 3 literals in each clause (e.g.,
$(x_{1}\vee\bar{x}_{3}\vee x_{5})\wedge(\bar{x}_{1}\vee x_{2}\vee
x_{3})\wedge(\bar{x}_{2}\vee x_{3}\vee x_{4})$), the task is to decide whether
a satisfying assignment exists. For completeness, let us recall the formal
statement of the ETH, of which Hypothesis 1 is an easy consequence. Let
$s_{k}$ be the infinum of all real numbers $\delta$ for which there exists an
$O(2^{\delta n})$ time algorithm for $k$-SAT. Then the ETH is the assumption
that $s_{k}>0$ for every $k\geq 3$. It is easy to show that this assumption
implies Hypothesis 1, hence if we can show that some statement would refute
Hypothesis 1, then it would refute the ETH as well.

As 3SAT can interpreted as a special case of CSP with domain size 2 and
constraints of arity 3, we can translate Hypothesis 1 into the language of
CSPs to obtain a lower bound for solving instances with constant domain size.

###### Corollary 6.1.

Assuming the ETH, there is no algorithm that solves every CSP instance
$I=(V,D,C)$ in time $2^{o(|V|)}\cdot n^{O(1)}$, even if $|D|=2$ and every
constraint has arity at most 3.

Hypothesis 1 rules out the existence of algorithms that are subexponential in
the number $n$ of variables. But the number $m$ of clauses in a 3SAT instance
can be up to cubic in the number of variables, thus the length of the instance
can be much larger than $O(n)$. Therefore, Hypothesis 1 does not rule out the
existence of algorithms that are subexponential in the length of the instance:
it could be potentially the case that all the really hard instances of 3SAT
have, say, $\Omega(n^{2})$ clauses, hence a $2^{o(\sqrt{n+m})}$ algorithm
would be still compatible with Hypothesis 1. Impagliazzo, Paturi and Zane
(Impagliazzo et al., 2001) showed that this is not the case: the
Sparsification Lemma implies that, for the purposes of Hypothesis 1, 3SAT
remains hard already when restricted to instances with a linear number of
clauses. With the Sparsification Lemma, the following stronger assumption
follows from Hypothesis 1:

###### Hypothesis 2 (Consequence of the ETH + Sparsification Lemma,
Impagliazzo, Paturi, and Zane (Impagliazzo et al., 2001)).

3SAT with $n$ variables and $m$ clauses cannot be solved in time $2^{o(n+m)}$.

This stronger assumption turns out to be very useful to prove lower bounds for
other problems. Reductions from 3SAT to other problems typically create
instances whose size depends not only on the number $n$ of variables, but also
on the number $m$ of clauses, hence it is important to have lower bounds on
3SAT in terms of both $n$ and $m$. For example, if we look at textbook
reductions from 3SAT to 3-Coloring, then they transform a formula with $n$
variables and $m$ clauses into a graph with $O(n+m)$ vertices and $O(n+m)$
edges. Such a reduction together with Hypothesis 2 implies a lower bound for
binary CSP over a constant domain size.

###### Corollary 6.2.

Assuming the ETH, there is no algorithm that solves every CSP instance
$I=(V,D,C)$ in time $2^{o(|V|+|C|)}\cdot n^{O(1)}$, even if $|D|=3$ and every
constraint is binary.

Let us turn our attention now to parameterized problems. A key result in
parameterized complexity states that, assuming ETH, the $n^{k}$ brute force
search for Clique cannot be improved better than a constant factor in the
exponent, even if we allow an arbitrary $f(k)$ factor in the running time.

###### Theorem 6.3 (Chen et al. (Chen et al., 2004)).

Assuming ETH, Clique cannot be solved in time $f(k)\cdot n^{o(k)}$ for any
computable function $f$.

The same is true for the Partitioned Clique, which, as we have seen in Section
2.3, is essentially equivalent to a binary CSP instance where the primal graph
is clique. Therefore, we can translate Theorem 6.3 into the language of CSPs.

###### Theorem 6.4.

Assuming ETH, there is no algorithm that solves every binary CSP instance
$I=(V,D,C)$ in time $f(|V|)\cdot|D|^{o(|V|)|}\cdot n^{O(1)}$, where $f$ is an
arbitrary computable function.

Moreover, we have seen in Section 5 that $k$-Clique can be reduced to a
Special CSP instance with $k+2^{k}$ variables. Together with Theorem 6.3 it
follows that, assuming the ETH, there is no $f(|V|)n^{o(\log|V|)}$ time
algorithm for Special CSP. This makes the NP-intermediate status of the
problem very precise: it is indeed $n^{O(\log|V|)}$ the best possible running
time we can hope for this problem.

Note that the treewidth of a $k$-clique is $k-1$. Therefore, Theorem 6.4 shows
that if $k$ is the treewidth of the primal graph of the CSP instance, then the
$n^{O(k)}$ time algorithm of Freuder (Freuder, 1990) is essentially optimal in
the sense that the exponent cannot be improved by more than a constant factor.

###### Theorem 6.5.

Assuming ETH, there is no algorithm that solves every binary CSP instance
$I=(V,D,C)$ in time $f(|V|)\cdot n^{o(k)}$, where $k$ is the treewidth of the
primal graph and $f$ is an arbitrary computable function $f$.

One could interpret Theorem 6.5 as saying that the treewidth-based algorithm
of Freuder is an optimal way of solving CSP instances. However, this
interpretation is misleading. What Theorem 6.5 really says is that there is
one type of primal graphs, namely cliques, where the $n^{O(k)}$ running time
that follows using that treewidth-based algorithm is essentially optimal. This
does not rule out the possibility that there are some graph classes, maybe
planar graphs, bounded-degree graphs, interval graphs, etc. where it is
possible to solve the problem $n^{o(k)}$ time, where $k$ is the treewidth of
the primal graph. Formally, we can approach this possibility in the spirit of
Theorem 5.2, by considering the problem $\textsc{CSP}(\mathcal{G})$, where the
primal graph is restricted some class $\mathcal{G}$. The following lower bound
shows that the treewidth-based algorithm is still optimal for any such
$\textsc{CSP}(\mathcal{G})$, up to a logarithmic factor in the exponent.

###### Theorem 6.6 ((Marx, 2010)).

Let $\mathcal{G}$ be a class of graphs with unbounded treewidth. Assuming ETH,
there is no algorithm that solves every instance $I=(V,D,C)$ of
$\textsc{CSP}(\mathcal{G})$ in time $f(|V|)n^{o(k/\log k)}$, where $k$ is the
treewidth of the primal graph and $f$ is an arbitrary computable function.

The formulation of Theorem 6.6 was originally chosen in a way to be analogous
to the formulation of Theorem 5.2. However, it later turned out that it is
possible to state it in a slightly more robust and expressive way that shows
the precise complexity of individual primal graphs.

###### Theorem 6.7 ((Cohen-Addad et al., [n.d.])).

Assuming the ETH, there exists a universal constant $\alpha>0$ such that for
any fixed primal graph $G$ with treewidth $k\geq 2$, there is no algorithm
deciding the binary CSP instances $I=(V,D,C)$ whose primal graph is $G$ in
time $O(|D|^{\alpha\cdot k/\log k})$.

##  7\. The Strong Exponential-Time Hypothesis

Despite the usefulness of the ETH, there are complexity lower bounds that seem
to be beyond the reach of what can be proved as a consequence of this
hypothesis. Impagliazzo, Paturi, and Zane (Impagliazzo et al., 2001) proposed
an even stronger assumption on the complexity of NP-hard problems: the so-
called Strong Exponential-Time Hypothesis (SETH). Using the notation
introduced at the beginning of Section 6, the SETH assumes that
$\lim_{k\to\infty}s_{k}=1$. The following consequence of the SETH is a
convenient formulation that can be used as a starting point for lower bounds
on other problems:

###### Hypothesis 3 (Consequence of the SETH, Impagliazzo, Paturi, and Zane
(Impagliazzo et al., 2001)).

SAT with $n$ variables and $m$ clauses cannot be solved in time
$(2-\epsilon)^{n}\cdot m^{O(1)}$ for any $\epsilon>0$.

Intuitively, Hypothesis 3 states that there is no better algorithm for SAT
than the brute force search of trying each of the $2^{n}$ possible
assignments. Note that here SAT is the satisfiability problem with unbounded
clause length. For fixed clause length, algorithms better than $2^{n}$ are
known: for example, the best known algorithms for 3SAT and 4SAT have running
times $1.308^{n}$ and $1.469^{n}$, respectively (Hertli, 2014). The SETH
states that the base of the exponent has to get closer and closer to 1 as the
clause length increases, and it is not possible to have an algorithm with base
$2-\epsilon$ that works for arbitrary large clause length.

It is important to note that there is no known analogue of the Sparsification
Lemma for the SETH. That is, we cannot assume that the hard instances
stipulated by Hypothesis 3 have only a linear number of clauses: for all we
know, the number of clauses can be exponential in the number $n$ of variables.
This severely limits the applicability of lower bounds based on the SETH as
any reduction from the SAT instance would create instances whose sizes are
potentially exponentially large in $n$. Nevertheless, the SETH has found
applications in parameterized complexity, for example, giving tight lower
bounds on how the running time has to depend on treewidth (Lokshtanov et al.,
2018; Borradaile and Le, 2016; Curticapean and Marx, 2016; Cygan et al., 2016,
2011; Iwata and Yoshida, 2015; Egri et al., 2018; Jaffke and Jansen, 2017).

An important parameterized problem for which the SETH gives a very tight lower
bound is Dominating Set. The closed neighborhood $N[v]=N(v)\cup\\{v\\}$ of a
vertex $v$ consists of the vertex itself and its neighbors. A dominating set
$S$ is a set of vertices that contains a vertex from the closed neighborhood
of every vertex, in other words, every vertex is either selected or has a
selected neighbor. In the Dominating Set problem, given a graph $G$ and an
integer $k$, the task is to find a dominating set $S$ of size at most $k$. If
$G$ is an $n$-vertex graph, then the trivial brute force algorithm enumerates
the $O(n^{k})$ subsets of size at most $k$ and needs $O(n^{2})$ time for each
of them to check if they form a solution. This results in a $O(n^{k+2})$ time
algorithm, which can be improved to $n^{k+o(1)}$ (Eisenbrand and Grandoni,
2004). The following lower bound shows that any small constant improvement
beyond $k$ in the exponent would violate the SETH.

###### Theorem 7.1 (Patrascu and Williams (Patrascu and Williams, 2010)).

If there is an integer $k\geq 3$ and a real number $\epsilon>0$ such that
$k$-Dominating Set can be solved in time $O(n^{k-\epsilon})$ on $n$-vertex
graphs, then the SETH is false.

As a demonstration, we show how Theorem 7.1 allows us to make Theorem 6.5
tighter. We are not just ruling out $|D|^{o(k)}$ time, but any potential
improvement in the exponent of the domain size beyond $k$, getting closer to
the upper bound of Theorem 4.2.

###### Theorem 7.2.

If there are integers $k\geq 3$, $c\geq 1$, and a real number $\epsilon>0$
such that there is an algorithm solving CSP instances $I=(V,D,C)$ whose primal
graph has treewidth at most $k$ in time $O(|V|^{c}\cdot|D|^{k-\epsilon})$,
then the SETH is false.

###### Proof.

Let $g\geq 1$ be the smallest integer such that $g\epsilon>c+\epsilon$ and let
$t=gk$. First we present a generic reduction from $t$-Dominating Set on an
$n$-vertex graph to a CSP instance with domain size $n$ where the treewidth of
the primal graph is $t$. Let $G$ be an $n$-vertex graph where we need to find
a solution $S$ of size at most $t$. For simplicity of notation, let us assume
that $V(G)=[n]$. We construct a CSP instance $I=(V,D,C)$ the following way.
The set $V$ contains $t+n$ variables $s_{1}$, $\dots$, $s_{t}$, $x_{1}$,
$\dots$, $x_{n}$. The domain $D$ is $V(G)=[n]$. The intended meaning of the
value of $s_{i}$ is the $i$-th vertex of the solution, and the intended
meaning of $x_{j}=i$ is that the solution vertex represented by $s_{i}$ is in
$N[j]$. To enforce this interpretation, for every $i\in[t]$ and $j\in[n]$, we
introduce a constraint $c_{i,j}=\langle(s_{i},v_{j}),R_{i,j}\rangle$, where

$\displaystyle R_{i,j}=$ $\displaystyle\left\\{(a,b)\mid a\in[n],b\in[t],b\neq
i\right\\}\bigcup$ $\displaystyle\left\\{(a,b)\mid a\in[n],b\in[t],b=i,a\in
N[j]\right\\}$

It is not difficult to check that if there is a solution to this CSP instance,
then $\\{s_{1},\dots,s_{t}\\}$ is a dominating set (as vertex $s_{x_{j}}$ is
in the closed neighborhood $N[j]$ of $j$). Conversely, a solution $S$ of
$t$-Dominating Set can be turned into a solution of this CSP instance. Observe
that the primal graph is complete bipartite graph with $t$ vertices on one
side and $n$ vertices on the other side. Such a graph has treewidth at most
$t$.

To obtain the required form of the lower bound, we need to modify the
constructed CSP instance. Let us group the variables $x_{1}$, $\dots$, $x_{t}$
into $t/g=k$ groups of size $g$ each. If we increase the domain from $D$ to
$D^{g}$ (having size $n^{g}$), we can represent each group with a single new
variable (and modify the constraints accordingly). This way, we can obtain an
equivalent CSP instance $I^{\prime}=(V^{\prime},D^{\prime},C^{\prime})$ where
$|D^{\prime}|=n^{g}$ and treewidth of the primal graph is at most $k$. By our
assumption, this CSP instance $I^{\prime}$ (and hence the original
$t$-Dominating Set instance) can be solved in time

$\displaystyle O(|V^{\prime}|^{c}\cdot|D^{\prime}|^{k-\epsilon})$
$\displaystyle=O(n^{c}\cdot n^{g(t/g-\epsilon)})$
$\displaystyle=O(n^{t+c-g\epsilon})=O(n^{t-\epsilon}).$

The size of the constructed instance $I^{\prime}$ can be generously bounded by
$O(n^{2g+1})$ which is less than $O(n^{t-\epsilon})$. The reduction presented
above can be done in time linear in the size of $I^{\prime}$, hence the
running time of the reduction itself is dominated by the running time of
solving $I^{\prime}$ with the assumed algorithm. Therefore, we obtain an
algorithm for solving $t$-Dominating Set in time $O(n^{t-\epsilon})$. By
Theorem 7.1, this violates SETH. ∎

In recent years, the SETH has been successfully used to give lower bounds for
polynomial-time solvable problems, for example, by showing that the textbook
$O(n^{2})$ dynamic programming algorithm for Edit Distance cannot be
significantly improved: it cannot be solved in time $O(n^{2-\epsilon})$ for
any $\epsilon>0$, unless the SETH fails (Bringmann and Künnemann, 2015;
Backurs and Indyk, 2018). Many other tight results of this form can be found
in the recent literature under the name “fine-grained complexity” (Bringmann
et al., 2018; Bringmann and Künnemann, 2018; Abboud et al., 2018b; Bringmann
and Künnemann, 2015; Bringmann, 2014; Backurs and Indyk, 2018; Abboud et al.,
2015, 2018c; Williams, 2015; Patrascu and Williams, 2010; Roditty and
Williams, 2013).

##  8\. Other conjectures

We finish the overview of lower bound techniques with a few other complexity
conjectures that have appeared recently in the literature. This section does
not contain any strong results or nontrivial reductions; the goal is to
present assumptions that have direct consequences when translated into the
language of database theory and CSP. The aim is to raise awareness of the
existence of these conjectures, which may be the starting point of future
research.

The $k$-clique conjecture. Matrix multiplication techniques can be used to
detect if a graph contains a triangle: if $A$ is the adjacency matrix of $G$,
then $G$ contains a triangle if and only if $A^{3}$ has a nonzero value on the
diagonal. Therefore, if we have an algorithm for multiplying two $n\times n$
matrices in time $O(n^{\omega})$ for some $\omega$ (the current best known
algorithm has $\omega<2.3729$ (Alman and Williams, 2021)), then we can detect
in time $O(n^{3})$ if an $n$-vertex graph contains a triangle. Nesetril and
Poljak (Nešetřil and Poljak, 1985) showed in 1985 that this can be generalized
further for detecting a clique of size $k$ in time $O(n^{\omega k/3})$ (if $k$
is divisible by $3$). As no significant improvement over this approach
appeared in the past 35 years, one can conjecture that there is no
$O(n^{(\omega-\epsilon)k/3+c})$ time algorithm for $k$-Clique for any
$\epsilon,c>0$. Abboud, Backurs, and Vassilevska Williams (Abboud et al.,
2018a) used this conjecture to give evidence that Valiant’s $O(n^{\omega})$
time parsing algorithm (Valiant, 1975) from 1975 is optimal.

As discussed in Section 2.3, $k$-Clique on an $n$-vertex graph can be
represented as a CSP with $k$ variables, $\binom{k}{2}$ constraints, and
domain size $n$. Therefore, the $k$-clique conjecture further refines Theorem
6.4 by ruling out not only a $|D|^{o(|V|)}$ dependence in the running time,
but also $|D|^{(\omega-\epsilon)|V|/3+c}$ for any $\epsilon,c>0$.

The $d$-uniform hyperclique conjecture. A hypergraph is $d$-uniform if every
hyperedge contains exactly $d$ vertices. The analog of a $k$-clique in a
$d$-uniform hypergraph is a set $S$ of $k$ vertices such that each of the
$\binom{k}{d}$ possible hyperedges are present in $S$. Somewhat surprisingly,
matrix multiplication techniques seem to speed up the search for $k$-cliques
only for $d=2$ (ordinary graphs). For any fixed $d\geq 3$, nothing
substantially better is known than trying every set of size $k$. This suggests
the conjecture that there is no $O(n^{(1-\epsilon)k+c})$ time algorithm for
detecting $k$-cliques in $d$-uniform hypergraphs for any fixed $d\geq 2$ and
$\epsilon,c>0$ (Lincoln et al., 2018). We can again translate this conjecture
into the language of CSPs: we can show that even if the arity of every
constraint is at most 3, there is no $f(|V|)\cdot|D|^{(1-\epsilon)|V|+c}\cdot
n^{O(1)}$ algorithm for CSP for any $\epsilon,c>0$ and computable function
$f$. Therefore, we get very tight lower bounds showing that essentially the
brute force search of all assignments cannot be avoided. The $d$-uniform
hyperclique conjecture was used to rule out the possibility of constant-delay
enumeration algorithms (Bagan et al., 2007; Brault-Baron, 2013).

The triangle conjecture. In database query problems it is more relevant to
express the running time in terms of the size of the database relations rather
than the size of the domain. For example, given the query
$Q=R_{1}(a_{1},a_{2})\bowtie R_{2}(a_{1},a_{3})\bowtie R_{3}(a_{2},a_{3})$
whose primal graph is the triangle, matrix multiplication can be used to check
in time $O(d^{\omega})$ if the answer is empty, where $d$ is the size of the
domain of the attributes. But what can we say about the running time expressed
as a function $N$ of the maximum size of the relations? As we have seen in
Section 3, the size of the solution is $O(N^{3/2})$, we can enumerate it in
time $O(N^{3/2})$, and this is tight. However, this does not rule out the
possibility that there are faster algorithms for deciding if the answer is
empty. In particular, can this be solved in linear time? Note that this
question is equivalent to asking for the best possible running time for
detecting triangles, where the running time is now expressed as a function of
the number $m$ of edges. The best known algorithm of this form detects the
existence of a triangle in time $O(m^{2\omega/(w+1)})$ (Alon et al., 1997) and
one can state as a conjecture (Strong Triangle Conjecture (Abboud and
Williams, 2014)) that this is indeed best possible.

##  9\. Conclusions

We have seen a sequence of complexity lower bounds of various strengths. The
results were based on assumptions with different levels of plausibility, going
all the way from unconditional bounds, classic NP-completeness, to novel
conjectures. The results also differ in the tightness of the lower bound: they
can be only qualitative results (polynomial-time vs. NP-hard, FPT vs.
W[1]-hard) or quantitative lower bounds showing the optimality of current
algorithms to various levels of tightness.

What can we learn from all these results? First, when aiming for a lower
bound, we need to select a precise form of the bound. Ideally, we would like
to have negative results that rule out the possibility of any improved
algorithm compared to what is known currently, showing that they are already
optimal. The meaning of “any improved algorithm” needs to be clarified
precisely and the choice of this meaning can greatly influence the technical
difficulty of the lower bound proof and the required assumptions. Second, we
need to choose a suitable complexity assumption that we can base the result
on. There are established conjectures, such as the ETH, that are widely used
in different domains. But we should be ready to connect our database theory or
CSP problem at hand with other, less celebrated open question as well. The
general theme of conditional lower bounds is to transform a relatively
specialized question to a more fundamental question that was studied from
multiple directions. If we can formally establish that the main challenge in
understanding our problem is really some other, more fundamental problem in
disguise, then this means that spending further efforts on finding improved
algorithms is not timely and we can assume for the time being that any
algorithm matching the lower bound is optimal. This is a common situation in
complexity theory: as it is often said, computational complexity progresses by
reducing the number of questions, without increasing the number of answers.

###### Acknowledgements.

Research supported by the European Research Council (ERC) consolidator grant
No. 725978 SYSTEMATICGRAPH.

## References

  * (1)
  * Abboud et al. (2015) Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015\.  Tight Hardness Results for LCS and Other Sequence Similarity Measures. In _Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)_. 59–78.
  * Abboud et al. (2018a) Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2018a.  If the Current Clique Algorithms Are Optimal, so Is Valiant’s Parser.  _SIAM J. Comput._ 47, 6 (2018), 2527–2555.  https://doi.org/10.1137/16M1061771
  * Abboud et al. (2018b) Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. 2018b.  More consequences of falsifying SETH and the orthogonal vectors conjecture. In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA, June 25-29, 2018_ , Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.). ACM, 253–266.  https://doi.org/10.1145/3188745.3188938
  * Abboud and Williams (2014) Amir Abboud and Virginia Vassilevska Williams. 2014\.  Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In _55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014_. IEEE Computer Society, 434–443.  https://doi.org/10.1109/FOCS.2014.53
  * Abboud et al. (2018c) Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. 2018c.  Matching Triangles and Basing Hardness on an Extremely Popular Conjecture.  _SIAM J. Comput._ 47, 3 (2018), 1098–1122.  https://doi.org/10.1137/15M1050987
  * Alman and Williams (2021) Josh Alman and Virginia Vassilevska Williams. 2021\.  A Refined Laser Method and Faster Matrix Multiplication. In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021_ , Dániel Marx (Ed.). SIAM, 522–539.  https://doi.org/10.1137/1.9781611976465.32
  * Alon et al. (1997) Noga Alon, Raphael Yuster, and Uri Zwick. 1997.  Finding and Counting Given Length Cycles.  _Algorithmica_ 17, 3 (1997), 209–223.  https://doi.org/10.1007/BF02523189
  * Arora and Barak (2009) Sanjeev Arora and Boaz Barak. 2009.  _Computational Complexity - A Modern Approach_.  Cambridge University Press.  http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264
  * Atserias et al. (2013) Albert Atserias, Martin Grohe, and Dániel Marx. 2013\.  Size Bounds and Query Plans for Relational Joins.  _SIAM J. Comput._ 42, 4 (2013), 1737–1767.  https://doi.org/10.1137/110859440
  * Babai (2016) László Babai. 2016\.  Graph isomorphism in quasipolynomial time [extended abstract]. In _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , Daniel Wichs and Yishay Mansour (Eds.). ACM, 684–697.  https://doi.org/10.1145/2897518.2897542
  * Babai and Luks (1983) László Babai and Eugene M. Luks. 1983.  Canonical Labeling of Graphs. In _Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA_ , David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas (Eds.). ACM, 171–183.  https://doi.org/10.1145/800061.808746
  * Backurs and Indyk (2018) Arturs Backurs and Piotr Indyk. 2018.  Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False).  _SIAM J. Comput._ 47, 3 (2018), 1087–1097.  https://doi.org/10.1137/15M1053128
  * Bagan et al. (2007) Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007\.  On Acyclic Conjunctive Queries and Constant Delay Enumeration. In _Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings_ _(Lecture Notes in Computer Science)_ , Jacques Duparc and Thomas A. Henzinger (Eds.), Vol. 4646. Springer, 208–222.  https://doi.org/10.1007/978-3-540-74915-8_18
  * Bertelè and Brioschi (1973) Umberto Bertelè and Francesco Brioschi. 1973.  On Non-serial Dynamic Programming.  _J. Comb. Theory, Ser. A_ 14, 2 (1973), 137–148.  https://doi.org/10.1016/0097-3165(73)90016-2
  * Borradaile and Le (2016) Glencora Borradaile and Hung Le. 2016.  Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In _11th International Symposium on Parameterized and Exact Computation (IPEC 2016)_ _(LIPIcs)_ , Jiong Guo and Danny Hermelin (Eds.), Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 8:1–8:23.  https://doi.org/10.4230/LIPIcs.IPEC.2016.8
  * Brault-Baron (2013) Johann Brault-Baron. 2013\.  _De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order)_.  Ph.D. Dissertation. University of Caen Normandy, France.  https://tel.archives-ouvertes.fr/tel-01081392
  * Bringmann (2014) Karl Bringmann. 2014\.  Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In _55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, USA, October 18-21, 2014_. IEEE Computer Society, 661–670.  https://doi.org/10.1109/FOCS.2014.76
  * Bringmann et al. (2018) Karl Bringmann, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. 2018.  Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)_ , Artur Czumaj (Ed.). SIAM, 1190–1206.  https://doi.org/10.1137/1.9781611975031.77
  * Bringmann and Künnemann (2015) Karl Bringmann and Marvin Künnemann. 2015.  Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In _IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), Berkeley, CA, USA, 17-20 October, 2015_ , Venkatesan Guruswami (Ed.). IEEE Computer Society, 79–97.  https://doi.org/10.1109/FOCS.2015.15
  * Bringmann and Künnemann (2018) Karl Bringmann and Marvin Künnemann. 2018.  Multivariate Fine-Grained Complexity of Longest Common Subsequence. In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)_ , Artur Czumaj (Ed.). SIAM, 1216–1235.  https://doi.org/10.1137/1.9781611975031.79
  * Bulatov (2017) Andrei A. Bulatov. 2017\.  A Dichotomy Theorem for Nonuniform CSPs. In _58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, USA, October 15-17, 2017_ , Chris Umans (Ed.). IEEE Computer Society, 319–330.  https://doi.org/10.1109/FOCS.2017.37
  * Chen et al. (2004) Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. 2004\.  Linear FPT reductions and computational lower bounds. In _Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004)_. ACM, New York, 212–221.
  * Chen et al. (2001) Jianer Chen, Iyad A. Kanj, and Weijia Jia. 2001.  Vertex cover: further observations and further improvements.  _J. Algorithms_ 41, 2 (2001), 280–301.
  * Chung et al. (1986) F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. 1986\.  Some intersection theorems for ordered sets and graphs.  _J. Combin. Theory Ser. A_ 43, 1 (1986), 23–37.
  * Cohen-Addad et al. ([n.d.]) Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. [n.d.].  Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.  To appear in Journal of the ACM.
  * Cook (1971) Stephen A. Cook. 1971\.  The Complexity of Theorem-Proving Procedures. In _Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA_ , Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman (Eds.). ACM, 151–158.  https://doi.org/10.1145/800157.805047
  * Curticapean and Marx (2016) Radu Curticapean and Dániel Marx. 2016.  Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In _Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)_. 1650–1669.
  * Cygan et al. (2016) Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. 2016.  On Problems as Hard as CNF-SAT.  _ACM Trans. Algorithms_ 12, 3 (2016), 41:1–41:24.
  * Cygan et al. (2015) Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015.  _Parameterized Algorithms_.  Springer.
  * Cygan et al. (2011) Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011.  Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. In _Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011)_. 150–159.
  * Downey and Fellows (1999) Rodney G. Downey and Michael R. Fellows. 1999.  _Parameterized Complexity_.  Springer, New York. xvi+533 pages.
  * Downey and Fellows (2013) Rodney G. Downey and Michael R. Fellows. 2013.  _Fundamentals of Parameterized Complexity_.  Springer.  https://doi.org/10.1007/978-1-4471-5559-1
  * Egri et al. (2018) László Egri, Dániel Marx, and Paweł Rzażewski. 2018.  Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization. In _35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)_. 27:1–27:15.  https://doi.org/10.4230/LIPIcs.STACS.2018.27
  * Eisenbrand and Grandoni (2004) Friedrich Eisenbrand and Fabrizio Grandoni. 2004.  On the complexity of fixed parameter clique and dominating set.  _Theor. Comput. Sci._ 326, 1-3 (2004), 57–67.  https://doi.org/10.1016/j.tcs.2004.05.009
  * Feder and Vardi (1999) Tomás Feder and Moshe Y. Vardi. 1999.  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.  _SIAM J. Comput._ 28, 1 (1999), 57–104.
  * Flum and Grohe (2006) Jörg Flum and Martin Grohe. 2006.  _Parameterized Complexity Theory_.  Springer, Berlin. xiv+493 pages.
  * Freuder (1990) E. C. Freuder. 1990\.  Complexity of K-Tree Structured Constraint Satisfaction Problems. In _Proc. of AAAI-90_. Boston, MA, 4–9.
  * Garey and Johnson (1979) M. R. Garey and David S. Johnson. 1979.  _Computers and Intractability: A Guide to the Theory of NP-Completeness_.  W. H. Freeman.
  * Grohe (2007) Martin Grohe. 2007\.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  _J. ACM_ 54, 1 (2007), 1.  https://doi.org/10.1145/1206035.1206036
  * Grohe et al. (2001) Martin Grohe, Thomas Schwentick, and Luc Segoufin. 2001\.  When is the evaluation of conjunctive queries tractable?. In _Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC 2001)_ (Hersonissos, Greece). ACM Press, New York, NY, USA, 657–666.  https://doi.org/10.1145/380752.380867
  * Halin (1976) Rudolf Halin. 1976\.  S-functions for graphs.  _Journal of Geometry_ 8, 1-2 (1976), 171–186.
  * Hertli (2014) Timon Hertli. 2014\.  3-SAT Faster and Simpler — Unique-SAT Bounds for PPSZ Hold in General.  _SIAM J. Comput._ 43, 2 (2014), 718–729.  https://doi.org/10.1137/120868177
  * Impagliazzo and Paturi (2001) Russell Impagliazzo and Ramamohan Paturi. 2001.  On the Complexity of $k$-SAT.  _J. Comput. Syst. Sci._ 62, 2 (2001), 367–375.
  * Impagliazzo et al. (2001) Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001\.  Which problems have strongly exponential complexity?  _J. Comput. System Sci._ 63, 4 (2001), 512–530.
  * Iwata and Yoshida (2015) Yoichi Iwata and Yuichi Yoshida. 2015.  On the Equivalence among Problems of Bounded Width. In _23rd Annual European Symposium (ESA 2015)_ _(Lecture Notes in Computer Science)_ , Nikhil Bansal and Irene Finocchi (Eds.), Vol. 9294. Springer, 754–765.  https://doi.org/10.1007/978-3-662-48350-3_63
  * Jaffke and Jansen (2017) Lars Jaffke and Bart M. P. Jansen. 2017.  Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems. In _Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017)_ _(Lecture Notes in Computer Science)_ , Vol. 10236. 345–356.
  * Karp (1972) Richard M. Karp. 1972\.  Reducibility Among Combinatorial Problems. In _Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA_ _(The IBM Research Symposia Series)_ , Raymond E. Miller and James W. Thatcher (Eds.). Plenum Press, New York, 85–103.  https://doi.org/10.1007/978-1-4684-2001-2_9
  * Ladner (1975) Richard E. Ladner. 1975\.  On the Structure of Polynomial Time Reducibility.  _J. ACM_ 22, 1 (1975), 155–171.  https://doi.org/10.1145/321864.321877
  * Lenstra and Pomerance (1992) H. W. Lenstra, Jr. and Carl Pomerance. 1992.  A rigorous time bound for factoring integers.  _J. Amer. Math. Soc._ 5, 3 (1992), 483–516.  https://doi.org/10.2307/2152702
  * Lincoln et al. (2018) Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. 2018.  Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018_ , Artur Czumaj (Ed.). SIAM, 1236–1252.  https://doi.org/10.1137/1.9781611975031.80
  * Lokshtanov et al. (2018) Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2018\.  Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal.  _ACM Trans. Algorithms_ 14, 2 (2018), 13:1–13:30.  https://doi.org/10.1145/3170442
  * Marx (2010) Dániel Marx. 2010\.  Can You Beat Treewidth?  _Theory of Computing_ 6, 1 (2010), 85–112.  https://doi.org/10.4086/toc.2010.v006a005 arXiv:toc:v006/a005
  * Nešetřil and Poljak (1985) Jaroslav Nešetřil and Svatopluk Poljak. 1985.  On the complexity of the subgraph problem.  _Commentationes Mathematicae Universitatis Carolinae_ 26, 2 (1985), 415–419.
  * Ngo et al. (2018) Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2018\.  Worst-case Optimal Join Algorithms.  _J. ACM_ 65, 3 (2018), 16:1–16:40.  https://doi.org/10.1145/3180143
  * Papadimitriou (1994) C. H. Papadimitriou. 1994\.  _Computational Complexity_.  Addison Wesley.
  * Patrascu and Williams (2010) Mihai Patrascu and Ryan Williams. 2010.  On the Possibility of Faster SAT Algorithms. In _Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)_. 1065–1075.
  * Robertson and Seymour (1984) Neil Robertson and Paul D. Seymour. 1984.  Graph minors. III. Planar tree-width.  _J. Comb. Theory, Ser. B_ 36, 1 (1984), 49–64.  https://doi.org/10.1016/0095-8956(84)90013-3
  * Roditty and Williams (2013) Liam Roditty and Virginia Vassilevska Williams. 2013\.  Fast approximation algorithms for the diameter and radius of sparse graphs. In _Proceedings of the 45th Annual ACM on Symposium on Theory of Computing (STOC 2013)_. 515–524.
  * Schaefer (1978) Thomas J. Schaefer. 1978\.  The Complexity of Satisfiability Problems. In _Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA_ , Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho (Eds.). ACM, 216–226.  https://doi.org/10.1145/800133.804350
  * Valiant (1975) Leslie G. Valiant. 1975\.  General Context-Free Recognition in Less than Cubic Time.  _J. Comput. Syst. Sci._ 10, 2 (1975), 308–315.  https://doi.org/10.1016/S0022-0000(75)80046-8
  * Veldhuizen (2014) Todd L. Veldhuizen. 2014\.  Triejoin: A Simple, Worst-Case Optimal Join Algorithm. In _Proc. 17th International Conference on Database Theory ((ICDT) 2014)_. 96–106.  https://doi.org/10.5441/002/icdt.2014.13
  * Williams (2015) Virginia Vassilevska Williams. 2015\.  Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis. In _Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)_ _(LIPIcs)_ , Vol. 43. 17–29.
  * Zhuk (2017) Dmitriy Zhuk. 2017\.  A Proof of CSP Dichotomy Conjecture. In _58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, USA, October 15-17, 2017_. 331–342.  https://doi.org/10.1109/FOCS.2017.38


It is directly verified that $P(\mu_i) = f(\mu_i)$ for all $i=k,\dots,k+\ell$. If $f$ is a polynomial of degree at most $\ell$ (notation $f\in \mathcal{P}_{\ell}$), then the polynomial is exact, i.e., $f = p$. As both $P,f \in \mathcal{P}_{\ell}$, we have $P - f\in \mathcal{P}_{\ell}$. By the fundamental theorem of algebra, it now follows that $P - f = 0$, since this polynomial is of degree at most $\ell$ but has at least $\ell+1$ distinct roots, namely $\mu_k,\dots,\mu_{k+\ell}$. Now take $f(x) = 1$ for all $x$. As $f\in \mathcal{P}_{\ell}$,

\[
1 = P(0) = \sum_{j=k}^{k+\ell}L_j(0)f(0) = \sum_{j=k}^{k+\ell}\prod_{\substack{i=k\\ i\neq j}}^{k+\ell}\frac{\mu_i}{\mu_i - \mu_j},
\]

as desired.

§.§.§ Proof of Lemma <ref>

We give a formal proof of the claim, remarking that various other approaches can be followed. By conditioning on the value of ${\rm E}(k,\mu)$, it is directly verified that

\begin{align*}
\psi_{vt}[k,\ell]
&= \int_{t-v}^{t}\mathbb{P}({\rm E}(\ell-k,\mu) > t-x)\,\mathbb{P}({\rm E}(k,\mu) \in {\rm d}x)
= \sum_{i=0}^{\ell-k-1}e^{-\mu t}\frac{\mu^{i+k}}{i!(k-1)!}\int_{t-v}^{t}x^{k-1}(t-x)^i \mathrm{d}x\\
&= \sum_{j=k}^{\ell-1}e^{-\mu t}\frac{\mu^{j}}{(j-k)!(k-1)!}\int_{t-v}^{t}x^{k-1}(t-x)^{j-k} \mathrm{d}x\\
&=\sum_{j=k}^{\ell-1}\mathbb{P}({\rm Pois}(\mu t) = j)\,\frac{j!}{(j-k)!(k-1)!}\int_{1-v/t}^{1}u^{k-1}(1-u)^{j-k} \mathrm{d}u,
\end{align*}

where we used the substitution $j:=i+k$ in the third equality, and the substitution  $u := x/t$
in the last equality. Then recall the property  that

\[
\int_{x}^{1}u^{k-1}(1-u)^{i-1} \mathrm{d}u
= \text{B}(k,i) - \text{B}_{x}(k,i),
\]

where, for $x\in[0,1]$ and $k,i\in{\mathbb N}$,

\[
\text{B}_{x}(k,i) := \int_{0}^{x}t^{k-1}(1 - t)^{i-1}\mathrm{d}t\quad \text{and}
\quad
\text{B}(k,i) := \text{B}_{1}(k,i) = \frac{(k-1)!(i-1)!}{(k+i-1)!},\quad a,b\in \mathbb{N},
\]

are the incomplete beta function and the beta function, respectively. It is a well-known property  [9] of these functions that

\[
\text{B}_{x}(k,i) = \text{B}(k,i)I_{x}(k,i) = \text{B}(k,i)\left(1 - I_{1-x}(i,k)\right),
\]

where in particular it holds that, for any $x\in[0,1]$ and $k,i\in\mathbb{N}$,
I_x(k,i) = \mathbb{P}(\text{Bin}(k+i-1,x) \geqslant i).
Combining the above findings, after some standard algebra, we obtain the stated.

§.§.§ Proof of Lemma <ref>

By an elementary conditioning argument,

\begin{align*}\sigma_t[m,k] &= \int_0^t \int_0^s\mu_1e^{-\mu_1 u}\frac{(\mu_1 u)^{m-1}}{(m-1)!}  \left(1-\sum_{\ell=0}^{k-1} e^{-\mu_2(s-u)}\frac{(\mu_2(s-u))^\ell}{\ell!}\right) {\rm d}u\,{\rm d}s\\
\int_0^t \int_0^{t-u}\mu_1e^{-\mu_1 u}\frac{(\mu_1 u)^{m-1}}{(m-1)!}  \left(1-\sum_{\ell=0}^{k-1} e^{-\mu_2 s}\frac{(\mu_2 s)^\ell}{\ell!}\right) {\rm d}s\,{\rm d}u\\
&=  \int_0^t \mu_1e^{-\mu_1 u}\frac{(\mu_1 u)^{m-1}}{(m-1)!}  \left(t-u-\sum_{\ell=0}^{k-1}\int_0^{t-u} e^{-\mu_2 s}\frac{(\mu_2 s)^\ell}{\ell!}{\rm d}s\right) {\rm d}u\\
t\left(1-\sum_{i=0}^{m-1} e^{-\mu_1 t}\frac{(\mu_1t)^i}{i!}\right)-
\frac{m}{\mu_1}\left(1-\sum_{i=0}^{m} e^{-\mu_1 t}\frac{(\mu_1t)^i}{i!}\right)\:
\sum_{\ell=0}^{k-1} \int_0^t\mu_1e^{-\mu_1 u}\frac{(\mu_1 u)^{m-1}}{(m-1)!}  \int_0^{t-u}
e^{-\mu_2 s}\frac{(\mu_2 s)^\ell}{\ell!}{\rm d}s\, {\rm d}u

using that, for any $\mu>0$, $\ell\in\{0,1,\ldots\}$, and $t\geqslant 0$,

\begin{align*}\int_0^{t} e^{-\mu s}\frac{(\mu s)^\ell}{\ell!}{\rm d}s&=\frac{1}{\mu}{\mathbb P}\left(
{\rm E}(\ell+1,\mu)\leqslant t\right)=\frac{1}{\mu}\left(1-\sum_{i=0}^\ell e^{-\mu t}\frac{(\mu t)^i}{i!}\right).
\end{align*}

Using the same argument, it follows that $\sigma_t[m,k]$ equals

\begin{align*}\lefteqn{
\left(t-\frac{k}{\mu_2}\right)\left(1-\sum_{i=0}^{m-1} e^{-\mu_1 t}\frac{(\mu_1t)^i}{i!}\right)
- \frac{m}{\mu_1}\left(1-\sum_{i=0}^{m} e^{-\mu_1 t}\frac{(\mu_1t)^i}{i!}\right)
\:+}\\
\int_0^te^{-\mu_1 u}\frac{(\mu_1 u)^{m-1}}{(m-1)!}
e^{-\mu_2(t-u)}\frac{(\mu_2(t-u))^i}{i!}{\rm d}u\\&= \left(t-\frac{k}{\mu_2}\right)\left(1-\sum_{i=0}^{m-1} e^{-\mu_1 t}\frac{(\mu_1t)^i}{i!}\right)
- \frac{m}{\mu_1}\left(1-\sum_{i=0}^{m} e^{-\mu_1 t}\frac{(\mu_1t)^i}{i!}\right)+\frac{\mu_1}{\mu_2}\sum_{\ell=0}^{k-1}\sum_{i=0}^\ell
\rho_t[m-1,i].
\end{align*}

This proves the claim.

§.§.§ Proof of Lemma <ref>

Observe that, by distinguishing between $s\in[0,t-v)$ and $s\in[t-v,t]$,

\begin{align*}
\chi_{vt,1}[k,\ell] &=  \int_0^\infty{\mathbb P}(t-v -s\leqslant {\rm E}(k,\mu_1)\leqslant t-s,
{\rm E}(k,\mu_1)+ {\rm E}(1,\mu_1)>t-s) \,{\mathbb P}({\rm E}(\ell,\mu_2)\in {\rm d}s)\\
&=\int_0^{t-v} e^{-\mu_1(t-s)}\frac{(\mu_1(t-s))^k}{k!}{\mathbb P}\left({\rm Bin}\left(k, \frac{v}{t-s} \right)>0\right)
\,{\mathbb P}({\rm E}(\ell,\mu_2)\in {\rm d}s)\:+\\
&\:\:\:\:\:\:\:\:\int_{t-v}^t  e^{-\mu_1(t-s)}\frac{(\mu_1(t-s))^k}{k!} \,{\mathbb P}({\rm E}(\ell,\mu_2)\in {\rm d}s),
\end{align*}

where the first term in the last expression is due to Lemma <ref>.

\[{\mathbb P}\left({\rm Bin}\left(k, \frac{v}{t-s} \right)>0\right) = 1 - \left(\frac{t-s-v}{t-s}\right)^k,\]

we find that $ \chi_{vt,1}[k,\ell]$ equals

\begin{align*}
\mu_2\int_{0}^t  e^{-\mu_1(t-s)}\frac{(\mu_1(t-s))^k}{k!} &\,e^{-\mu_2 s}\frac{(\mu_2 s)^{\ell-1}}{(\ell-1)!} {\rm d}s\\
-&\mu_2\int_0^{t-v} e^{-\mu_1(t-s)}\frac{(\mu_1(t-s))^k}{k!} \left(\frac{t-s-v}{t-s}\right)^k \,e^{-\mu_2 s}\frac{(\mu_2 s)^{\ell-1}}{(\ell-1)!} {\rm d}s.
\end{align*}

The first term we recognize as $\mu_2\,\rho_{t}[k,\ell-1].$ The second term can be rewritten as

\[e^{-\mu_1 v}\mu_2\int_{0}^{t-v} e^{-\mu_1(t-s-v)}\frac{(\mu_1(t-s-v))^k}{k!} \,e^{-\mu_2 s}\frac{(\mu_2 s)^{\ell-1}}{(\ell-1)!} {\rm d}s,\]

which equals $e^{-\mu_1 v}\mu_2 \,\rho_{t-v}[k,\ell-1]$.

§.§.§ Description of convolution-based algorithm

We here provide a brief account of a method by which one can numerically evaluate a discrete-time approximation of the objective function. In this setup an equidistant  discrete grid is chosen on which the service times are defined; in the description below we assume, without loss of generality,  that the service times attain positive integer values.

Let as before $N_t$ denote the number of clients present at time $t\in{\mathbb N}$, and $R_t$ the elapsed service time of the client in service at $t$ (if any). In order to compute the objective function,
we have to compute probabilities of the type

\begin{equation}\label{prob0}
\mathfrak{p}[(m,k)\to(n,\ell)]:=
{\mathbb P}(N_t = n , R_t= \ell\,|\,N_0=m, R_0 = k),\end{equation}

and various related quantities (of which some are considerably more involved).
To compute the probability (<ref>), we define, for a given $k$, the distribution

\[{\mathbb P}(\xi^\star_k = k') = \frac{{\mathbb P}(\xi= k+k')}{{\mathbb P}(\xi\geqslant k)},\]

where $\xi$ is distributed as a single service time;
the random variable $\xi^\star_k$ represents the residual service time, conditional on the service time being at least $k$. As is seen easily,  the evaluation of $\mathfrak{p}[(m,k)\to(n,\ell)]$ requires a routine to compute probabilities of the type

\begin{equation}\label{prob}{\mathbb P}\left(\xi^\star_k +\sum_{i=1}^j\xi_i\leqslant t, \xi^\star_k +\sum_{i=1}^{j+1}\xi_i> t \right)
={\mathbb P}\left(\xi^\star_k +\sum_{i=1}^j\xi_i\leqslant t \right)-{\mathbb P}\left( \xi^\star_k +\sum_{i=1}^{j+1}\xi_i\leqslant t \right)

where the $\xi_i$ are i.i.d. copies of $\xi$, also independent of $\xi_k^\star$.

Suppose now that the $\xi_i$ are, say, (the discrete-time version of) lognormal or Weibull, then a complication is that we do not have explicit expressions for the density or the cumulative distribution function of the random variables appearing in the probability (<ref>). This means that we have to resort to numerical techniques to evaluate it, requiring the computation of a $(j+1)$-fold and a $(j+2)$-fold convolution. This is most efficiently done relying on fast Fourier transform methodology (and that is also how we implemented it).