Department of Computer Sciences, University of Wisconsin-Madison, United
Statesafan@cs.wisc.eduhttps://orcid.org/0000-0001-7714-2195 Department of
Computer Sciences, University of Wisconsin-Madison, United States and
https://pages.cs.wisc.edu/~paris/
paris@cs.wisc.eduhttps://orcid.org/0000-0001-6309-1702 Department of Computer
Sciences, University of Wisconsin-Madison, United
Stateshangdong@cs.wisc.eduhttps://orcid.org/0009-0009-7636-0831 Austen Z. Fan,
Paraschos Koutris and Hangdong Zhao [100]Database theory; Complexity theory
and logic John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product
Problems

Austen Z. Fan  Paraschos Koutris  Hangdong Zhao

###### Abstract

We study the fine-grained complexity of evaluating Boolean Conjunctive Queries
and their generalization to sum-of-product problems over an arbitrary
semiring. For these problems, we present a general _semiring-oblivious_
reduction from the $k$-clique problem to any query structure (hypergraph). Our
reduction uses the notion of embedding a graph to a hypergraph, first
introduced by Marx [18]. As a consequence of our reduction, we can show tight
conditional lower bounds for many classes of hypergraphs, including cycles,
Loomis-Whitney joins, some bipartite graphs, and chordal graphs. These lower
bounds have a dependence on what we call the clique embedding power of a
hypergraph $H$, which we believe is a quantity of independent interest. We
show that the clique embedding power is always less than the submodular width
of the hypergraph, and present a decidable algorithm for computing it. We
conclude with many open problems for future research.

###### keywords:

Fine-grained complexity, conjunctive queries, semiring-oblivious reduction

##  1 Introduction

In a seminal paper, Marx proved the celebrated result that
$\operatorname{CSP}(\mathcal{H})$ is fixed-parameter tractable (FPT) if and
only if the hypergraph $\mathcal{H}$ has a bounded submodular width [18]. In
the language of database theory, a Boolean Conjunctive Query (BCQ) can be
identified as the problem of $\operatorname{CSP}(\mathcal{H})$ where
$\mathcal{H}$ is the hypergraph associated with the query [10]. Thus, Marx’s
result implies that a class of Boolean Conjunctive Queries is FPT if and only
if its submodular width is bounded above by some universal constant. Built on
this result, Khamis, Ngo, and Suciu introduced in [15] the $\mathsf{PANDA}$
(Proof-Assisted eNtropic Degree-Aware) algorithm, which can evaluate a
BCQ111Technically, the $\mathsf{PANDA}$ algorithm works for Boolean or full
CQs. in time $\tilde{O}(|I|^{\mathsf{subw}(H)})$, where $|I|$ is the input
size and $\mathsf{subw}(\mathcal{H})$ is the submodular width of $\mathcal{H}$
(here $\tilde{O}$ hides polylogarithmic factors). Remarkably, the running time
of $\mathsf{PANDA}$ achieves the best known running time of _combinatorial
algorithm_ 222Informally speaking, this requires the algorithm does not
leverage the fast matrix multiplication. for _all_ BCQs. It is thus an
important open question whether there exists a faster combinatorial algorithm
than $\mathsf{PANDA}$ for some Boolean CQ.

To show that large submodular width implies not being FPT, Marx introduced the
notion of an _embedding_ , which essentially describes a reduction from one
$\operatorname{CSP}$ problem to another. Our key insight in this work is that
we can apply the notion of an embedding to measure how well cliques of
different sizes can be embedded to a hypergraph $\mathcal{H}$. By taking the
supremum over all possible clique sizes, we arrive at the definition of
_clique embedding power_ , denoted $\mathsf{emb}(\mathcal{H})$. The use of
cliques as the starting problem means that we can use popular lower bound
conjectures in fine-grained complexity (the Boolean $k$-Clique conjecture, the
Min-Weight $k$-Clique conjecture) to obtain (conditional) lower bounds for the
evaluation of BCQs that depend on $\mathsf{emb}(\mathcal{H})$.

Equipped with the new notion of the clique embedding power, we can show tight
lower bounds for several classes of queries. That is, assuming the Boolean
$k$-Clique Conjecture, we derive (conditional) lower bounds for many queries
that meet their submodular width, and therefore the current best algorithm, up
to polylogarithmic factors. In particular, we show that for cycles [2],
Loomis-Whitney joins [20], and chordal graphs, among others, the current
combinatorial algorithms are optimal.

We further extend the embedding reduction to be independent of the underlying
(commutative) semiring333A triple
$(\mathbf{D},\oplus,\otimes,\mathbf{0},\mathbf{1})$ is a commutative semiring
if $\oplus$ and $\otimes$ are commutative binary operators over $\mathbf{D}$
with the following properties: $(i)$ $(\mathbf{D},\oplus)$ is a commutative
monoid with an additive identity $\mathbf{0}$. $(ii)$ $(\mathbf{D},\otimes)$
is a commutative monoid with a multiplicative identity $\mathbf{1}$. $(iii)$
$\otimes$ distributes over $\oplus$. $(iv)$ For any element $e\in\mathbf{D}$,
we have $e\otimes\mathbf{0}=\mathbf{0}\otimes e=\mathbf{0}$.. It was observed
by Green, Karvounarakis, and Tannen [9] that the semantics of CQs can be
naturally generalized to sum-of-product operations over a semiring. This point
of view unifies a number of database query semantics that seem unrelated. For
example, evaluation over set semantics corresponds to evaluation over the
Boolean semiring $\sigma_{\mathbb{B}}=(\\{0,1\\},\vee,\wedge,0,1)$, while bag
semantics corresponds to the semiring $(\mathbb{N},+,\times,0,1)$.
Interestingly, following this framework, the decision problem of finding a
$k$-clique in a graph can be interpreted as the following sum-of-product
operation: consider the input graph $G=(V,E)$ as the edge-weighted graph of
the complete graph with $|V|$ vertices where
$\mathsf{weight}(e)=\mathbbm{1}_{e\in E}$; then the problem is to compute
$\bigvee_{{V^{\prime}\subseteq
V:|V^{\prime}|=k}}\bigwedge\mathsf{w}(\\{v,w\\})$. Observe that by changing
the underlying semiring to be the tropical semiring
$\mathsf{trop}=(\mathbb{R}^{\infty},\min,+,\infty,0)$, this formulation
computes the min-weight $k$-clique problem. Indeed, given an edge-weighted
graph (where the weight of non-existence edges is 0), the minimum weight of
its $k$-clique is exactly $\min_{{V^{\prime}\subseteq
V:|V^{\prime}|=k}}\sum\mathsf{w}(\\{v,w\\})$. We prove that the clique
embedding reduction is _semiring-oblivious_ , i.e., the reduction holds for
arbitrary underlying semirings. This enables one to transfer the lower bound
result independent of the underlying semiring and should be of independent
interest.

Recent years have witnessed emerging interests in proving lower bounds for the
runtime of database queries (see Durand [8] for a wonderful survey). Casel and
Schmid consider the fine-grained complexity of regular path queries over graph
databases [7]. Joglekar and Ré prove a full dichotomy for whether a 1-series-
parallel graph admits a subquadratic algorithm [12]. Their proof is based on
the hardness hypothesis that 3-XOR cannot be solved in subquadratic time.
Perhaps the line of work in spirit closest to ours is the characterization of
queries which can be enumerated by linear preprocessing time and constant
delay [3, 6, 4]. However, their results focus on the enumeration problem, and
therefore are different to the main subject of our paper. Furthermore, their
characterization mainly classifies queries based on the existence of a linear
preprocessing time and constant delay algorithm. In contrast, our method can
provide a lower bound for _every_ query.

##### Our Contributions

We summarize our contributions as follows:

  * •

We introduce the notion of the clique embedding power
$\mathsf{emb}(\mathcal{H})$ of a hypergraph $\mathcal{H}$ (Section 3). We show
several interesting properties of this notion; most importantly, we show that
it is always upper-bounded by the submodular width,
$\mathsf{subw}(\mathcal{H})$. This connection can be seen as additional
evidence of the plausibility of the lower bound conjectures for the $k$-clique
problem.

  * •

We show how to construct a reduction from the $k$-clique problem to any
hypergraph $\mathcal{H}$ for any semiring, and discuss how the clique
embedding power provides a lower bound for its running time (Section 4).

  * •

We study how to compute $\mathsf{emb}(\mathcal{H})$ (Section 5). In
particular, we prove that it is a decidable problem, and give a Mixed Integer
Linear Program formulation. One interesting consequence of this formulation is
that to achieve $\mathsf{emb}(\mathcal{H})$ it suffices to consider clique
sizes that depend on the hypergraph size.

  * •

We identify several classes of hypergraphs for which
$\mathsf{emb}(\mathcal{H})=\mathsf{subw}(\mathcal{H})$ (Section 6). For these
classes of queries, our lower bounds match the best known upper bounds if we
consider the Boolean semiring with combinatorial algorithms, or the tropical
semiring. The most interesting class of hypergraphs we consider is the class
of chordal hypergraphs (which captures chordal graphs).

  * •

Finally, we identify a hypergraph with six vertices for which there is a gap
between its clique embedding power and submodular width (Section 7). We
believe that the existence of this gap leaves many open questions.

##  2 Background

In this section, we define the central problem, and notions necessary for our
results.

##### The SumProduct Problem

We define this general problem following the notation in [14, 13]. Consider
$\ell$ variables $x_{1},x_{2},\dots,x_{\ell}$, where each variable $x_{i}$
takes values in some discrete domain $\mathsf{Dom}(x_{i})$. A valuation $v$ is
a function that maps each $x_{i}$ to $\mathsf{Dom}(x_{i})$. For a subset
$S\subseteq[\ell]$, we define the tuple $\mathbf{x}_{S}=(x_{i})_{i\in S}$ and
$v(\mathbf{x}_{S})=(v(x_{i}))_{i\in S}$.

The SumProduct Problem is parameterized by:

  1. 1.

a commutative semiring
$\sigma=(\mathbf{D},\oplus,\otimes,\mathbf{0},\mathbf{1})$, where $\mathbf{D}$
is a fixed domain.

  2. 2.

a hypergraph $\mathcal{H}=(V,E)$ where $V=[\ell]$.

The input $I$ specifies for every hyperedge $e\in E$ a function
$R_{e}:\prod_{i\in e}\mathsf{Dom}(x_{i})\rightarrow\mathbf{D}$. This function
is represented in the input as a table of all tuples of the form
$(\mathbf{a}_{e},R_{e}(\mathbf{a}_{e}))$, such that
$R_{e}(\mathbf{a}_{e})\neq\mathbf{0}$. This input representation is standard
in the CSP and database settings. We use $|I|$ to denote the input size, which
is simply the sum of sizes of all tables in the input.

The SumProduct Problem then asks to compute the following function:

$\bigoplus_{v:\text{valuation}}\bigotimes_{e\in E}R_{e}(v(\mathbf{x}_{e})).$

We will say that $v$ is a solution for the above problem if $\bigotimes_{e\in
E}R_{e}(v(\mathbf{x}_{e}))\neq\mathbf{0}$.

Within this framework, we can capture several important problems depending on
the choice of the semiring and the hypergraph. If we consider the Boolean
semiring $\sigma_{\mathbb{B}}=(\\{0,1\\},\vee,\wedge,0,1)$, then each $R_{e}$
behaves as a relational instance ($R_{e}$ is $1$ if the tuple is in the
instance, otherwise $0$) and the SumProduct function captures Boolean
Conjunctive Query evaluation. If $\sigma=(\mathbb{N},+,\times,0,1)$ and
$R_{e}$ is defined as above, then the SumProduct function computes the number
of solutions to a Conjunctive Query. Another important class of problems is
captured when we consider the min-tropical semiring
$\mathsf{trop}=(\mathbb{R}^{\infty},\min,+,\infty,0)$ and we assign each tuple
to a non-negative weight; this computes a minimum weight solution that
satisfies the structural properties.

##### The Complexity for SumProduct Problems

We adopt the random-access machine (RAM) as our computation model with $O(\log
n)$-bit words, which is standard in fine-grained complexity. The machine has
read-only input registers which contains the database and the query, read-
write work memory registers, and write-only output registers. It is assumed
that each register can store any tuple, and each tuple is stored in one
register. The machine can perform all “standard” 444This includes all
arithmetic (e.g. $+,-,\div,*$) and logical operations. operations on one or
two registers in constant time.

In this paper, we are interested in the computational complexity of a
SumProduct problem for a fixed hypergraph $\mathcal{H}$. (This is typically
called data complexity). We will consider two different ways of treating
semirings when we think about algorithms.

In the first variant, we fix the semiring $\sigma$ along with the hypergraph
$\mathcal{H}$. This means that the representation of the semiring is not part
of the input and is known a priori to the algorithm. We denote this problem as
$\mathsf{SumProd}\langle\sigma,\mathcal{H}\rangle$. In the second variant, we
consider algorithms that access the semiring only via an oracle. In
particular, the algorithm does not know the semiring a priori and can only
access it during runtime by providing the values for the $\oplus,\otimes$
operations. We assume that each of these operations takes a constant amount of
time. We denote this problem as $\mathsf{SumProd}\langle\mathcal{H}\rangle$.

Our goal in this paper is to specify the exact exponent of $|I|$ in the
polynomial-time runtime cost of an algorithm that computes
$\mathsf{SumProd}\langle\sigma,\mathcal{H}\rangle$ or
$\mathsf{SumProd}\langle\mathcal{H}\rangle$.

##### Tree Decompositions

A tree decomposition of a hypergraph $\mathcal{H}$ is a pair
$(\mathcal{T},\chi)$, where $\mathcal{T}$ is a tree and $\chi$ maps each node
$t\in V(\mathcal{T})$ of the tree to a subset $\chi(t)$ of $V(\mathcal{H})$
such that:

  1. 1.

every hyperedge $e\in E(\mathcal{H})$ is a subset of $\chi(t)$ for some $t\in
V(\mathcal{T})$; and

  2. 2.

for every vertex $v\in V(\mathcal{H})$, the set $\\{t\mid v\in\chi(t)\\}$ is a
non-empty connected subtree of $\mathcal{T}$.

We say that a hypergraph $\mathcal{H}$ is acyclic if it has a tree
decomposition such that each bag corresponds to a hyperedge.

##### Notions of Width

Let $\mathcal{H}$ be a hypergraph and $F$ be a set function over $V(H)$. The
$F$-width of a tree decomposition $(\mathcal{T},\chi)$ is defined as
$\max_{t}F(\chi(t))$. The $F$-width of $\mathcal{H}$ is the minimum $F$-width
over all possible tree decompositions of $\mathcal{H}$.

A fractional independent set of a hypergraph $\mathcal{H}$ is a mapping
$\mu:V(\mathcal{H})\rightarrow[0,1]$ such that $\sum_{v\in e}\mu(v)\leq 1$ for
every $e\in E(\mathcal{H})$. We naturally extend functions on the vertices of
$\mathcal{H}$ to subsets of vertices of $\mathcal{H}$ by setting
$\mu(X)=\sum_{v\in X}\mu(v)$.

The adaptive width $\mathsf{adw}(\mathcal{H})$ of a hypergraph $\mathcal{H}$
is defined as the supreme of $F\text{-width}(\mathcal{H})$, where $F$ goes
over all fractional independent sets of $\mathcal{H}$. Hence if
$\mathsf{adw}(\mathcal{H})\leq w$, then for every $\mu$, there exists a tree
decomposition of $\mathcal{H}$ with $\mu$-width at most $w$.

A set function $F$ is submodular if for any two sets $A,B$ we have $F(A\cup
B)+F(A\cap B)\leq F(A)+F(B)$. It is monotone if whenever $A\subseteq B$, then
$F(A)\leq F(B)$. The submodular width $\mathsf{subw}(\mathcal{H})$ of a
hypergraph $\mathcal{H}$ is defined as the supreme of
$F\text{-width}(\mathcal{H})$, where $F$ now ranges over all non-negative,
monotone, and submodular set functions over $V(\mathcal{H})$ such that for
every hyperedge $e\in E(\mathcal{H})$, we have $F(e)\leq 1$. A non-negative,
monotone, and submodular set function $F$ is edge-dominated if $F(e)\leq 1$,
for every $e\in E$.

The fractional hypertree width of a hypergraph $\mathcal{H}$ is
$\mathsf{fhw}(\mathcal{H})=\min_{(\mathcal{T},\chi)}\max_{t\in
V(\mathcal{T})}\rho^{*}(\chi(t))$, where $\rho^{*}$ is the minimum fractional
edge cover number of the set $\chi(t)$. It holds that
$\mathsf{adw}(\mathcal{H})\leq\mathsf{subw}(\mathcal{H})\leq\mathsf{fhw}(\mathcal{H})$.

It is known that
$\mathsf{SumProd}\langle\sigma_{\mathbb{B}},\mathcal{H}\rangle$ can be
computed in time $\tilde{O}(|I|^{\mathsf{subw}(\mathcal{H})})$ using the
$\mathsf{PANDA}$ algorithm [15]. However, we do not know of a way to achieve
the same runtime for the general $\mathsf{SumProd}\langle\mathcal{H}\rangle$
problem. For this, the best known runtime is
$\tilde{O}(|I|^{\mathsf{\\#\mathsf{subw}}(\mathcal{H})})$, where
$\mathsf{subw}(\mathcal{H})\leq\\#\mathsf{subw}(\mathcal{H})\leq\mathsf{fhw}(\mathcal{H})$
[13]. On the other hand, there are hypergraphs for which we can compute
$\mathsf{SumProd}\langle\sigma_{\mathbb{B}},\mathcal{H}\rangle$ with runtime
better than $\tilde{O}(|I|^{\mathsf{subw}(\mathcal{H})})$ using non-
combinatorial algorithms. For example, if $\mathcal{H}$ is a triangle we can
obtain a runtime $\tilde{O}(|I|^{2\omega/(\omega+1)})$, where $\omega$ is the
matrix multiplication exponent (the submodular width of the triangle is
$3/2$).

##### Conjectures in Fine-Grained Complexity

Our lower bounds will be based on the following popular conjectures in fine-
grained complexity. To state the conjectures, it will be helpful to define the
$k$-clique problem over a semiring $\sigma$: given an undirected graph
$G=(V,E)$ where each edge has a weight in the domain of the semiring, we are
asked to compute the semiring-product over all the $k$-cliques in $G$, where
the weight of each clique is the semiring-sum of clique edge weights.

######  Definition 2.1 (Boolean $k$-Clique Conjecture).

There is no real $\epsilon>0$ such that computing the $k$-clique problem (with
$k\geq 3$) over the Boolean semiring in an (undirected) $n$-node graph
requires time $O(n^{k-\epsilon})$ using a combinatorial algorithm.

######  Definition 2.2 (Min-Weight $k$-Clique Conjecture).

There is no real $\epsilon>0$ such that computing the $k$-clique problem (with
$k\geq 3$) over the tropical semiring in an (undirected) $n$-node graph with
integer edge weights can be done in time $O(n^{k-\epsilon})$.

When $k=3$, min-weight 3-clique is equivalent to the All-Pairs Shortest Path
(APSP) problem under subcubic reductions. The Min-Weight Clique Conjecture
assumes the Min-Weight $k$-Clique conjecture for every integer $k\geq 3$
(similarly for the Boolean Clique Conjecture).

##  3 The Clique Embedding Power

In this section, we define the clique embedding power, a quantity central to
this paper.

###  3.1 Graph Embeddings

We introduce first the definition of embedding a graph $G$ to a hypergraph
$\mathcal{H}$, first defined by Marx [18, 17]. We say that two sets of
vertices $X,Y\subseteq V(\mathcal{H})$ touch in $\mathcal{H}$ if either $X\cap
Y\neq\emptyset$ or there is a hyperedge $e\in E(\mathcal{H})$ that intersects
both $X$ and $Y$. We say a hypergraph is connected if its underlying clique
graph is connected.

######  Definition 3.1 (Graph Embedding).

Let $G$ be an undirected graph, and $\mathcal{H}$ be a hypergraph. An
embedding from $G$ to $\mathcal{H}$, denoted $G\mapsto\mathcal{H}$, is a
mapping $\psi$ that maps every vertex $v\in V(G)$ to a non-empty subset
$\psi(v)\subseteq V(\mathcal{H})$ such that the following hold:

  1. 1.

$\psi(v)$ induces a connected subhypergraph;

  2. 2.

if $u,v\in V(G)$ are adjacent in $G$, then $\psi(u),\psi(v)$ touch in
$\mathcal{H}$.

It will often be convenient to describe an embedding $\psi$ by the reverse
mapping $\psi^{-1}(x)=\\{i\mid x\in\psi(i)\\}$, where $x$ is a vertex in
$V(\mathcal{H})$. Given an embedding $\psi$ and a vertex $v\in
V(\mathcal{H})$, we define its vertex depth as $d_{\psi}(v)=|\psi^{-1}(v)|$.
For a hyperedge $e\in E(\mathcal{H})$, we define its weak edge depth as
$d_{\psi}(e)=|\\{v\in V(G)\mid\psi(v)\cap e\neq\emptyset\\}|$, i.e., the
number of vertices of $G$ that map to some variable in $e$. Moreover, we
define the edge depth of $e$ as $d^{+}_{\psi}(e)=\sum_{v\in e}d_{\psi}(v)$.

The weak edge depth of an embedding $\psi$ can then be defined as
$\mathsf{wed}(\psi)=\max_{e}d_{\psi}(e)$, and the edge depth as
$\mathsf{ed}(\psi)=\max_{e}d^{+}_{\psi}(e)$. Additionally, we define as
$\mathsf{wed}(G\mapsto\mathcal{H})$ the minimum weak edge depth of any
embedding $\psi$ from $G$ to $\mathcal{H}$. Similarly for
$\mathsf{ed}(G\mapsto\mathcal{H})$. It is easy to see that
$\mathsf{wed}(G\mapsto\mathcal{H})\leq\mathsf{ed}(G\mapsto\mathcal{H})$.

It will be particularly important for our purposes to think about embedding
the $k$-clique graph $C_{k}$ to an arbitrary hypergraph $\mathcal{H}$. In this
case, it will be simpler to think of the vertices of $G$ as the numbers
$1,\dots,k$ and the embedding $\psi$ as a mapping from the set
$\\{1,\dots,k\\}$ to a subset of $V(\mathcal{H})$. We can now define the
following quantity, which captures how well we can embed a $k$-clique to $H$
for an integer $k\geq 3$:

$\mathsf{emb}_{k}(\mathcal{H}):=\frac{k}{\mathsf{wed}(C_{k}\mapsto\mathcal{H})}.$

######  Example 3.2.

Consider the hypergraph $\mathcal{H}$ with the following hyperedges:

$\\{x_{1},x_{2},x_{3}\\},\\{x_{1},y\\},\\{x_{2},y\\},\\{x_{3},y\\}$

We can embed the $5$-clique into $\mathcal{H}$ as follows:

$1\rightarrow\\{x_{1}\\},2\rightarrow\\{x_{2}\\},3\rightarrow\\{x_{3}\\},4,5\rightarrow\\{y\\}.$

It it easy to check that is this a valid embedding, since, for example, $1,4$
touch at the edge $\\{x_{1},y\\}$. Moreover, $\mathsf{wed}(C_{5}\mapsto G)=3$,
hence $\mathsf{emb}_{5}(G)=5/3$.

###  3.2 Embedding Properties

In this part, we will explore how $\mathsf{wed}(C_{k}\mapsto\mathcal{H})$ and
$\mathsf{emb}_{k}(\mathcal{H})$ behave as a function of the size of the clique
$k$. We start with some basic observations, whose proofs are elaborated in
Appendix A.

######  Proposition 3.3.

For any hypergraph $\mathcal{H}$ and integer $k\geq 3$:

  1. 1.

$\mathsf{wed}(C_{k}\mapsto\mathcal{H})\leq k$.

  2. 2.

$\mathsf{wed}(C_{k}\mapsto\mathcal{H})\leq\mathsf{wed}(C_{k+1}\mapsto
H)\leq\mathsf{wed}(C_{k}\mapsto\mathcal{H})+1.$

  3. 3.

If $k=m\cdot n$, where $k,m,n\in\mathbb{Z}_{\geq 0}$, then
$\mathsf{emb}_{k}(\mathcal{H})\geq\mathsf{emb}_{m}(\mathcal{H})$.

The first item of the above proposition tells us that
$\mathsf{emb}_{k}(\mathcal{H})\geq 1$ for any $k$. But how does
$\mathsf{emb}_{k}(\mathcal{H})$ behave as $k$ grows? We next show that
$\mathsf{emb}_{k}(\mathcal{H})$ is always upper bounded by the submodular
width of $\mathcal{H}$.

######  Lemma 3.4.

Let $\mathcal{H}$ be a hypergraph. Take an embedding
$\psi:C_{k}\mapsto\mathcal{H}$. Let $(\mathcal{T},\chi)$ be a tree
decomposition of $\mathcal{H}$. Then, there exists a node $t\in T$ such that
for every $i=1,\dots,k$, $\psi(i)\cap\chi(t)\neq\emptyset$.

######  Proof 3.5.

For $i=1,\dots,k$, let $\mathcal{T}_{i}$ be the subgraph of $\mathcal{T}$ that
includes all nodes $t\in V(\mathcal{T})$ such that
$\psi(i)\cap\chi(t)\neq\emptyset$.

We first claim that $\mathcal{T}_{i}$ forms a tree. To show this, it suffices
to show that $\mathcal{T}_{i}$ is connected. Indeed, take any two nodes
$t_{1},t_{2}$ in $\mathcal{T}_{i}$. This means that there exists
$x_{1}\in\chi(t_{1})\cap\psi(i)$ and $x_{2}\in\chi({t_{2}})\cap\psi(i)$. Since
$x_{1},x_{2}\in\psi(i)$ and $\psi(i)$ induces a connected subgraph in
$\mathcal{H}$, there exists a sequence of vertices
$x_{1}=z_{1},\dots,z_{k}=x_{2}$, all in $\psi(i)$, such that every two
consecutive vertices belong to an edge of $\mathcal{H}$. Let
$S_{1},\dots,S_{k}$ be the trees in $\mathcal{T}$ that contain
$z_{1},\dots,z_{k}$ respectively. Take any two consecutive $z_{i},z_{i+1}$:
since they belong to the same edge, there exists a bag that contains both of
them, hence $S_{i},S_{i+1}$ intersect. This means that there exists a path
between $t_{1},t_{2}$ in $\mathcal{T}$ such that every node is in $T_{i}$.

Second, we claim that any two $\mathcal{T}_{i},\mathcal{T}_{j}$ have at least
one common vertex. Indeed, $\psi(i)$, $\psi(j)$ must touch in $\mathcal{H}$.
If there exists a variable $x\in\psi(i)\cap\psi(j)$, then any vertex that
contains $x$ is a common vertex between $\mathcal{T}_{i},\mathcal{T}_{j}$.
Otherwise, there exists $x\in\psi(i)$, $y\in\psi(j)$ such that $x,y$ occur
together in a hyperedge $e\in E(\mathcal{H})$. But this means that some node
$t\in\mathcal{T}$ contains both $x,y$, hence $\mathcal{T}_{i},\mathcal{T}_{j}$
intersect at $t$.

Finally, we apply the fact that a family of subtrees of a tree satisfies the
Helly property [11], i.e. a collection of subtrees of a tree has at least one
common node if and only if every pair of subtrees has at least one common
node. Indeed, the trees $\mathcal{T}_{1},\dots,\mathcal{T}_{k}$ satisfy the
latter property, so there is a vertex $t$ common to all of them. Such $t$ has
the desired property of the lemma.

We can now state the following Theorem 3.6 on the embedding power of a
hypergraph. A similar result for $\mathsf{adw}$ is stated and proven in
Theorem A.2 in Appendix A.

######  Theorem 3.6.

For any hypergraph $\mathcal{H}$ and integer $k\geq 3$, the following holds:

$\mathsf{wed}(C_{k}\mapsto\mathcal{H})\geq\frac{k}{\mathsf{subw}(\mathcal{H})}$

######  Proof 3.7.

Let $\mathsf{wed}(C_{k}\mapsto\mathcal{H})=\alpha$. Then, there is an
embedding $\psi:C_{k}\mapsto\mathcal{H}$ with weak edge depth $\alpha$. We
will show that $\mathsf{subw}(\mathcal{H})\geq k/\alpha$.

First, we define the following set function over subsets of $V(\mathcal{H})$:
for any $S\subseteq V(\mathcal{H})$, let $\mu(S)=|\\{i\mid\psi(i)\cap
S\neq\emptyset\\}|/\alpha$. This is a coverage function, and hence it is a
submodular function. It is also edge-dominated, since for any hyperedge $e$,
we have $\mu(e)=|\\{i\mid\psi(i)\cap e\neq\emptyset\\}|/\alpha\leq 1$.

Now, consider any decomposition $(\mathcal{T},B_{t})$ of $\mathcal{H}$. From
Lemma 3.4, there is a node $t\in\mathcal{T}$ such that or every $i=1,\dots,k$,
$\psi(i)\cap B_{t}\neq\emptyset$. Hence, $\mu(B_{t})=|\\{i\mid\psi(i)\cap
B_{t}\neq\emptyset\\}|/\alpha=k/\alpha$. Thus, the submodular width of the
decomposition is at least $k/\alpha$.

The above result tells us that
$\mathsf{emb}_{k}(\mathcal{H})\leq\mathsf{subw}(\mathcal{H})$ for any $k\geq
3$. Hence, taking the supremum of $\mathsf{emb}_{k}(\mathcal{H})$ for $k\geq
3$ is well-defined, since the set is bounded. This leads us to the following
definition:

######  Definition 3.8 (Clique Embedding Power).

Given a hypergraph $\mathcal{H}$, define the clique embedding power of
$\mathcal{H}$ as

$\mathsf{emb}(\mathcal{H}):=\sup_{k\geq
3}\mathsf{emb}_{k}(\mathcal{H})=\sup_{k\geq
3}\frac{k}{\mathsf{wed}(C_{k}\mapsto\mathcal{H})}.$

The following is immediate:

######  Corollary 3.9.

For any hypergraph $\mathcal{H}$,
$1\leq\mathsf{emb}(\mathcal{H})\leq\mathsf{subw}(\mathcal{H})$.

##  4 Lower Bounds

In this section, we show how to use the clique embedding power to obtain
conditional lower bounds for SumProduct problems. Our main reduction follows
the reduction used in [18], but also has to account for constructing the
appropriate values for the semiring computations.

######  Theorem 4.1.

For any hypergraph $\mathcal{H}$ and semiring $\sigma$, if
$\mathsf{SumProd}\langle\sigma,\mathcal{H}\rangle$ can be solved in time
$O(|I|^{c})$ with input $I$, then $k$-Clique over $\sigma$ can be solved in
time $O(n^{c\cdot\mathsf{wed}(C_{k}\mapsto\mathcal{H})})$ where $n$ is the
number of vertices.

######  Proof 4.2.

We will show a reduction from the $k$-clique problem with $n$ vertices over a
semiring $\sigma$ to $\mathsf{SumProd}\langle\sigma,\mathcal{H}\rangle$.
Without loss of generality, we will assume that the input graph $G$ to the
$k$-clique problem is $k$-partite, with partitions $V_{1},\dots,V_{k}$.
Indeed, given any graph $G=(V,E)$ where $V=\\{v_{1},v_{2},\dots,v_{n}\\}$,
consider the $k$-partite graph $G^{k}=(V^{k},E^{k})$ where
$V^{k}=\\{v_{i}^{j}\mid 1\leq i\leq n,1\leq j\leq k\\}$ and for any two
vertices $v_{i}^{j},v_{p}^{q}\in V^{k}$, $\\{v_{i}^{j},v_{p}^{q}\\}\in E^{k}$
iff $\\{v_{i},v_{p}\\}\in E$ and $j\neq q$. Then there is a one-to-one mapping
from a $k$-clique in $G$ to a $k$-clique in $G^{k}$.

Let $\psi$ be an embedding from $C_{k}$ to $\mathcal{H}$ that achieves a weak
edge depth $\lambda=k/\mathsf{emb}_{k}(\mathcal{H})$. As we mentioned before,
it is convenient to take $V(C_{k})=\\{1,\dots,k\\}$. We now construct the
input instance $I$ for $\mathsf{SumProd}\langle\sigma,\mathcal{H}\rangle$.
More explicitly, the task is to construct the function $R_{e}$ for each
hyperedge $e\in E$.

To this end, we first assign to each pair $\\{i,j\\}:i\neq
j,i,j,\in\\{1,2,\dots,k\\}$ a hyperedge $\theta(\\{i,j\\})=e\in
E(\mathcal{H})$ satisfying the following conditions: $\psi(i)\cap
e\neq\emptyset$ and $\psi(j)\cap e\neq\emptyset$. Such an $e$ must exist by
the definition of an embedding. If there is more than one hyperedge satisfying
the condition, we arbitrarily choose one.

For every variable $x\in V(\mathcal{H})$, let $\psi^{-1}(x)$ be the subset of
$\\{1,\dots,k\\}$ mapping to $x$. Then, we define the domain
$\mathsf{Dom}(x_{i})$ of each variable $x_{i}$ in the input instance as
vectors over ${[n]}^{|\psi^{-1}(x_{i})|}$. Let
$S_{e}=\\{i\in[k]\mid\psi(i)\cap e\neq\emptyset\\}$. Note that
$|S_{e}|=d_{\psi}(e)\leq\lambda$. Also, note that $\psi^{-1}(x)\subseteq
S_{e}$ for all $x\in e$. Then, we compute all cliques in the graph $G$ between
the partitions $V_{i},i\in S_{e}$; these cliques will be of size $|S_{e}|$ and
can be computed in running time $O(n^{\lambda})$ by brute force.

For every clique $\\{a_{i}\in V_{i}\mid i\in S_{e}\\}$, let $t$ be the tuple
over $\prod_{i\in S_{e}}\mathsf{Dom}(x_{i})$ such that its value at position
$x$ is $\langle a_{i}\mid i\in\psi^{-1}(x)\rangle$. Then, we set

$R_{e}(t)=\mathbf{1}\otimes\bigotimes_{\\{i,j\\}:\theta(\\{i,j\\})=e}w(\\{i,j\\}).$

In other words, we set the value as the semiring product of all the weights
between the edges $\\{a_{i},a_{j}\\}$ in the clique whenever the pair
$\\{i,j\\}$ is assigned to the hyperedge $e$. All the other tuples are mapped
to $\mathbf{0}$. By construction, the size of the input is
$|I|=O(n^{\lambda})$.

We now show that the two problems will return exactly the same output. To show
this, we first show that there is a bijection between $k$-cliques in $G$ and
the solutions of the SumProduct instance.

$\Leftarrow$ Take a clique $\\{a_{1},\dots,a_{k}\\}$ in $G$. We map the clique
to the valuation $v(x)=\langle a_{i}\mid i\in\psi^{-1}(x)\rangle$. This
valuation is a solution to the SumProduct problem, since any subset of
$\\{a_{1},\dots,a_{k}\\}$ forms a sub-clique. Hence for any hyperedge $e$,
$R_{e}(v(\mathbf{x}_{e}))\neq\mathbf{0}$.

$\Rightarrow$ Take a valuation $v$. Consider any $i\in\\{1,\dots,k\\}$ and
consider any two variables $x,y\in\psi(i)$ (recall that $\psi(i)$ must be
nonempty). Recall that $x,y\in V(\mathcal{H})$. We claim that the $i$-th index
in the valuation $v(x),v(y)$ must take the same value, which we will denote as
$a_{i}$; this follows from the connectivity condition of the embedding.
Indeed, since $x,y\in\psi(i)$, there exists a sequence of hyperedges
$e_{1},e_{2},\dots,e_{m}$ where $m\geq 1$ such that $e_{j}\cap
e_{j+1}\neq\emptyset$ for $1\leq j\leq m-1$ and $x\in e_{1}$, $y\in e_{m}$. By
the construction, the $i$-th index in $v(x)$ will then “propagate” to that in
$v(y)$. This proves the claim. It then suffices to show that
$\\{a_{1},\dots,a_{k}\\}$ is a clique in $G$. Indeed take any
$i,j\in\\{1,\dots,k\\}$. Since $i$ and $j$ are adjacent as two vertices in
$C_{k}$, we know $\psi(i)$ and $\psi(j)$ touch. Therefore, there exists a
hyperedge $e$ that contains some $x\in\psi(i)$ and $y\in\psi(j)$. But this
means that $\\{a_{i},a_{j}\\}$ must form an edge in $G$.

We next show that the semiring product of the weights in the clique has the
same value as the semiring product of the corresponding solution. Indeed:

$\bigotimes_{e\in E}R_{e}(v(\mathbf{x}_{e}))=\mathbf{1}\otimes\bigotimes_{e\in
E}\bigotimes_{\\{i,j\\}:\theta(\\{i,j\\})=e}w(\\{i,j\\})=\bigotimes_{\\{i,j\\}:i\neq
j}w(\\{i,j\\})$

where the last equality holds because each edge of the $k$-clique is assigned
to exactly one hyperedge of $\mathcal{H}$.

The above claim together with the bijection show that the output will be the
same; indeed, each the semiring sums will go over exactly the same elements
with the same values.

To conclude the proof, suppose that
$\mathsf{SumProd}\langle\sigma,\mathcal{H}\rangle$ could be answered in time
$O(|I|^{c})$ for some $c\geq 1$. This means that we can solve the $k$-clique
problem over $\sigma$ in time
$O(n^{\lambda}+n^{c\lambda})=O(n^{c\cdot\mathsf{wed}(C_{k}\mapsto\mathcal{H})})$.

As an immediate consequence of Theorem 4.1, we can show the following lower
bound.

######  Proposition 4.3.

Under the Min-Weight $k$-Clique conjecture,
$\mathsf{SumProd}\langle\mathsf{trop},\mathcal{H}\rangle$ (and thus
$\mathsf{SumProd}\langle\mathcal{H}\rangle$) cannot be computed in time
$O(|I|^{\mathsf{emb}_{k}(\mathcal{H})-\epsilon})$ for any constant
$\epsilon>0$.

######  Proof 4.4.

Indeed, if $\mathsf{SumProd}\langle\mathsf{trop},\mathcal{H}\rangle$ can be
computed in time $O(|I|^{\mathsf{emb}_{k}(\mathcal{H})-\epsilon})$ for some
constant $\epsilon>0$, then by Theorem 4.1 the $k$-Clique problem over the
tropical semiring can be solved in time
$O(n^{(\mathsf{emb}_{k}(\mathcal{H})-\epsilon)\cdot\mathsf{wed}(C_{k}\mapsto\mathcal{H})})=O(n^{k-\delta})$
for some $\delta>0$. However, this violates the Min-Weight $k$-Clique
conjecture.

Similarly, we can show the following:

######  Proposition 4.5.

Under the Boolean $k$-Clique conjecture,
$\mathsf{SumProd}\langle\sigma_{\mathbb{B}},\mathcal{H}\rangle$ (and thus
$\mathsf{SumProd}\langle\mathcal{H}\rangle$) cannot be computed via a
combinatorial algorithm in time
$O(|I|^{\mathsf{emb}_{k}(\mathcal{H})-\epsilon})$ for any constant
$\epsilon>0$.

The above two results imply that to obtain the best lower bound, we need to
find the clique size with the largest $\mathsf{emb}_{k}(\mathcal{H})$.
However, the function $k\mapsto\mathsf{emb}_{k}(\mathcal{H})$ is really
intriguing. It is not clear whether in the definition supremum is ever needed,
i.e., whether there exists a hypergraph where the embedding power is achieved
in the limit.

In section 5, we show that for every hypergraph $\mathcal{H}$, there exists a
natural number $k$ such that
$\mathsf{emb}(\mathcal{H})=\mathsf{emb}_{k}(\mathcal{H})$. We also demonstrate
how to compute $\mathsf{emb}(\mathcal{H})$ through a MILP and locate the
complexity of computing the embedding power within the class
2-$\mathsf{EXPTIME}$ (double exponential time). The insight of our method is
that, instead of computing the “integral” embedding power, one can consider
the “fractional” embedding power and then recover the “integral” one by
letting the clique size $k$ to be sufficiently large.

##  5 Decidability of the Clique Embedding Power

To illustrate the algorithm for computing $\mathsf{emb}(\mathcal{H})$, it is
instructive to first show how to compute $\mathsf{emb}_{k}(\mathcal{H})$ for a
fixed clique size $k$.

###  5.1 An Integer Linear Program for $\mathsf{wed}(C_{k}\mapsto\mathcal{H})$

The following ILP formulation computes the minimum weak edge depth
$w=\mathsf{wed}(C_{k}\mapsto\mathcal{H})$.

$\begin{array}[]{llllllll}\displaystyle\min&\lx@intercol w\hfil\lx@intercol\\\
\textrm{s.t.}&&&\displaystyle\sum\limits_{S\subseteq V}x_{S}&=&k\\\
&&&x_{S}&=&0&\forall S\subseteq V&\textrm{ where }\textrm{$S$ is not
connected}\\\ &&&\min\\{x_{S},x_{T}\\}&=&0&\forall S,T\subseteq V&\textrm{
where $S,T$ do not touch}\\\ \displaystyle&&&\sum\limits_{S\subseteq V:e\cap
S\neq\emptyset}x_{S}&\leq&w&\forall e\in\mathcal{E}\\\
&&&x_{S}&\in&\mathbb{Z}_{\geq 0}&\forall S\subseteq V\end{array}$ (1)

Each integer variable $x_{S}$, $S\subseteq V$, indicates how many vertices in
$C_{k}$ are assigned to the subset $S$. For example, if $x_{\\{1,2\\}}=3$,
this means in the embedding $\psi$, three vertices are mapped to the subset
$\\{1,2\\}\subseteq V$. It is sufficient to record only the number of vertices
in $C_{k}$ because of the symmetry of the clique. That is, since any two
vertices are connected in $C_{k}$, one can arbitrarily permute the vertices in
$C_{k}$ so that the resulting map $\psi^{\prime}$ is still an embedding (given
$\psi$ is). Moreover, since the clique size $k$ is fixed, to compute
$\mathsf{emb}_{k}(\mathcal{H})$ it suffices to minimize $w$.

Observe that the condition $\min\\{x_{S},x_{T}\\}=0$ is not a linear
condition. To encode it as such, we perform a standard transformation. We
introduce a binary variable $y_{S}$ for every set $S\subseteq V$. Then, we can
write it as

$\left\\{\begin{array}[]{lllll}&x_{S}&+&k\cdot y_{S}&\leq k\\\ &x_{T}&+&k\cdot
y_{T}&\leq k\\\ &y_{S}&+&y_{T}&\geq 1\\\ \end{array}\right.$

Indeed, since $y_{S}$ and $y_{T}$ are binary variables, at least one of them
is $1$. Without loss of generality assume $y_{S}$ = 1. Then $x_{S}=0$ since
$x_{S}\in\mathbb{Z}_{\geq 0}$. Therefore two subsets that do not touch cannot
be both chosen in the embedding.

###  5.2 A Mixed Integer Linear Program for $\mathsf{emb}(\mathcal{H})$

The above ILP construction does not directly yield a way to compute the clique
embedding power, since the latter is defined to be the supremum for all $k$.
As alluded before, the behavior of $\mathsf{emb}_{k}(\mathcal{H})$ as a
function of $k$ is non-trivial (and certainly not monotone). Figure 3 in
Appendix B depicts how the clique embedding power changes with respect to
different clique sizes for the 6-cycle, where the horizontal line represents
the clique size.

To compute the supremum, the key idea is to change the integer variables
$x_{S}$ to be continuous (so they behave as fractions) and "normalize" the
clique size $k$ to 1. Specifically, we can write the following mixed integer
linear program (MILP).

$\begin{array}[]{llllllll}\displaystyle\min&\lx@intercol w\hfil\lx@intercol\\\
\textrm{s.t.}&&&\displaystyle\sum\limits_{S\subseteq V}x_{S}&=&1\\\
&&&x_{S}&=&0&\forall S\subseteq V&\textrm{ where }\textrm{$S$ is not
connected}\\\ &&&\min\\{x_{S},x_{T}\\}&=&0&\forall S,T\subseteq V&\textrm{
where $S,T$ do not touch}\\\ \displaystyle&&&\sum\limits_{S\subseteq V:e\cap
S\neq\emptyset}x_{S}&\leq&w&\forall e\in\mathcal{E}\\\
&&&x_{S}&\in&\mathbb{R}_{\geq 0}&\forall S\subseteq V\end{array}$ (2)

######  Proposition 5.1.

Let $w^{*}$ be the optimal solution of MILP (2). Then,
$\mathsf{emb}(\mathcal{H})=1/w^{*}$. Additionally, there exists an integer
$K\geq 3$ such that $\mathsf{emb}(\mathcal{H})=\mathsf{emb}_{K}(\mathcal{H})$.

######  Proof 5.2.

We first show for any $k$, $\mathsf{emb}_{k}(\mathcal{H})\geq 1/w^{*}$.
Indeed, any embedding $\psi:C_{k}\rightarrow\mathcal{H}$ determines the values
of the variables $x_{S}$ in MILP (1). Let $\hat{x_{S}}=\frac{x_{S}}{k}$ and
$\hat{w}=\frac{w}{k}$ be an assignment of the variables in MILP (2). It is
easy to see that this is a feasible assignment. Thus,
$w^{*}\leq\mathsf{wed}(C_{k}\mapsto\mathcal{H})/k$. Therefore
$\mathsf{emb}_{k}(\mathcal{H})=k/\mathsf{wed}(C_{k}\mapsto\mathcal{H})\leq
1/w^{*}$.

Next, observe that $\mathsf{emb}(\mathcal{H})$ is a rational number. In fact,
the solution $w^{*}$ for MILP (2) is a rational number, since every constant
is a rational number [22]. Let $K$ be the least common multiplier of their
denominators of the fractions in the set $\\{x_{S}\\}$. Then, the assignment
$K\cdot x_{S},K\cdot w$ is a feasible solution for MILP (1) for $k=K$. This
implies that $K\cdot w^{*}\geq\mathsf{wed}(C_{K}\mapsto\mathcal{H})$, so
$\mathsf{emb}_{K}(\mathcal{H})\geq 1/w^{*}$.

Thus, we have shown that $1/w^{*}$ is an upper bound for
$\\{\mathsf{emb}_{k}(\mathcal{H})\\}_{k}$, but also
$\mathsf{emb}_{K}(\mathcal{H})=1/w^{*}$. Hence,
$\mathsf{emb}(\mathcal{H})=\mathsf{emb}_{K}(\mathcal{H})=1/w^{*}$.

This leads to the following theorem (proof in Appendix B).

######  Theorem 5.3.

The problem of computing ${\mathsf{emb}}(\mathcal{H})$ for a hypergraph
$\mathcal{H}$ is in 2-$\mathsf{EXPTIME}$ and, in particular, is decidable.

Unfortunately, our method does not yield an upper bound on how large the $K$
in Proposition 5.1 might be. There is no reason that $K$ cannot be very large,
e.g. doubly exponential to the size of $\mathcal{H}$. Some knowledge of that
could be very useful in computing the clique embedding power. For example, one
can compute all the embeddings from $C_{k}$, for $k$ not greater than the
upper bound, and output the one with the largest embedding power. Currently
the best bound we have is the following (proof in Appendix B).

######  Proposition 5.4.

For any hypergraph $\mathcal{H}$, there is a constant $K=O((2^{|V|})!)$ such
that $\mathsf{emb}(\mathcal{H})=\mathsf{emb}_{K}(\mathcal{H})$.

##  6 Examples of Tightness

In this section, we identify several classes of queries where the clique
embedding power coincides with the submodular width. For brevity, we write
$\mathsf{emb}$, $\mathsf{subw}$, $\mathsf{fhw}$, and $\mathsf{adw}$ when the
underlying hypergraph is clear under context. Table 1 summarizes our results.

| $\mathsf{emb}$ |  | $\mathsf{subw}$ |
---|---|---|---|---
Acyclic | $1$ | [Theorem 6.13] | $1$ | [25]
Chordal | $=$ | [Theorem 6.9] | $=$ | [20]
$\ell$-cycle | $2-1/\lceil\ell/2\rceil$ | [6.2] | $2-1/\lceil\ell/2\rceil$ | [2]
$K_{2,\ell}$ | $2-1/\ell$ | [6.4] | $2-1/\ell$ | [15]
$K_{3,3}$ | $2$ | [6.5] | $2$ | [15]
$A_{\ell}$ | $(\ell-1)/2$ | [C.6] | $(\ell-1)/2$ | [20]
$\mathcal{H}_{\ell,k}$ | $\ell/k$ | [C.8] | $\ell/k$ | [20]
$Q_{b}$ | $17/9$ |  | $2$ | [12]
$Q_{hb}$ | $7/4$ |  | $2$ | [7.1]
Table 1: Summary of $\mathsf{emb}$ and $\mathsf{subw}$ for some classes of
queries

###  6.1 Cycles

For the cycle query of length $\ell\geq 3$, we show that
$\mathsf{emb}=\mathsf{subw}=2-1/\lceil\ell/2\rceil$. The best-known algorithm
for $\ell$-cycle detection (and counting) of Alon, Yuster, and Zwick [2] runs
in time $O(|I|^{\mathsf{subw}})$. First, we show the following lemma whose
proof is in Appendix C.1.

######  Lemma 6.1.

Consider the cycle query of length $\ell\geq 3$. Then $\mathsf{emb}\geq
2-1/{\lceil\frac{\ell}{2}\rceil}$.

######  Proposition 6.2.

Consider the cycle query of length $\ell\geq 3$. Then we have

$\mathsf{emb}=\mathsf{subw}=2-\frac{1}{\lceil\frac{\ell}{2}\rceil}$

######  Proof 6.3.

It can be shown using Example 7.4 in [15] (setting $m=1$) that
$\mathsf{subw}\leq 2-1/\lceil\frac{\ell}{2}\rceil$ (technically the Example
7.4 in [15] only deals with cycles of even length, but their argument can be
easily adapted to cycles of odd length). We thus conclude by applying 6.1 and
Theorem 3.6.

###  6.2 Complete Bipartite Graphs

We consider a complete bipartite graph $K_{m,n}$ where the two partitions of
its vertices are $\\{x_{1},\dots,x_{m}\\}$ and $\\{y_{1},\dots,y_{n}\\}$. We
study two of its special cases, $K_{2,\ell}$ and $K_{3,3}$, where both proofs
can be found in Appendix C.2.

######  Proposition 6.4.

For the bipartite graph $K_{2,\ell}$,
$\mathsf{emb}(K_{2,\ell})=\mathsf{subw}(K_{2,\ell})=2-1/\ell$.

######  Proposition 6.5.

For $K_{3,3}$, we have $\mathsf{emb}(K_{3,3})=\mathsf{subw}(K_{3,3})=2$.

Fnding $\mathsf{emb}(K_{m,n})$ and $\mathsf{subw}(K_{m,n})$ in the most
general case is still an open question.

###  6.3 Chordal Queries

In this section, we identify a special class of queries, called choral
queries. We introduce necessary definitions and lemmas to prove that for a
chordal query, $\mathsf{emb}$, $\mathsf{subw}$, $\mathsf{fhw}$, and
$\mathsf{adw}$ all coincide, as stated in Theorem 6.9.

Let $G$ be a graph. A chord of a cycle $C$ of $G$ is an edge that connects two
non-adjacent nodes in $C$. We say that $G$ is chordal if any cycle in $G$ of
length greater than 3 has a chord. We can extend chordality to hypergraphs by
considering the clique-graph of a hypergraph $\mathcal{H}$, where edges are
added between all pairs of vertices contained in the same hyperedge.

Let $(\mathcal{T},\chi)$ be a tree decomposition of a hypergraph $\mathcal{H}$
and
$\mathsf{bags}(\mathcal{T})\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\chi(t)\mid
t\in V(\mathcal{T})\\}$. We say that $(\mathcal{T},\chi)$ is proper if there
is no tree decomposition $(\mathcal{T}^{\prime},\chi^{\prime})$ such that

  1. 1.

for every bag $b_{1}\in\mathsf{bags}(\mathcal{T}^{\prime})$, there is a bag
$b_{2}\in\mathsf{bags}(\mathcal{T})$ such that $b_{1}\subseteq b_{2}$;

  2. 2.

$\mathsf{bags}(\mathcal{T}^{\prime})\nsupseteq\mathsf{bags}(\mathcal{T})$,

The following important properties hold for chordal graphs.

######  Lemma 6.6 ([5]).

If $G$ is a chordal graph and $(\mathcal{T},\chi)$ is a proper tree
decomposition of $G$, then the bags of $(\mathcal{T},\chi)$, i.e.
$\mathsf{bags}(\mathcal{T})$, are the maximal cliques in $G$.

For chordal hypergraphs, we can show the following (proof in Appendix C.3):

######  Lemma 6.7.

Let $\mathcal{H}$ be a hypergraph. Then, $(\mathcal{T},\chi)$ is a (proper)
tree decomposition of $\mathcal{H}$ if and only if it is a (proper) tree
decomposition of the clique-graph of $\mathcal{H}$.

The following corollary is immediate from both 6.6 and 6.7:

######  Corollary 6.8.

If $\mathcal{H}$ is a chordal hypergraph and $(\mathcal{T},\chi)$ is a proper
tree decomposition of $\mathcal{H}$, then the bags of $(\mathcal{T},\chi)$ are
the maximal cliques in the clique-graph of $\mathcal{H}$.

The above corollary tells us that every proper tree decomposition has the same
set of bags, with the only difference being the way the bags are connected in
the tree. From this, we can easily obtain that $\mathsf{subw}=\mathsf{fhw}$.
However, we have an even stronger result:

######  Theorem 6.9.

If $\mathcal{H}$ is a chordal hypergprah, then
$\mathsf{emb}=\mathsf{adw}=\mathsf{subw}=\mathsf{fhw}$.

######  Proof 6.10.

Since $\mathcal{H}$ is chordal, by 6.8, the bags of any proper tree
decomposition $(\mathcal{T},\chi)$ of $\mathcal{H}$ are the maximal cliques in
the clique-graph of $\mathcal{H}$. Then, there is a node $t\in V(\mathcal{T})$
such that the minimum fractional edge cover (also the maximum fractional
vertex packing) of $\chi(t)$ is $\mathsf{fhw}$. In particular, let
$\\{u_{i}\mid i\in\chi(t)\\}$ be the optimal weights assigned to each vertex
in $\chi(t)$ that obtain the maximum fractional vertex packing, so
$\sum_{i\in\chi(t)}u_{i}=\mathsf{fhw}$. We let
$\hat{u}_{i}=u_{i}/\sum_{i\in\chi(t)}u_{i}$ and $k$ be the smallest integer
such that $k\cdot\hat{u}_{i}$ is an integer for every $i\in\chi(t)$. Now we
construct an embedding $\psi$ from $C_{k}$ to $\mathcal{H}$ so that every
$\psi(j)$, for $j\in[k]$ is a singleton and for each $i\in\chi(t)$, let
$d_{\psi}^{-1}(i)\stackrel{{\scriptstyle\text{def}}}{{=}}k\cdot\hat{u}_{i}$.
This assignment uses up all $k$ vertices in $C_{k}$, since
$\sum_{i\in\chi(t)}k\cdot\hat{u}_{i}=k$. Then,

$\mathsf{wed}(\psi)=\max_{e\in E(\mathcal{H})}\sum_{i\in
e}k\cdot\hat{u}_{i}=\frac{k}{\sum_{i\in\chi(t)}u_{i}}\cdot\max_{e\in
E(\mathcal{H})}\sum_{i\in e}u_{i}\leq\frac{k}{\sum_{i\in\chi(t)}u_{i}}$

and thus, we get $\mathsf{emb}=\mathsf{fhw}$ since

$\mathsf{emb}\geq\mathsf{emb}(C_{k}\mapsto\mathcal{H})\geq\frac{k}{\mathsf{wed}(\psi)}\geq\sum_{i\in\chi(t)}u_{i}=\mathsf{fhw}.$

For $\mathsf{adw}$, we define the following modular function over subsets of
$V(\mathcal{H})$: for any $S\subseteq V(\mathcal{H})$, let
$\mu(S)\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{i\in S}u_{i}$. It is
edge-dominated since for every hyperedge $e$, $\mu(e)=\sum_{i\in e}u_{i}\leq
1$. Moreover, we have that
$\mu(\chi(t))=\sum_{i\in\chi(t)}u_{i}=\mathsf{fhw}$. That is,
$\mathsf{adw}\geq\mathsf{fhw}$, so $\mathsf{adw}=\mathsf{fhw}$. As a remark,
it is also viable to use Lemma 3.1 in [15] to prove the claim for adaptive
width.

Recall that Corollary 6.8 implies if $\mathcal{H}$ is chordal, then every
proper tree decomposition of $\mathcal{H}$ has the same set of bags. We show
the converse is also true, which could be of independent interest.

######  Lemma 6.11.

Let $\mathcal{H}$ be a hypergraph. If every proper tree decomposition of
$\mathcal{H}$ has the same set of bags, then $\mathcal{H}$ is chordal.

Next, we identify three classes of hypergraphs (almost-cliques, hypercliques,
and acyclic hypergraphs) that are chordal and find their clique embedding
powers and submodular widths. In particular, to keep this paragraph succinct,
we defer the discussion of almost-cliques and hypercliques to Appendix C.3.1
and Appendix C.3.2, respectively.

##### Acyclic Queries

First, we claim that acyclic queries are indeed chordal queries. This claim is
proved in Appendix C.3.3.

######  Lemma 6.12.

An acyclic hypergraph $\mathcal{H}$ is chordal.

Now we prove the following theorem for acyclic hypergprahs:

######  Theorem 6.13.

For an acyclic hypergprah $\mathcal{H}$,
$\mathsf{emb}=\mathsf{adw}=\mathsf{subw}=\mathsf{fhw}=1$.

######  Proof 6.14.

From 3.3, we know that $\mathsf{emb}\geq 1$. Since it is known that
$\mathsf{subw}=\mathsf{fhw}=1$, the theorem is then a direct result from 6.12
and Theorem 6.9.

##  7 Gap Between Clique Embedding Power and Submodular Width

In this section, we discuss the boat query and its variant depicted in Figure
1, where gaps between the clique embedding power and submodular width can be
shown.

$x_{1}$$x_{4}$$x_{5}$$x_{8}$$x_{2}$$x_{3}$$x_{6}$$x_{7}$ (a) Boat Query
$Q_{b}$

$y_{1}$$y_{2}$$y_{3}$$z_{1}$$z_{2}$$z_{3}$ (b) Hyper-boat Query $Q_{hb}$

Figure 1: The Boat query and its variant, the Hyper-boat Query

###  7.1 Clique Embedding Power, Submodular Width and Adaptive Width

1,6-11,165-113-52-4,12-171,2,6-81,2,12-159-11,16-1712-17 (a) $\mathsf{emb}$
for $Q_{b}$

1-32,31,475,64-6 (b) $\mathsf{emb}$ for $Q_{hb}$

Figure 2: Optimal embedding for the boat query and its variants

Using MILP (2), we find the optimal clique embedding for $Q_{b}$ and $Q_{hb}$,
as illustrated in Figure 2. The numbers represent the vertices from the
clique, and we adopt the shorthand notation, say, 6-8 to refer to the set
{6,7,8}. The clique embedding powers for $Q_{b}$ and $Q_{hb}$ are
$\frac{17}{9}$ and $\frac{7}{4}$, respectively. However, [12] proves that for
the boat query, $\mathsf{subw}(Q_{b})=2$. This implies a gap since
$\mathsf{emb}(Q_{b})=17/9<\mathsf{subw}(Q_{b})=2$. We show that for the hyper-
boat query $Q_{hb}$, there is also a gap between the optimal clique embedding
power and submodular width. In particular, we show that
$\mathsf{subw}(Q_{hb})=2$ in the following proposition, which implies the
following gap: $\mathsf{emb}(Q_{hb})=\frac{7}{4}<\mathsf{subw}(Q_{hb})=2$. Its
proof can be found in Appendix D.

######  Proposition 7.1.

For $Q_{hb}$, we have $\mathsf{subw}(Q_{hb})=2$.

###  7.2 Subquadratic Equivalence Between Boat Queries

In this section, we demonstrate an interesting connection between the two boat
queries. To start, let’s consider $Q_{b}$ and $Q_{hb}$. Both queries admit an
algorithm that runs in time $O(|I|^{2})$. Informally, we are going to show
that either both queries can be executed significantly faster, or neither can.
Following the seminal paper by Williams and Williams [23], we define truly
subquadratic algorithm and subquadratic equivalence.

######  Definition 7.2.

An algorithm is said to be _truly subquadratic_ if it runs in time
$O(m^{2-\epsilon})$ for some $\epsilon>0$ ($m$ is the input size).

Two problems $A$ and $B$ are _subquadratic equivalent_ if $A$ admits a truly
subquadratic algorithm iff $B$ admits a truly subquadratic algorithm. We show
that the two boat queries are subquadratic equivalent. We defer the proof of
the following theorem to Appendix D.

######  Theorem 7.3.

$Q_{b}$ is subquadratic equivalent to $Q_{hb}$.

We remark that the reduction from $Q_{hb}$ to $Q_{b}$ is parametrized by the
running time of the algorithm for $Q_{hb}$. That is, the reduction is not
uniform in the sense that only after given $\delta>0$ can we specify a
suitable $\epsilon$. Theorem 7.3 implies that either both boat queries admit a
truly subquadratic algorithm, or none of them does.

The fact that there is a gap between $\mathsf{subw}(Q_{hb})=2$ and
$\mathsf{emb}(Q_{hb})=\frac{7}{4}$ suggests currently our lower bound does not
match with the best upper bound, i.e., $\mathsf{PANDA}$. This implies either
that $\mathsf{PANDA}$ is not universally optimal, or that we are missing the
best lower bound. We leave this as an open question.

Finally, we note that Theorem 4 in [12], which proves there does not exist a
$\tilde{O}(m^{2-\epsilon}+|\text{OUT}|)$555$|\text{OUT}|$ is the size of the
output. algorithm for the boat query unless 3-XOR can be solved in time
$\tilde{O}(m^{2-t})$ for a $t>0$, does not directly translate into the
quadratic hardness for the boat query in our case. This is because their
reduction uses the output of the boat query in an essential way to “hack back
the collision” which is not available in the Boolean case.

##  8 Related Work

##### Fine-Grained Complexity

The study of fine-grained complexity aims to show (conditional) hardness of
easy problems. Recent years have witnessed a bloom of development into this
fascinating subject, resulting in many tight lower bounds which match exactly,
or up to poly log factors, the running time of best-known algorithms [16, 24,
23, 1]. Among many others, popular hardness assumptions include the Strong
Exponential Time Hypothesis (SETH), Boolean Matrix Multiplication (BMM), and
All-Pairs Shortest Paths (APSP). Our work can be seen as a particular instance
under this framework, i.e. using Boolean or Min-Weight $k$-Clique Conjecture
to show conditional lower bounds for BCQs. Interestingly, our reduction of
$k$-cycles essentially mirrors the construction in the proof of Theorem 3.1 in
[16].

##### Functional Aggregate Queries (FAQ)

FAQ [14] provides a Sum-of-Product framework to define the semantics of
conjunctive queries over arbitrary semirings. The semiring point-of-view
originated from the seminal paper [9]. We show that the embedding from a
$k$-clique into a hypergraph holds for arbitrary semirings, which enables one
to transfer the hardness of $k$-clique to FAQ independent of the underlying
semiring. To the best of our knowledge, this is the first _semiring-oblivious_
reduction.

##### Enumeration and Preprocessing

[3] characterized for which self-join-free conjunctive queries a linear or
constant delay and linear preprocessing algorithm is possible. A recent paper
[6] makes an initial foray towards the characterization of conjunctive queries
with self-joins. Also recently, [4] identifies new queries which can be solved
with linear preprocessing time and constant delay. Their fine-grained hardness
results are based on the Hyperclique conjecture, the Boolean Matrix
Multiplication conjecture, and the 3SUM conjecture.

##  9 Conclusion

In this paper, we study the fine-grained complexity of BCQs. We give a
semiring-oblivious reduction from the $k$-clique problem to an arbitrary
hypergraph. Assuming the Boolean $k$-Clique Conjecture, we obtain conditional
lower bounds for many queries that match the combinatorial upper bound
achieved by the best-known algorithms, possibly up to a poly-logarithmic
factor.

One attractive future direction is to fully unravel the gap between the clique
embedding power and submodular width, where improved lower bounds or upper
bounds are possible. The Boolean $k$-Clique Conjecture states that there is no
$O(n^{k-\epsilon})$ _combinatorial_ algorithm for detecting $k$-cliques. One
future direction is to base the hardness assumption over Nešetřil and Poljak’s
algorithm [19], which solves the $k$-clique problem in
$O\left(n^{(\omega/3)k}\right)$ by leveraging fast matrix multiplication and
show lower bounds for any algorithm.

## References

  * [1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams.  If the current clique algorithms are optimal, so is Valiant’s parser.  In FOCS, pages 98–117. IEEE Computer Society, 2015.
  * [2] Noga Alon, Raphael Yuster, and Uri Zwick.  Finding and counting given length cycles.  Algorithmica, 17(3):209–223, 1997.
  * [3] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In CSL, volume 4646 of Lecture Notes in Computer Science, pages 208–222. Springer, 2007.
  * [4] Karl Bringmann and Nofar Carmeli.  Unbalanced triangle detection and enumeration hardness for unions of conjunctive queries.  CoRR, abs/2210.11996, 2022.
  * [5] Nofar Carmeli, Batya Kenig, Benny Kimelfeld, and Markus Kröll.  Efficiently enumerating minimal triangulations.  Discret. Appl. Math., 303:216–236, 2021.
  * [6] Nofar Carmeli and Luc Segoufin.  Conjunctive queries with self-joins, towards a fine-grained complexity analysis.  CoRR, abs/2206.04988, 2022.
  * [7] Katrin Casel and Markus L. Schmid.  Fine-grained complexity of regular path queries.  In ICDT, volume 186 of LIPIcs, pages 19:1–19:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [8] Arnaud Durand.  Fine-grained complexity analysis of queries: From decision to counting and enumeration.  In PODS, pages 331–346. ACM, 2020.
  * [9] Todd J. Green, Gregory Karvounarakis, and Val Tannen.  Provenance semirings.  In PODS, pages 31–40. ACM, 2007.
  * [10] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  Journal of the ACM (JACM), 54(1):1–24, 2007.
  * [11] Pinar Heggernes.  Treewidth, partial $k$-trees, and chordal graphs.  Partial curriculum in INF334-Advanced algorithmical techniques, Department of Informatics, University of Bergen, Norway, 2005.
  * [12] Manas Joglekar and Christopher Ré.  It’s all a matter of degree - using degree information to optimize multiway joins.  Theory Comput. Syst., 62(4):810–853, 2018.
  * [13] Mahmoud Abo Khamis, Ryan R. Curtin, Benjamin Moseley, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich.  On functional aggregate queries with additive inequalities.  In PODS, pages 414–431. ACM, 2019.
  * [14] Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra.  FAQ: questions asked frequently.  In PODS, pages 13–28. ACM, 2016.
  * [15] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu.  What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?  In PODS, pages 429–444. ACM, 2017.
  * [16] Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams.  Tight hardness for shortest cycles and paths in sparse graphs.  In SODA, pages 1236–1252. SIAM, 2018.
  * [17] Dániel Marx.  Can you beat treewidth?  Theory Comput., 6(1):85–112, 2010.
  * [18] Dániel Marx.  Tractable hypergraph properties for constraint satisfaction and conjunctive queries.  J. ACM, 60(6):42:1–42:51, 2013.
  * [19] Jaroslav Nešetřil and Svatopluk Poljak.  On the complexity of the subgraph problem.  Commentationes Mathematicae Universitatis Carolinae, 26(2):415–419, 1985.
  * [20] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra.  Worst-case optimal join algorithms.  J. ACM, 65(3):16:1–16:40, 2018.
  * [21] Donald J. Rose, Robert Endre Tarjan, and George S. Lueker.  Algorithmic aspects of vertex elimination on graphs.  SIAM J. Comput., 5(2):266–283, 1976.
  * [22] Alexander Schrijver.  Theory of linear and integer programming.  Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
  * [23] Virginia Vassilevska Williams and R. Ryan Williams.  Subcubic equivalences between path, matrix, and triangle problems.  J. ACM, 65(5):27:1–27:38, 2018.
  * [24] Virginia Vassilevska Williams and Yinzhan Xu.  Monochromatic triangles, triangle listing and APSP.  In FOCS, pages 786–797. IEEE, 2020.
  * [25] Mihalis Yannakakis.  Algorithms for acyclic database schemes.  In VLDB, pages 82–94. IEEE Computer Society, 1981.

##  Appendix A Missing Details from section 3

######  Proof A.1 (Proof of Proposition 3.3).

(1) We define an embedding $\psi$ from a $k$-clique where
$\psi(i)=V(\mathcal{H})$ for every $i=1,\dots,k$. It is easy to see that
$\psi$ is an embedding with weak edge depth $k$.

(2) For the first inequality, take any $\psi_{k+1}$, we can construct a
$\psi_{k}$ by only preserving the mapping $\psi_{k+1}$ for $[k]$. Then, for
any $e\in E(\mathcal{H})$, we have

$\\{y\in V(C_{k})\mid\psi_{k}(y)\cap e\neq\emptyset\\}\subseteq\\{y\in
V(C_{k+1})\mid\psi_{k+1}(y)\cap e\neq\emptyset\\}$

Thus,

$\mathsf{wed}(C_{k}\mapsto\mathcal{H})\leq\mathsf{wed}(\psi_{k}):=\max_{e\in
E(\mathcal{H})}d_{\psi_{k}}(e)\leq\mathsf{wed}(\psi_{k+1}).$

For the second inequality, take any $\psi_{k}$, we construct a $\psi_{k+1}$ by
preserving the mapping $\psi_{k}$ and $\psi_{k+1}$ maps $k+1$ to
$V(\mathcal{H})$. Then, for any $e\in E(\mathcal{H})$, we have

$d_{\psi_{k+1}}(e)=d_{\psi_{k}}(e)+1$

so

$\mathsf{wed}(\psi_{k+1})=\mathsf{wed}(\psi_{k})+1$

in particular, we can take $\psi_{k}$ such that

$\mathsf{wed}(\psi_{k+1})\leq\mathsf{wed}(C_{k}\mapsto\mathcal{H})+1$

which implies that

$\mathsf{wed}(C_{k+1}\mapsto\mathcal{H})\leq\mathsf{wed}(C_{k}\mapsto\mathcal{H})+1$

(3) Suppose $\psi$ is the embedding that achieves
$\mathsf{emb}_{m}(\mathcal{H})$ for $C_{m}$. It suffices to construct an
embedding $\psi^{\prime}$ for $C_{k}$ which achieves the same quantity
$\mathsf{emb}_{m}(\mathcal{H})$. To do so, we simply bundle every $n$ vertices
in $C_{k}$ to be a “hypernode”. That is, label the bundles as
$b_{1},\dots,b_{n}$. and $\psi^{\prime}(v)=\psi(i)$ if and only if $v\in
B_{i}$. The embedding power given by $\psi^{\prime}$ is then

$\frac{k}{\mathsf{wed}(\psi^{\prime})}=\frac{mn}{\mathsf{wed}(\psi)n}=\frac{m}{\mathsf{wed}(\psi)}=\mathsf{emb}_{m}(\mathcal{H}).$

######  Theorem A.2.

For any hypergraph $\mathcal{H}$, the following holds:

$\mathsf{ed}(C_{k}\mapsto\mathcal{H})\geq\frac{k}{\mathsf{adw}(\mathcal{H})}$

######  Proof A.3.

Let $\mathsf{ed}(C_{k}\mapsto\mathcal{H})=\alpha$. Then, there is an embedding
$\psi:C_{k}\mapsto\mathcal{H}$ with edge depth $\alpha$. We will show that
$\mathsf{adw}(\mathcal{H})\geq k/\alpha$.

First, we define the following function over subsets of $V(\mathcal{H})$: for
any $S\subseteq V(\mathcal{H})$, let $\mu(S)=\sum_{v\in S}d_{\psi}(v)/\alpha$.
This function forms a fractional independent set, since for any hyperedge $e$,
we have $\mu(e)=\sum_{v\in e}d_{\psi}(v)/\alpha=d^{+}_{\psi}(e)/\alpha\leq 1$.

Now, consider any decomposition $(\mathcal{T},\chi)$ of $\mathcal{H}$. From
Lemma 3.4, there is a node $t\in T$ such that or every $i=1,\dots,k$,
$\psi(i)\cap\chi(t)\neq\emptyset$. Hence, $\mu(B_{t})=\sum_{v\in
B_{t}}d_{\psi}(v)/\alpha\geq k/\alpha$. Thus, the adaptive width of the
decomposition is at least $k/\alpha$.

##  Appendix B Missing Details from section 5

Figure 3: $\mathsf{emb}_{k}(\mathcal{H})$ for the 6-cycle

######  Proof B.1 (Proof of Theorem 5.3).

Proposition 5.1 shows that to compute ${\mathsf{emb}}(\mathcal{H})$ it
suffices to solve MILP (2). To solve the MILP, we can sequentially fix the
assignments of the binary variables $y_{S}$ and then solve a linear program.
Note that the remaining linear program might have exponentially many
conditions in the size of $\mathcal{H}$, since the number of variables is
$2^{|V|}$. The proof is then complete by observing the number of assignments
of $y_{S}$ are doubly exponential in $\mathcal{H}$.

######  Proof B.2 (Proof of 5.4).

We simply find an upper bound for the least common multiplier $K$ such that
$K\cdot x_{S}$ are integers ($x_{S}$ are the variables in MILP (2)). Following
the backward direction of the previous proof, we know that for this $K$, we
have $\mathsf{emb}_{K}(\mathcal{H})=\mathsf{emb}(\mathcal{H})$. The MILP has
$O(2^{|V|})$ constraints where all coefficients are in $\\{1,0,-1\\}$. By
Cramer’s rule, a common denominator $K$ of all $x_{i}$ is (the absolute value
of) the determinant of an $O(2^{|V|})\times O(2^{|V|})$ matrix whose entries
are all in $\\{1,0,-1\\}$. Thus, $K=O((2^{|V|})!)$.

##  Appendix C Missing Details from section 6

###  C.1 Cycles

######  Proof C.1 (Proof of 6.1).

We start with the case where $\ell$ is odd and name the variables of the cycle
query as $x_{1},\dots,x_{\ell}$. Then, we define $\lambda=(\ell+1)/2$ and an
embedding from a $\ell$-clique as follows:

$\displaystyle\psi^{-1}(x_{1})$ $\displaystyle=\\{1,2,\dots,\lambda-1\\}$ (3)
$\displaystyle\psi^{-1}(x_{2})$ $\displaystyle=\\{2,3,\dots,\lambda\\}$
$\displaystyle\dots$ $\displaystyle\psi^{-1}(x_{\ell})$
$\displaystyle=\\{2\lambda-1,1,\dots,\lambda-2\\}$

In other words, $\psi$ maps each $i\in[\ell]$ into a consecutive segment
consisting of $\lambda-1$ vertices in the cycle. To see why $\psi$ is an
embedding, we observe that for any $i,j\in[\ell]$ such that
$\psi(i)\cap\psi(j)=\emptyset$, $|\psi(i)\cup\psi(j)|=2\lambda-2=\ell-1$, so
there is an edge that intersects both $\psi(i)$ and $\psi(j)$. It is easy to
see that $\mathsf{wed}(\psi)=\lambda=(\ell+1)/2$. Thus,
$\mathsf{emb}\geq\ell/\lambda=2\ell/(\ell+1)=2-2/(\ell+1)$.

If $\ell$ is even, we define $\lambda=\ell/2$ and an embedding from a
$(\ell-1)$-clique as follows:

$\displaystyle\psi^{-1}(x_{1})$ $\displaystyle=\\{1,2,\dots,\lambda-1\\}$
$\displaystyle\psi^{-1}(x_{2})$ $\displaystyle=\\{2,3,\dots,\lambda\\}$
$\displaystyle\dots$ $\displaystyle\psi^{-1}(x_{\ell-1})$
$\displaystyle=\\{2\lambda-2,2\lambda-1,1,\dots,\lambda-3\\}$
$\displaystyle\psi^{-1}(x_{\ell})$ $\displaystyle=\psi^{-1}(x_{\ell-1})$

where $\psi^{-1}(x_{i}),i\in[\ell-1]$ is exactly the embedding we constructed
for $(\ell-1)$-cycle. We show that this is a valid embedding. Let
$i,j\in[\ell]$ such that $\psi(i)\cap\psi(j)=\emptyset$.

  1. 1.

If $i\in\psi^{-1}(x_{\ell-1})$ (or $j\in\psi^{-1}(x_{\ell-1})$), then
$|\psi(i)\cup\psi(j)|=\ell-1$, so there is an edge that intersects both
$\psi(i)$ and $\psi(j)$.

  2. 2.

If $i,j\notin\psi^{-1}(x_{\ell-1})$, then $\psi(i)$ and $\psi(j)$ do not
contain $x_{\ell-1}$ and $x_{\ell}$. There is an edge that intersects both
$\psi(i)$ and $\psi(j)$ since $|\psi(i)\cup\psi(j)|=\ell-2$.

For this embedding, we have $\mathsf{wed}(\psi)=\lambda=\ell/2$, so
$\mathsf{emb}\geq(\ell-1)/\lambda=2-2/\ell$.

###  C.2 Complete Bipartite Graphs

######  Proof C.2 (Proof of 6.4).

We define the embedding $\psi$ from a $(2\ell-1)$-clique as follows:
$\psi^{-1}(x_{1})=\\{1,\dots,\ell-1\\}$,
$\psi^{-1}(x_{2})=\\{\ell,\dots,2\ell-2\\}$, and
$\psi^{-1}(y_{i})=\\{i,\ell+i-1\\}$ for $1\leq i\leq\ell-1$, while
$\psi^{-1}(y_{\ell})=\\{2\ell-1\\}$. To show that $\psi$ is an embedding, we
observe that $\psi(2\ell-1)=\\{y_{\ell}\\}$ and for each $i\in[2\ell-2]$,
$\psi(i)$ contains exactly two vertices, one from $\\{x_{1},x_{2}\\}$ and the
other from $\\{y_{1},\dots,y_{n}\\}$, so $\psi(i)$ induces an edge as a
subgraph. Thus, for any $i,j\in[2\ell-1]$, $\psi(i)$ and $\psi(j)$ touch
because there is an edge $(u,v)$, where
$u\in\psi(i)\cap\\{x_{1},x_{2}\\},v\in\psi(j)\cap\\{y_{1},\dots,y_{n}\\}$,
that intersects both $\psi(i)$ and $\psi(j)$. It is easy to see that
$\mathsf{wed}(\psi)=\ell$, thus $\mathsf{emb}_{2\ell-1}\geq 2-1/\ell$.

Next, we show that $\mathsf{subw}(K_{2,\ell})\leq 2-1/\ell$. There are only
two proper tree decompositions for $K_{2,\ell}$, where the first one has
$\ell$ bags $\\{x_{1},x_{2},y_{1}\\},\dots,\\{x_{1},x_{2},y_{\ell}\\}$ and the
second one has two bags
$\\{x_{1},y_{1},\dots,y_{\ell}\\},\\{x_{2},y_{1},\dots,y_{\ell}\\}$. Let $h$
be any edge-dominated submodular function.

  1. (1)

$h(x_{i})\leq\theta$ for some $i\in\\{1,2\\}$. WLOG we assume
$h(\\{x_{1}\\})\leq\theta$. Then, for any bag in the first decomposition,
i.e., $\\{x_{1},x_{2},y_{i}\\}$, $i\in[\ell]$, we have

$h(\\{x_{1},x_{2},y_{i}\\})\leq
h(\\{x_{1}\\})+h(\\{x_{2},y_{i}\\})\leq\theta+1$

  2. (2)

$h(x_{i})>\theta$ for any $i\in\\{1,2\\}$. Then, for any of the two bags in
the second decomposition, say $\\{x_{1},y_{1},\ldots,y_{\ell}\\}$, we have

$\displaystyle h(\\{x_{1},y_{1},\ldots,y_{\ell}\\})$ $\displaystyle\leq
h(\\{x_{1},y_{1}\\})+h(\\{x_{1},y_{2},\ldots,y_{\ell}\\})-h(\\{x_{1}\\})$
$\displaystyle\leq
h(\\{x_{1},y_{1}\\})+h(\\{x_{1},y_{2}\\})+h(\\{x_{1},y_{3},\ldots,y_{\ell}\\})-2h(\\{x_{1}\\})$
$\displaystyle\cdots$
$\displaystyle\leq\sum_{i=1}^{\ell-1}h(\\{x_{1},y_{i}\\})-(\ell-1)h(\\{x_{1}\\})$
$\displaystyle\leq\ell-(\ell-1)\theta$

Setting $\theta=1-1/\ell$, we conclude that $\mathsf{subw}(K_{2,\ell})\leq
2-1/\ell$. Therefore, $\mathsf{emb}_{2\ell-1}=\mathsf{subw}=2-1/\ell$ by
Theorem 3.6.

######  Proof C.3 (Proof of 6.5).

We first show that $\mathsf{emb}(K_{3,3})\geq 2$ by constructing an embedding
$\psi$ from a $8$-clique to $K_{3,3}$, where $\psi$ is defined as follows:

$\displaystyle\psi^{-1}(x_{1})=\\{1,3,5\\},\quad\psi^{-1}(x_{2})=\\{2,4,6\\},\quad\psi^{-1}(x_{3})=\\{7,8\\}$
$\displaystyle\psi^{-1}(y_{1})=\\{1,2\\},\quad\quad\psi^{-1}(y_{2})=\\{3,4\\},\quad\quad\psi^{-1}(y_{3})=\\{5,6\\}$

Therefore, $\mathsf{emb}\geq 8/\mathsf{wed}(\psi)=8/4=2$.

Next, we show that $\mathsf{subw}(K_{3,3})\leq 2$. We take two tree
decompositions, where the first decomposition has bags
$\\{x_{1},x_{2},x_{3},y_{i}\\}$, where $i\in[3]$ and the second decomposition
has bags $\\{y_{1},y_{2},y_{3},x_{i}\\}$, where $i\in[3]$. For an arbitrary
edge-dominated $h\in\Gamma_{3}$, we assume WLOG in each decomposition, the
maximum value of $h$ is attained when $i=1$. We observe that

$\displaystyle h(\\{x_{1},x_{2},x_{3},y_{1}\\})$ $\displaystyle\leq
h(\\{x_{3},y_{1}\\})+h(\\{x_{1},x_{2},y_{1}\\})-h(\\{y_{1}\\})\leq
1+h(\\{x_{1},x_{2},y_{1}\\})-h(\\{y_{1}\\})$ $\displaystyle
h(\\{y_{1},y_{2},y_{3},x_{1}\\})$ $\displaystyle\leq
h(\\{y_{3},x_{1}\\})+h(\\{y_{1},y_{2},x_{1}\\})-h(\\{x_{1}\\})\leq
1+h(\\{y_{1},y_{2},x_{1}\\})-h(\\{x_{1}\\})$

Taking the sum of the above two inequalities, we get

$\displaystyle
h(\\{x_{1},x_{2},x_{3},y_{1}\\})+h(\\{y_{1},y_{2},y_{3},x_{1}\\})$
$\displaystyle\leq
2+h(\\{x_{1},x_{2},y_{1}\\})-h(\\{x_{1}\\})+h(\\{y_{1},y_{2},x_{1}\\})-h(\\{y_{1}\\})$
$\displaystyle\leq 2+h(\\{x_{2},y_{1}\\})+h(\\{y_{2},x_{1}\\})$
$\displaystyle\leq 4$

Then, it holds that
$\mathsf{subw}(K_{3,3})\leq\min\\{h(\\{x_{1},x_{2},x_{3},y_{1}\\}),h(\\{x_{1},x_{2},x_{3},y_{1}\\})\\}\leq
2$. We close the proof by applying Theorem 3.6.

###  C.3 Chordal Queries

######  Proof C.4 (Proof of 6.7).

We first show that $(\mathcal{T},\chi)$ is a tree decomposition of
$\mathcal{H}$ if and only if it is also a tree decomposition of the clique-
graph of $\mathcal{H}$. The forward direction is straightforward. For the
backward direction, let $(\mathcal{T},\chi)$ be a decomposition of the clique-
graph of $\mathcal{H}$. Then for any hyperedge $e\in\mathcal{H}$ and any pair
of vertices $u,v\in e$, we know that $\\{t\mid u\in\chi(t)\\}\cap\\{t\mid
v\in\chi(t)\\}\neq\emptyset$. By the Helly Property, there is a bag that
contains all vertices in the hyperedge $e$. Therefore, $(\mathcal{T},\chi)$ is
a tree decomposition for $\mathcal{H}$. It is easy to extend the proof for
proper tree decompositions.

######  Proof C.5 (Proof of 6.11).

Let $G$ be the clique-graph of $\mathcal{H}$. Lemma 5.4 in [5] states that
there is a one-to-one correspondence between the set of bags in a proper tree
decomposition (of $G$) and the set of possible minimal triangulations of $G$.
Thus, we proceed to prove the following claim: if a graph $G$ has only one
minimal triangulation, then $G$ is chordal and so is $\mathcal{H}$.

We show the contrapositive of the claim. Suppose the graph $G=(V,E)$ is not a
chordal graph, then it has at least one minimal triangulation. We take one
fill edge in this minimal triangulation, called $e$, and show that we can
construct another minimal triangulation without taking $e$ as a fill edge.
Indeed, we can start from a $|V|$-clique and remove $e$ from it. The resulting
graph is called an almost-clique and shown to be chordal in Appendix C. Since
$e\notin E$, this almost-clique is a triangulation of the original graph $G$
and we can keep removing fill edges from this triangulation till it becomes a
minimal triangulation of $G$ without $e$. This process shows that there are at
least two distinct minimal triangulations of $G$. This finishes the proof.

####  C.3.1 Almost-cliques

Consider the $\ell$-clique where one vertex, say $x_{1}$, connects to $k$
vertices only, where $1\leq k<\ell-1$ (hence it is the missing edges from
being a $\ell$-clique). We denote such a hypergraph as $A_{\ell}$. To show
that $A_{\ell}$ is chordal, we observe that for any cycle of length $\geq 4$
that contains $x_{1}$, the two adjacent vertices of $x_{1}$ in the cycle must
be connected by an edge in $A_{\ell}$ and that edge is a chord to the given
cycle. Furthermore, we show the following proposition.

######  Proposition C.6.

For an almost-cliques $A_{\ell}$,
$\mathsf{emb}=\mathsf{subw}=\mathsf{fhw}=(\ell-1)/2$.

######  Proof C.7.

To prove the claim, suppose WLOG $x_{i}$ connects only to $x_{i}$, where $i\in
2,3,\ldots,k$. Then, we take the decomposition with two bags:
$\\{x_{1},x_{2},\dots,x_{k}\\}$, $\\{x_{2},x_{3},\dots,x_{\ell}\\}$, where
each bag has an edge cover of at most $(\ell-1)/2$ since the first bag induces
an $k$-clique and the second bag induces an $(\ell-1)$-clique. Hence,
$\mathsf{fhw}\leq(\ell-1)/2$.

On the other hand, consider the embedding $\psi$ from the $(\ell-1)$-clique,
where $\psi(i)=x_{i+1}$, $1\leq i\leq\ell-1$; it is easy to verify that this
is a valid embedding such that $\mathsf{wed}(\psi)=2$, hence
$\mathsf{emb}\geq(\ell-1)/2$. Therefore, we have shown that
$\mathsf{emb}=\mathsf{subw}=(\ell-1)/2$ by Theorem 3.6.

####  C.3.2 Hypercliques

Next, we consider the $(\ell,k)$-hyperclique query $\mathcal{H}_{\ell,k}$,
where $1<k\leq\ell$. This query has $\ell$ variables, and includes as atoms
all possible subsets of $\\{x_{1},\dots,x_{\ell}\\}$ of size exactly $k$. When
$k=\ell-1$, the query simply becomes a Loomis-Whitney join [20]. It is easy to
see that $\mathcal{H}_{\ell,k}$ is chordal since the clique-graph of
$\mathcal{H}_{\ell,k}$ is a $\ell$-clique.

######  Proposition C.8.

For $\mathcal{H}_{\ell,k}$, we have
$\mathsf{emb}=\mathsf{subw}=\mathsf{fhw}=\ell/k$.

######  Proof C.9.

First, we show that $\mathsf{fhw}\leq\ell/k$. Indeed, there is a fractional
edge cover that assigns a weight of $1/k$ to each hyperedge that contains $k$
consecutive vertices in $\\{x_{1},\dots,x_{\ell}\\}$ (let the successor of
$x_{\ell}$ be $x_{1}$). The fractional edge cover is then $\ell/k$. We show
next that this bound coincides with $\mathsf{emb}$.

We simply define the embedding $\psi$ from a $\ell$-clique as
$\psi(i)=x_{i},i\in[\ell]$. Then, $\mathsf{wed}(\psi)=k$ since every hyperedge
has exactly $k$ vertices. Therefore, $\mathsf{emb}\geq\ell/k\geq\mathsf{fhw}$
and we conclude by applying 6.1 and Theorem 3.6.

####  C.3.3 Acyclic Queries

######  Proof C.10 (Proof of 6.12).

We prove by induction on the number of hyperedges in the hypergraph
$\mathcal{H}=(V,E)$. If $|E|=1$, it is clique-graph is a clique, thus it is
chordal. The induction hypothesis assumes the claim for acyclic hypergraphs
with $|E|\leq k$ hyperedges. Let $\mathcal{H}$ be an acyclic hypergraph such
that $|E|=k+1$. Since $\mathcal{H}$ is acyclic, it has a join forest whose
vertices are the hyperedges of $\mathcal{H}$. Let $e_{\ell}\in E$ be a leaf of
the join forest and it is easy to show that
$\mathcal{H}^{\prime}=(V,E\setminus\\{e_{\ell}\\})$ is an acyclic hypergraph
with $k$ hyperedges. For any cycle in the clique-graph of $\mathcal{H}$ having
length $\geq 4$, we discuss the following two cases.

If every edge of the cycle is in the clique-graph of $\mathcal{H}^{\prime}$:
by the induction hypothesis, there is a chord for this cycle in the clique-
graph of $\mathcal{H}^{\prime}$ (thus also in $\mathcal{H}$).

Otherwise, there is an edge $e$ in the cycle that is in the clique-graph of
$\mathcal{H}$, but not in the clique-graph of $\mathcal{H}^{\prime}$:
therefore, the edge $e$ is only contained by $e_{\ell}$. This implies that
there is a vertex $u$ that is only contained by $e_{\ell}$, not by any other
edges in $E$. Let $\\{u,v\\}$ and $\\{u,w\\}$ be the edges connecting $u$ in
the given cycle, we know that $\\{u,v,w\\}\subseteq e_{\ell}$ and thus,
$\\{v,w\\}$ is a chord for the given cycle.

##  Appendix D Missing Details from section 7

Before proving 7.1, we show the following helper lemma.

######  Lemma D.1.

Any proper tree decomposition of $Q_{hb}$ contains a bag that has at least $4$
vertices, two from $\\{y_{1},y_{2},y_{3}\\}$, two from
$\\{z_{1},z_{2},z_{3}\\}$.

######  Proof D.2.

Take any proper tree decomposition of $Q_{hb}$. By 6.11, it is also a proper
tree decomposition of the clique-graph of $Q_{hb}$. Lemma 5.4 in [5] states
that there is a one-to-one correspondence between the set of bags in a proper
tree decomposition and the set of possible minimal triangulations of $G$ and
furthermore, following 6.6, the set of bags in the proper tree decomposition
is exactly the set of maximal cliques after a minimal triangulation.
Therefore, we only need to show the following statement: for any minimal
triangulation of the clique-graph of $Q_{hb}$, there is a $4$-clique that
contains at least $4$ vertices, two from $\\{y_{1},y_{2},y_{3}\\}$, two from
$\\{z_{1},z_{2},z_{3}\\}$.

Let us, WLOG, fill $\\{y_{2},z_{3}\\}$ as a chord for the $4$-cycle
$(y_{2},y_{3},z_{3},z_{2})$. For the $4$-cycle $(y_{1},y_{2},z_{2},z_{1})$,
there are two cases:

  1. 1.

fill $\\{y_{2},z_{1}\\}$ as a chord for the $4$-cycle
$(y_{1},y_{2},z_{2},z_{1})$: now for the $4$-cycle
$(y_{1},y_{3},z_{3},z_{1})$, assume WLOG the chord $\\{y_{1},z_{3}\\}$ is
filled. This implied that $\\{y_{1},y_{2},z_{1},z_{3}\\}$ forms a $4$-clique
after this minimal triangluation.

  2. 2.

fill $\\{y_{1},z_{2}\\}$ as a chord for the $4$-cycle
$(y_{1},y_{2},z_{2},z_{1})$: in this case, consider the $4$-cycle
$(y_{1},y_{3},z_{3},z_{2})$. Rose, Tarjan and Lueker [21] show that a
triangulation is minimal if and only if every filled edge is the unique chord
of a 4-cycle. This implies that only the chord $\\{y_{1},z_{3}\\}$ can be
filled now (not $\\{y_{3},z_{2}\\}$), in order to be a minimal triangulation,
which leads to a $4$-clique $\\{y_{1},y_{2},z_{2},z_{3}\\}$.

Since we have exhausted all possible minimal triangulations, the proof is
finished.

Next, we show a formal proof of 7.1.

######  Proof D.3 (Proof of 7.1).

To see that $\mathsf{subw}(Q_{hb})\leq 2$, we note that there is fractional
edge cover of $Q_{hb}$ that assigns weight $1$ and $\\{y_{1},y_{2},y_{3}\\}$
and $\\{z_{1},z_{2},z_{3}\\}$ and gets total weight of $2$. Thus, for
$Q_{hb}$, $\mathsf{subw}\leq\mathsf{fhw}\leq 2$.

Next, we show that $\mathsf{subw}(Q_{hb})\geq 2$. We fix an edge-dominated
submodular function defined on $V(Q_{hb})$ as follows,

$\displaystyle h(\emptyset)=0,\quad h(y_{i})=h(z_{i})=1/2,\quad i\in[3]$
$\displaystyle h(e)=1,\quad e\in E$ $\displaystyle
h(\\{y_{1},y_{2},y_{3},z_{i}\\})=h(\\{z_{1},z_{2},z_{3},y_{i}\\})=3/2,\quad
i\in[3]$ $\displaystyle
h(\\{y_{1},y_{2},y_{3},z_{i},z_{j}\\})=h(\\{z_{1},z_{2},z_{3},y_{i},y_{j}\\})=h(\\{z_{1},z_{2},z_{3},y_{1},y_{2},y_{3}\\})=2,\quad
i,j\in[3],i\neq j$ $\displaystyle h(\\{u,v\\})=1,\quad u,v\in V,u\neq v$
$\displaystyle h(\\{y_{i},y_{j},z_{k}\\})=h(\\{y_{k},z_{i},z_{j}\\})=3/2,\quad
i,j,k\in[3],i\neq j$ $\displaystyle
h(\\{y_{i},y_{j},z_{k},z_{\ell}\\})=2,\quad i,j,k,\ell\in[3],i\neq
j,k\neq\ell.$

By D.1, we know that for any proper decomposition, there is one bag $B$ such
that $h(B)\geq h(\\{y_{i},y_{j},z_{k},z_{\ell}\\})=2$, for some $i,j,k$, where
$\ell\in[3],i\neq j,k\neq\ell$. Therefore, we have shown that
$\mathsf{subw}(Q_{hb})\geq 2$. Together, we have proved the claim.

######  Proof D.4 (Proof of Theorem 7.3).

It’s easy to see that a truly subquadratic algorithm for $Q_{b}$ gives a truly
subquadratic algorithm for $Q_{hb}$. Indeed, given an input instance $I_{hb}$
of $Q_{hb}$, we can form an input instance $I_{b}$ of $Q_{b}$ where the table
$(x_{1},x_{2})$ is the projection of the table $(y_{1},y_{2},y_{3})$ in
$I_{hb}$, and similar for the tables
$(x_{1},x_{4}),(x_{1},x_{6}),(x_{3},x_{8}),(x_{5},x_{8})$ and $(x_{7},x_{8})$.
We then solve $I_{b}$ by the truly subquadratic algorithm for $Q_{b}$ and
return the answer. It is easy to see that this algorithm is correct and runs
in truly quadratic time.

The converse direction needs more work, since if we were to simply create the
table $(y_{1},y_{2},y_{3})$ for $Q_{hb}$ by joining the tables
$(x_{1},x_{2}),(x_{1},x_{4})$ and $(x_{1},x_{6})$ for $Q_{b}$, the size of the
result might be significantly greater than all previous tables. For example,
if the sizes of the tables $(x_{1},x_{2}),(x_{1},x_{4})$ and $(x_{1},x_{6})$
are all $m$, then joining them could result in a table of size
$m^{\frac{3}{2}}$ and therefore calling the algorithm for $Q_{hb}$ on this
instance does not necessarily yield a truly subquadratic algorithm for
$Q_{b}$.

We perform the our fine-grained reduction based on _heavy-light split_. Our
goal is to give a subquadratic algorithm for $Q_{b}$ assuming there is one
such algorithm for $Q_{hb}$. Suppose the subquadratic algorithm for $Q_{b}$
runs in time $O(m^{2-\delta})$ for some $\delta>0$, where $m$ is the size of
all tables. Our algorithm for $Q_{b}$ runs as follows. First, it checks
whether there are entries of attribute $x_{1}$ that has degree more than
$\Delta:=m^{\epsilon}$ in tables $(x_{1},x_{2}),(x_{1},x_{4})$ and
$(x_{1},x_{6})$ for some $\epsilon>0$ to be specified later. Those are called
_heavy_ and there are at most $\frac{m}{\Delta}$ many of them. For those
entries, we fix each one so that the remaining query becomes acyclic, and thus
can be solved in linear time by Yannakakis algorithm [25]. We do the same
procedure for heavy entries of attribute $x_{8}$. Therefore, any result of
$Q_{b}$ that contains a heavy entry in attributes $x_{1}$ or $x_{8}$ will be
detected in time $O(m^{2-\epsilon})$. It remains to consider the case where
the entries of attributes $x_{1}$ and $x_{8}$ have degrees less than $\Delta$,
which are called _light_. In this case, we loop over all light entries of
$x_{1}$ in the table $(x_{1},x_{2})$ and directly join them with the tables
$(x_{1},x_{4})$ and $(x_{1},x_{6})$ and project the result to build a table
$(x_{2},x_{4},x_{6})$. We then do the same procedure for joining $x_{8}$. This
will cost time $O(m\cdot\Delta\cdot\Delta)=O(m^{1+2\epsilon})$. We then call
the $O(m^{2-\delta})$ algorithm for $Q_{hb}$, which cost time
$O(m^{(1+2\epsilon)(2-\delta)})$. By choosing
$0<\epsilon<\frac{\delta}{4-2\delta}$ (note that $\delta<2$), we observe that
the whole algorithm for $Q_{b}$ takes time
$O(m^{2-\epsilon})+O(m^{(1+2\epsilon)(2-\delta)})=O(m^{2-\epsilon^{\prime}})$
for some $\epsilon^{\prime}>0$.