This is the full version of the article [25]. The first author has been funded
by the Federal Ministry of Education and Research of Germany (BMBF) in the KI-
LAB-ITSE framework – project number 01IS19066. The second author has been
funded by the German Research Foundation (Deutsche Forschungsgemeinschaft,
DFG) – project number 416776735 (gefördert durch die Deutsche
Forschungsgemeinschaft (DFG) – Projektnummer 416776735).
_2012 ACM Subject Classification_ : Theory of computation $\rightarrow$
Regular languages; Theory of computation $\rightarrow$ Problems, reductions
and completeness; Theory of computation $\rightarrow$ Database query languages
(principles); Theory of computation $\rightarrow$ Data structures and
algorithms for data management

# Fine-Grained Complexity of Regular Path Queries

Katrin Casel  Hasso Plattner Institute, University of Potsdam, Potsdam,
Germany<EMAIL_ADDRESS>Markus L. Schmid  Humboldt-Universität zu Berlin,
Unter den Linden 6, D-10099, Berlin, Germany<EMAIL_ADDRESS>
###### Abstract

A regular path query (RPQ) is a regular expression $q$ that returns all node
pairs $(u,v)$ from a graph database that are connected by an arbitrary path
labelled with a word from $L(q)$. The obvious algorithmic approach to RPQ-
evaluation (called PG-approach), i. e., constructing the product graph between
an NFA for $q$ and the graph database, is appealing due to its simplicity and
also leads to efficient algorithms. However, it is unclear whether the PG-
approach is optimal. We address this question by thoroughly investigating
which upper complexity bounds can be achieved by the PG-approach, and we
complement these with conditional lower bounds (in the sense of the fine-
grained complexity framework). A special focus is put on enumeration and delay
bounds, as well as the data complexity perspective. A main insight is that we
can achieve optimal (or near optimal) algorithms with the PG-approach, but the
delay for enumeration is rather high (linear in the database). We explore
three successful approaches towards enumeration with sub-linear delay: super-
linear preprocessing, approximations of the solution sets, and restricted
classes of RPQs.

###### keywords:

Graph Databases, Regular Path Queries, Enumeration, Fine-Grained Complexity

##  1 Introduction

An essential component of graph query languages (to be found both in
academical prototypes as well as in industrial solutions) are _regular path
queries_ ($\mathsf{RPQ}$s). Abstractly speaking, a regular expression $q$ over
some alphabet $\Sigma$ is interpreted as query that returns from a
$\Sigma$-edge-labelled, directed graph $\operatorname{\mathcal{D}}$ (i. e., a
_graph database_) the set $q(\operatorname{\mathcal{D}})$ of all node pairs
$(u,v)$ that are connected by a $q$-path, i. e., a path labelled with a word
from $q$’s language (and possibly also a witness path per node pair, or even
all such paths). This simple, yet relevant concept has heavily been studied in
database theory (the following list is somewhat biased towards recent work):
results on $\mathsf{RPQ}$s [26, 7, 37, 39, 42, 16], conjunctive
$\mathsf{RPQ}$s [15, 46, 9] and extensions thereof [36, 12, 36, 31], questions
of static analysis [30, 11, 29, 33, 47], experimental analyses [17, 19, 41],
and surveys of this research area [10, 57, 5, 23].

In the simplest setting, where we are only interested in the node pairs (but
no paths) connected by _arbitrary_ $q$-paths (instead of, e. g., simple
paths), evaluation can be done efficiently. Deviating from this simple
setting, however, leads to intractability: if we ask for nodes connected by
_simple paths_ (no repeated nodes), or connected by _trails_ (no repeated
arcs), then $\mathsf{RPQ}$ evaluation is $\operatorname{\mathsf{NP}}$-hard
even in data-complexity (see [43, 7, 40] and [39], respectively). Note that
the simple path and trail semantics are mostly motivated by the fact that
under these semantics there is only a finite number of $q$-paths per node
pair. If we move to conjunctions of $\mathsf{RPQ}$s ($\mathsf{CRPQ}$s) or even
more powerful extensions motivated by practical requirements, then also with
the arbitrary path semantics evaluation becomes intractable in combined
complexity (i. e., they inherit hardness from relational conjunctive queries
($\mathsf{CQ}$s)).

In order to guide practical developments in the area of graph databases, the
computational hard cases of $\mathsf{RPQ}$ (and $\mathsf{CRPQ}$) evaluation
have been thoroughly investigated in database theory. However, with respect to
arbitrary $q$-paths, research seems to have stopped at the conclusion that
efficient evaluation is possible by the following simple _PG-approach_ : given
graph database
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
and $\operatorname{\mathsf{NFA}}$ $M_{q}$ for $q$ with state set $V_{q}$,
construct the _product graph_ $G_{\operatorname{\mathcal{D}},q}$ with nodes
$V_{\operatorname{\mathcal{D}}}\times V_{q}$ and an arc
$((u,p),(v,p^{\prime}))$ iff, for some $\mathtt{a}\in\Sigma$,
$\operatorname{\mathcal{D}}$ has an arc $(u,\mathtt{a},v)$ and $M_{q}$ has an
arc $(p,\mathtt{a},p^{\prime})$, and then use simple graph-searching
techniques on $G_{\operatorname{\mathcal{D}},q}$.

The PG-approach is explicitly defined in several papers, e. g., [43, 10, 40],
and mainly used to prove a worst-case upper bound (actually
$\operatorname{O}(|q||\operatorname{\mathcal{D}}|)$ for Boolean evaluation; in
[40] it is used for enumerating $q$-paths between two given nodes. But it is
also very appealing from a practical point of view due to its simplicity: we
are just coupling well-understood algorithmic concepts like finite automata
and graph reachability algorithms. Arguably, implementing the PG-approach is
an exercise suitable for a first year programming course (making it feasible
and cost-efficient for industrial systems). As it seems, putting
$\mathsf{RPQ}$ evaluation with arbitrary path semantics and the respective PG-
approach into the focus of a thorough theoretical study has not yet been done.
This paper is devoted to this task. In particular, we wish to investigate the
following two (somewhat overlapping) aspects:

  1. 1.

Applicability of the PG-approach: the PG-approach is suited for solving simple
evaluation problems like checking $q(\operatorname{\mathcal{D}})=\emptyset$ or
$(u,v)\in q(\operatorname{\mathcal{D}})$ (for given $u,v\in
V_{\operatorname{\mathcal{D}}}$), but is it also appropriate for more relevant
tasks like computing, counting or enumerating $q(\operatorname{\mathcal{D}})$?

  2. 2.

Optimality of the PG-approach: Does the PG-approach lead to optimal
algorithms, or can it be beaten by conceptionally different techniques?

Answering these questions provides a better theoretical understanding of
$\mathsf{RPQ}$-evaluation (which, as mentioned above, are at the heart of many
graph query languages). But also for the more powerful $\mathsf{CRPQ}$s and
more practically motivated graph query languages, we can derive valuable
insights from our investigation. Let us mention two such examples (a complete
summary of our results follows further down). As noted in [10], we can reduce
$\mathsf{CRPQ}$ evaluation to the evaluation of relational $\mathsf{CQ}$s by
first constructing all tables represented by the single $\mathsf{RPQ}$s and
then evaluating a $\mathsf{CQ}$ over this database. To do this, we first have
to compute the results of all $\mathsf{RPQ}$s, so it seems helpful to know the
best algorithms for this intermediate task. Moreover, if we want to benefit
from the existing $\mathsf{CQ}$ evaluation techniques (e. g., exploiting
acyclicity etc.) we are more or less forced to this two-step approach. With
respect to _enumerations_ of $\mathsf{CQ}$s, it is known that linear
preprocessing and constant delay enumeration is possible provided that the
$\mathsf{CQ}$s satisfy certain acyclicity properties (see [8, 14], or the
surveys [13, 48]). Unfortunately, these techniques do not carry over to
$\mathsf{CRPQ}$s since, as we show, linear preprocessing and constant delay
enumeration is not possible even for single $\mathsf{RPQ}$s (conditional to
some complexity assumptions).

Since the problem we investigate can be solved in polynomial time (also in
combined complexity), we cannot show lower bounds in terms of hardness results
for complexity classes like $\operatorname{\mathsf{NP}}$ or
$\operatorname{\mathsf{PSPACE}}$. Instead, we make use of the framework of
_fine-grained complexity_ , which allows to prove lower bounds that are
conditional on some algorithmic assumptions (see the surveys [54, 22, 55]). In
particular, fine-grained complexity is a rather successful toolbox for giving
evidence that the _obvious_ algorithmic approach to some basic problem, is
also the _optimal_ one. This is exactly our setting here, with respect to
$\mathsf{RPQ}$-evaluation and the PG-approach. To the knowledge of the
authors, such conditional lower bounds are not yet a well-established
technique in database theory (however, see [13, Section 6] for a survey of
conditional lower bounds in the context of $\mathsf{CQ}$ enumeration).

A main challenge is that fine-grained complexity is not exactly tailored to
either the data-complexity perspective or to enumeration problems. We will
next outline our results.

###  1.1 Our Contribution

Non-enum. Results |  $\operatorname{\textsc{Boole}}$, $\operatorname{\textsc{Test}}$, $\operatorname{\textsc{Witness}}$ | $\operatorname{\textsc{Eval}}$ | $\operatorname{\textsc{Count}}$
---|---|---|---
upper bounds | $\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$ |  $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}||q|)$ $\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{\omega})$ |  $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}||q|)$ $\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{\omega})$
lower bounds |  $\operatorname{\textsf{OV}}\&\operatorname{\textsf{com-BMM}}$ |  $\operatorname{O}((|\operatorname{\mathcal{D}}||q|)^{1-\epsilon})$ | — | —
$\operatorname{\textsf{OV}}$ | — | — | $\operatorname{O}^{\textsf{dc}}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon})$
$\operatorname{\textsf{SBMM}}$ | — |  $\operatorname{O}^{\textsf{dc}}(|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)$ | —
|  $\operatorname{\textsf{com-BMM}}$ | — |  $\operatorname{O}^{\textsf{dc}}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon})$ | —
Table 1: All upper bounds can be achieved as running times of some algorithm,
while the lower bounds cannot be achieved as running time by any algorithm,
unless the displayed hypothesis fails. The exponent $\omega$ denotes the best
known matrix multiplication exponent.

All investigated $\mathsf{RPQ}$-evaluation problems are summarised on page 3
(see especially Table 3). In the following,
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
is the graph database, $q$ is the $\mathsf{RPQ}$, and $\epsilon>0$. With the
notation $\operatorname{O}^{\textsf{dc}}(\cdot)$, we hide factors $f(|q|)$ for
some function $f$ (i. e., it is used for stating data-complexities). All lower
bounds mentioned in the following are conditional to some of the algorithmic
assumptions summarised in Section 4 (we encourage the reader less familiar
with fine-grained complexity hypotheses to have a look at this section first,
which can be read independently). For presentational reasons, we do not always
explicitly mention this in the rest of the introduction and when we say that a
certain running time is “not possible”, this statement is always conditional
in this sense (see Tables 1 and 2 for the actual hypotheses). As common in
fine-grained complexity, we rule out _true_ sub-linear
($\operatorname{O}(n^{1-\epsilon})$), sub-quadratic
($\operatorname{O}(n^{2-\epsilon})$), or sub-cubic
($\operatorname{O}(n^{3-\epsilon})$) running times, but not possible running
time improvements by logarithmic factors, e. g.,
$\operatorname{O}(\frac{n^{3}}{\log(n)})$.

####  1.1.1 Non-Enumeration Variants

The following results are summarised in Table 1. For the simple problems
$\operatorname{\textsc{Boole}}$ (checking
$q(\operatorname{\mathcal{D}})=\emptyset$), $\operatorname{\textsc{Test}}$
(checking $(u,v)\in q(\operatorname{\mathcal{D}})$) and
$\operatorname{\textsc{Witness}}$ (computing some element from
$q(\operatorname{\mathcal{D}})$), the PG-approach yields an upper bound of
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$, which is optimal (since
linear) in data complexity, and we can show lower bounds demonstrating its
optimality also in combined complexity. For $\operatorname{\textsc{Eval}}$
(computing the set $q(\operatorname{\mathcal{D}})$) the PG-approach yields a
data complexity upper bound of
$\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)$,
which cannot be improved by _combinatorial_ algorithms, although
$\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|^{2.37})$ is
possible by fast matrix multiplication (see Section 4 for a discussion of the
meaning of the term “combinatorial”). In addition, we can show that linear
time data complexity, i. e.,
$\operatorname{O}^{\textsf{dc}}(|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)$,
is not possible even for non-combinatorial algorithms. For
$\operatorname{\textsc{Count}}$ (computing $|q(\operatorname{\mathcal{D}})|$),
we get
$\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)$
as upper and lower bound, not restricted to combinatorial algorithms.

####  1.1.2 Enumeration

Our results for $\mathsf{RPQ}$-enumeration are summarised in Table 2. An entry
“$\operatorname{O}(\text{delay})$” in column “preprocessing” means that the
preprocessing is bounded by the delay (which means that no preprocessing is
required). The column “sorted” indicates whether the enumeration is produced
lexicographically sorted.

In comparison to the non-enumeration problem variants, the picture is less
clear and deserves more explanation. The PG-approach yields a simple
enumeration algorithm with delay
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$, that also trivially
supports updates in constant time, since the preprocessing fits into the delay
bound. Our lower bounds for $\operatorname{\textsc{Boole}}$ also mean that
this delay cannot be improved in terms of _combined complexity_. While this
lower bound was interesting for problems like $\operatorname{\textsc{Boole}}$
etc., it now gives a correct answer to the wrong question. The main goal now
should be to find out whether we can remedy the linear dependency of the delay
on $|\operatorname{\mathcal{D}}|$, at the expense of spending more time in
terms of $|q|$, or of losing the ability of handling updates, or even of
allowing a slightly super-linear preprocessing.

In this regard, the strongest result would be linear preprocessing
$\operatorname{O}(|\operatorname{\mathcal{D}}|f(|q|))$ and constant delay
$\operatorname{O}(f(|q|))$. However, we can rule this out even for algorithms
not capable of handling updates. Then, the next question is which non-constant
delays can be achieved that are strictly better than linear. For example, none
of our lower bounds for the non-enumeration variants suggest that linear
preprocessing and a delay bounded by, e. g.,
$|V_{\operatorname{\mathcal{D}}}|$ or the degree of
$\operatorname{\mathcal{D}}$, should not be possible. We are _not_ able to
answer this question in its general form (and believe it to be very
challenging), but we are able to provide several noteworthy insights.

For linear preprocessing, a delay of
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ (if possible at all)
cannot be beaten by combinatorial algorithms (even without updates). This can
be strengthened considerably, if we also require updates in some reasonable
time: for general algorithms (i. e., not necessarily combinatorial) delay
_and_ update time strictly better than
$\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|)$ is not
possible even with arbitrary preprocessing, and for combinatorial algorithms
with linear preprocessing even delay _and_ update time of
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$ cannot be beaten. This last
result nicely complements the upper bound at least for combinatorial
algorithms and in the dynamic case.

In summary, for linear preprocessing,
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ is a lower bound for the
delay and if we can beat $\operatorname{O}(|\operatorname{\mathcal{D}}|)$, we
should not be able to also support updates.

Enum. Results | $\operatorname{\textsc{Enum}}$
---|---
|  preprocessing |  delay | sorted | updates
upper bounds |  $\operatorname{O}(\text{delay})$ |  $\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$ |  ✓ |  $\operatorname{O}(1)$
lower bounds |  $\operatorname{\textsf{OV}}\&\operatorname{\textsf{com-BMM}}$ |  $\operatorname{O}(\text{delay})$ |  $\operatorname{O}((|\operatorname{\mathcal{D}}||q|)^{1-\epsilon})$ | $\times$ | $\times$
$\operatorname{\textsf{SBMM}}$ |  $\operatorname{O}^{\textsf{dc}}(|\operatorname{\mathcal{D}}|)$ | $\operatorname{O}^{\textsf{dc}}(1)$ | $\times$ | $\times$
$\operatorname{\textsf{com-BMM}}$ | $\operatorname{O}^{\textsf{dc}}(|\operatorname{\mathcal{D}}|)$ | $\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon})$ | $\times$ | $\times$
| $\operatorname{\textsf{OMv}}$ | arbitrary | $\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon})$ | $\times$ | $\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon})$
| $\operatorname{\textsf{com-BMM}}$ | $\operatorname{O}^{\textsf{dc}}(|\operatorname{\mathcal{D}}|)$ | $\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|^{2-\epsilon})$ | $\times$ | $\operatorname{O}^{\textsf{dc}}(|V_{\operatorname{\mathcal{D}}}|^{2-\epsilon})$
Table 2: All upper bounds can be achieved as running times of some algorithm,
while the lower bounds cannot be achieved as running time by any algorithm,
unless the displayed hypothesis fails. The exponent $\omega$ denotes the best
known matrix multiplication exponent.

####  1.1.3 Enumeration of Restricted Variants

Finally, we obtain restricted problem variants that can be solved with delay
strictly better than $\operatorname{O}(|\operatorname{\mathcal{D}}|)$ (in data
complexity). We explore three different approaches:

  1. 1.

by allowing super-linear preprocessing of
$\operatorname{O}^{\textsf{dc}}(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}}))|\operatorname{\mathcal{D}}|)$
(where
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$
is the average degree of $\operatorname{\mathcal{D}}$), we can achieve a delay
of $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$;

  2. 2.

in linear preprocessing and constant delay, we can enumerate a representative
subset of $q(\operatorname{\mathcal{D}})$ instead of the whole set
$q(\operatorname{\mathcal{D}})$;

  3. 3.

for a subclass of $\mathsf{RPQ}$s, we can solve $\operatorname{\textsc{RPQ-
Enum}}$ with linear preprocessing and delay
$\operatorname{O}(\operatorname{\Delta}(\operatorname{\mathcal{D}}))$ (where
$\operatorname{\Delta}(\operatorname{\mathcal{D}})$ is the maximum degree of
$\operatorname{\mathcal{D}}$).

##  2 Main Definitions

Let $\mathbb{N}=\\{1,2,3,\ldots\\}$ and $[n]=\\{1,2,\ldots,n\\}$ for
$n\in\mathbb{N}$. For a finite alphabet $A$, $A^{+}$ denotes the set of non-
empty words over $A$ and $A^{*}=A^{+}\cup\\{\operatorname{\varepsilon}\\}$
(where $\operatorname{\varepsilon}$ is the empty word). For a word $w\in
A^{*}$, $|w|$ denotes its length; $w^{1}=w$ and $w^{k}=ww^{k-1}$ for every
$k\geq 2$. For $L,K\subseteq A^{*}$, let $L\cdot K=\\{w_{1}\cdot w_{2}\mid
w_{1}\in L,w_{2}\in K\\}$, let $L^{1}=L$ and $L^{k}=L\cdot L^{k-1}$ for every
$k\geq 2$, let $L^{+}=\bigcup_{k\geq 1}L^{k}$ and
$L^{*}=L^{+}\cup\\{\operatorname{\varepsilon}\\}$.

###  2.1 $\Sigma$-Graphs

We now define the central graph model that is used to represent graph
databases as well as finite automata. Let $\Sigma$ be a finite alphabet of
constant size. A _$\Sigma$ -graph_ is a directed, edge labelled multigraph
$G=(V,E)$, where $V$ is the set of _vertices_ (or _nodes_) and $E\subseteq
V\times(\Sigma\cup\\{\operatorname{\varepsilon}\\})\times V$ is the set of
_edges_ (or _arcs_). For $u\in V$ and
$x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$, $E_{x}(u)=\\{v\mid(u,x,v)\in
E\\}$ is the set of _$x$ -successors of $u$_. A path from $w_{0}\in V$ to
$w_{k}\in V$ of length $k\geq 0$ is a sequence
$p=(w_{0},a_{1},w_{1},a_{2},w_{2}\ldots,w_{k-1},a_{k},w_{k})$ with
$(w_{i-1},a_{i},w_{i})\in E$ for every $i\in[k]$. We say that $p$ is
_labelled_ with the _word_ $a_{1}a_{2}\ldots a_{k}\in\Sigma^{*}$. According to
this definition, for every $v\in V$, $(v)$ is a path from $v$ to $v$ of length
$0$ that is labelled by $\operatorname{\varepsilon}$. Hence, every node $v$ of
a $\Sigma$-graph has an $\operatorname{\varepsilon}$-labelled path to itself,
even though there might not be an $\operatorname{\varepsilon}$-arc from $v$ to
$v$. Moreover, due to $\operatorname{\varepsilon}$ as a possible edge-label,
paths of length $k$ may be labelled with words $w$ with $|w|<k$. The size of
$G=(V,E)$ is $|G|=\max\\{|V|,|E|\\}$.

For any $\Sigma$-graph $G=(V,E)$, we call $(V,\\{(u,v)\mid u\neq
v\wedge\exists x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}:(u,x,v)\in
E\\})$ the _underlying graph_ of $G$ (note that the underlying graph is
simple, non-labelled and has no loops). In particular, by a slight abuse of
notation, we denote by $E^{*}$ the reflexive-transitive closure of the
underlying graph of $G$. Since we always assume $|\Sigma|$ to be a constant,
we have that $|G|=\Theta(\max\\{|V|,|\\{(u,v)\mid u\neq v\wedge\exists
x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}:(u,x,v)\in E\\}|\\})$ (i. e.,
$|G|$ is asymptotically equal to the size of its underlying graph). For every
$u\in V$, the _degree of $u$_ is
$\operatorname{\Delta}(u)=|\bigcup_{x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}}E_{x}(u)|$
(so $\operatorname{\Delta}(u)$ is actually the out-degree), and the _maximum
degree_ of $G$ is
$\operatorname{\Delta}(G)=\max\\{|\operatorname{\Delta}(u)|\mid u\in V\\}$.
The _average degree_ of $G$ is
$\operatorname{\overline{\operatorname{\Delta}}}(G)=\tfrac{1}{|V|}\sum_{u\in
V}|\operatorname{\Delta}(u)|$. Obviously,
$\operatorname{\overline{\operatorname{\Delta}}}(G)\leq\operatorname{\Delta}(G)\leq|V|$.

Since $\Sigma$-graphs are the central data structures for our algorithms, we
have to discuss implementational aspects of $\Sigma$-graphs in more detail.
The set $V$ of a $\Sigma$-graph $G=(V,E)$ is represented as a list, and, for
every $u\in V$ and for every $x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$,
we store a list of all $x$-successors of $u$, which is called the _$x$
-adjacency list_ for $u$. We assume that we can check in constant time whether
a list is empty and we can insert elements in constant time. However, finding
and deleting an element from a list requires linear time. Furthermore, we
assume that we always store together with a node a pointer to its adjacency
list (thus, we can always retrieve the $x$-adjacency list for a given node in
constant time).

######  Remark 1.

All lower bounds presented in this paper hold for any graph representation
that can be constructed in time linear in $|G|=\max\\{|V|,|E|\\}$. For the
upper bounds, we chose the simple representation with adjacency lists as it
emerged as the natural structure for our enumeration approach; let us point
out here that since we always store pointers to the adjacency lists along with
the nodes, we can perform a breadth-first search (BFS) from any given start
node $u$ in time $\operatorname{O}(|G|)$. It is a plausible assumption that
most specific graph representations can be transformed into our list-based
representation without much effort. This ensures a certain generality of our
upper complexity bounds in the sense that the corresponding algorithms are, to
a large extent, independent from implementational details. Note also that the
list-based structure only requires space linear in $|G|$.

In the adjacency list representation, we do not have random access to specific
nodes in the graph database, or to specific neighbours of a given node. Thus,
we have to measure a non-constant running-time for performing such operations.
However, the algorithms for our upper bounds are independent from this aspect,
i. e., the total running times would not change if we assume random access to
nodes in constant time.

An exception to this is Theorem 26, for which we can obtain some small
improvement by applying the technique of lazy array initialization (see Remark
27).

For a $\Sigma$-graph $G=(V,E)$, we denote by $G^{R}=(V,E^{R})$ the
$\Sigma$-graph obtained from $G$ by reversing all arcs, i. e.,
$E^{R}=\\{(v,x,u)\mid(u,x,v)\in E\\}$.

######  Lemma 2.

Let $G=(V,E)$ be a $\Sigma$-graph. Then $G^{R}$ can be computed in time
$\operatorname{O}(|G|)$.

######  Proof 2.1.

Since $G^{R}=(V,E^{R})$, it is sufficient to show how the adjacency lists can
be computed that represent $E^{R}$. To avoid confusion with respect to whether
we talk about the $\Sigma$-graph $G$ or the $\Sigma$-graph $G^{R}$ to be
constructed, we denote the $x$-adjacency lists by $x$-$G$-adjacency lists or
$x$-$G^{R}$-adjacency lists, respectively.

We first move through the list for $V$ and, for every $u\in V$, we store this
node in an array along with an empty $x$-$G^{R}$-adjacency list for every
$x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$. This requires time
$\operatorname{O}(|V|)$. Then, for every $u\in V$ and
$x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$, we move through the
$x$-$G$-adjacency list for $u$, and for every element $v$ that we encounter,
we add $u$ to the $x$-$G^{R}$-adjacency list for $v$. Since we can access all
$x$-$G^{R}$-adjacency lists in constant time, we only have to add as many
elements to some $x$-$G^{R}$-adjacency as there are edges in $E$, i. e., the
second step can be done in time $\operatorname{O}(|E|)$. Consequently, we can
construct all $x$-$G^{R}$-adjacency lists in total time
$\operatorname{O}(|V|+|E|)=\operatorname{O}(|G|)$.

###  2.2 Graph Databases and Regular Path Queries

A _nondeterministic finite automaton_ ($\operatorname{\mathsf{NFA}}$ for
short) is a tuple $M=(G,S,T)$, where $G=(V,E)$ is a $\Sigma$-graph (the nodes
$q\in V$ are also called _states_), $S\subseteq V$ with $S\neq\emptyset$ is
the set of _start states_ and $T\subseteq V$ with $T\neq\emptyset$ is the set
of _final states_. The language $\operatorname{\mathcal{L}}(M)$ of an
$\operatorname{\mathsf{NFA}}$ $M$ is the set of all labels of paths from some
start state to some final state. For a $\Sigma$-graph $G=(V,E)$, any subsets
$S,T\subseteq V$ with $S\neq\emptyset\neq T$ induce the
$\operatorname{\mathsf{NFA}}$ $(G,S,T)$. If $S=\\{s\\}$ and $T=\\{t\\}$ are
singletons, then we also write $(G,s,t)$ instead of $(G,\\{s\\},\\{t\\})$.

The set $\operatorname{\mathsf{RE}}_{\Sigma}$ of _regular expressions_ (_over
$\Sigma$_) is recursively defined as follows:
$a\in\operatorname{\mathsf{RE}}_{\Sigma}$ for every
$a\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$;
$(\alpha\cdot\beta)\in\operatorname{\mathsf{RE}}_{\Sigma}$,
$(\alpha\operatorname{\vee}\beta)\in\operatorname{\mathsf{RE}}_{\Sigma}$, and
$(\alpha)^{+}\in\operatorname{\mathsf{RE}}_{\Sigma}$, for every
$\alpha,\beta\in\operatorname{\mathsf{RE}}_{\Sigma}$. For any
$\alpha\in\operatorname{\mathsf{RE}}_{\Sigma}$, let
$\operatorname{\mathcal{L}}(\alpha)$ be the regular language described by the
regular expression $\alpha$ defined as usual:111As usual, we use the same
notation $\operatorname{\mathcal{L}}(\cdot)$ both for regular expressions as
well as finite automata. for every
$a\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$,
$\operatorname{\mathcal{L}}(a)=\\{a\\}$, and for every
$\alpha,\beta\in\operatorname{\mathsf{RE}}_{\Sigma}$,
$\operatorname{\mathcal{L}}(\alpha\cdot\beta)=\operatorname{\mathcal{L}}(\alpha)\cdot\operatorname{\mathcal{L}}(\beta)$,
$\operatorname{\mathcal{L}}(\alpha\operatorname{\vee}\beta)=\operatorname{\mathcal{L}}(\alpha)\cup\operatorname{\mathcal{L}}(\beta)$
and
$\operatorname{\mathcal{L}}(\alpha^{+})=\operatorname{\mathcal{L}}(\alpha)^{+}$.
We also use $\alpha^{*}$ as short hand form for
$\alpha^{+}\operatorname{\vee}\operatorname{\varepsilon}$. By $|\alpha|$, we
denote the length of $\alpha$ represented as a string.

######  Proposition 3.

Every regular expression $\alpha$ can be transformed in time
$\operatorname{O}(|\alpha|)$ into an equivalent $\operatorname{\mathsf{NFA}}$
$M=(G,p_{0},p_{f})$ with $|G|=\operatorname{O}(|\alpha|)$.

######  Proof 2.2.

Let $\alpha\in\operatorname{\mathsf{RE}}_{\Sigma}$. We first construct the
syntax tree $T_{\alpha}$ of $\alpha$ with node set $V_{T_{\alpha}}$.
Obviously, $T_{\alpha}$ has size $\operatorname{O}(|\alpha|)$ and we can
obtain $V_{T_{\alpha}}$ from $\alpha$ in time $\operatorname{O}(|\alpha|)$
(for example, we can transform the expression $\alpha$ to prefix notation and
then construct $T_{\alpha}$ while moving through the prefix notation of
$\alpha$ from left to right). We now construct an
$\operatorname{\mathsf{NFA}}$ $M_{\alpha}=(G=(V,E),\\{p_{0}\\},\\{p_{f}\\})$
from $T_{\alpha}$ as follows (recall that $G$ is a $\Sigma$-graph and
therefore it should adhere to our representations of $\Sigma$-graphs). We
first construct an array of size $2|V_{T_{\alpha}}|$ that contains the nodes
of $V=\\{t_{1},t_{2}\mid t\in V_{T_{\alpha}}\\}$ and we initialise empty
$x$-adjacency lists for all these nodes and for every
$x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$. Then we move through
$T_{\alpha}$ top-down and if the current node $t$ is an inner node with two
children $r$ and $s$, then we do the following:

  * •

If $t$ corresponds to a concatenation $\cdot$, then we add $r_{1}$ to the
$\operatorname{\varepsilon}$-adjacency list of $t_{1}$, we add $s_{1}$ to the
$\operatorname{\varepsilon}$-adjacency list of $r_{2}$, and we add $t_{2}$ to
the $\operatorname{\varepsilon}$-adjacency list of $s_{2}$.

  * •

If $t$ corresponds to an alternation $\operatorname{\vee}$, then we add
$r_{1}$ to the $\operatorname{\varepsilon}$-adjacency list of $t_{1}$, we add
$s_{1}$ to the $\operatorname{\varepsilon}$-adjacency list of $t_{1}$, we add
$t_{2}$ to the $\operatorname{\varepsilon}$-adjacency list of $r_{2}$, and we
add $t_{2}$ to the $\operatorname{\varepsilon}$-adjacency list of $s_{2}$.

If $t$ is an inner node with one child $r$ (which means it necessarily
corresponds to a $+$), then we add $r_{1}$ to the
$\operatorname{\varepsilon}$-adjacency list of $t_{1}$, we add $t_{2}$ to the
$\operatorname{\varepsilon}$-adjacency list of $r_{2}$, and we add $t_{1}$ to
the $\operatorname{\varepsilon}$-adjacency list of $t_{2}$. If $t$ is a leaf
labelled with $x\in\Sigma\cup\\{\operatorname{\varepsilon}\\}$, then we add
$t_{2}$ to the $x$-adjacency list of $t_{1}$. Finally, if $t$ is the root of
$T_{\alpha}$, we relabel $t_{1}$ by $p_{0}$ and we relabel $t_{2}$ by $p_{f}$.

It can be easily verified that
$\operatorname{\mathcal{L}}(M_{\alpha})=\operatorname{\mathcal{L}}(\alpha)$.
By construction
$|V|=\operatorname{O}(|T_{\alpha}|)=\operatorname{O}(|\alpha|)$ and, since $G$
has constant degree, we also have that
$|G|=\operatorname{O}(|V|)=\operatorname{O}(|\alpha|)$. Moreover, in the
construction we spend constant time per arc that is added, so the whole
construction of $M_{\alpha}$ can be done in time $\operatorname{O}(|\alpha|)$.

In the following, when we speak about an _automaton_ (or an
_$\operatorname{\mathsf{NFA}}$_) _for a regular expression $\alpha$_, we
always mean an $\operatorname{\mathsf{NFA}}$ equivalent to $\alpha$ with the
properties asserted by Proposition 3.

A $\Sigma$-graph without $\operatorname{\varepsilon}$-arcs is also called a
_graph database_ (_over $\Sigma$_); in the following, we denote graph
databases by
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$.
Since $V_{\operatorname{\mathcal{D}}}$ is represented as a list, any graph
database implicitly represents a linear order on
$V_{\operatorname{\mathcal{D}}}$ (i. e., the order induced by the list that
represents $V_{\operatorname{\mathcal{D}}}$), which we denote by
$\preceq_{\operatorname{\mathcal{D}}}$, or simply $\preceq$ if
$\operatorname{\mathcal{D}}$ is clear from the context. A class $\mathcal{C}$
of graph databases is called _sparse_ if there is a constant $c$ such that
$|E_{\operatorname{\mathcal{D}}}|\leq c|V_{\operatorname{\mathcal{D}}}|$ for
every $\operatorname{\mathcal{D}}\in\mathcal{C}$. Slightly abusing notation,
we shall also call single graph databases sparse to denote that we are dealing
with a graph database from a sparse class of graph databases.

Regular expressions $q$ (over alphabet $\Sigma$) are interpreted as _regular
path queries_ ($\mathsf{RPQ}$) for graph databases (over $\Sigma$). The
_result_ $q(\operatorname{\mathcal{D}})$ of an $\mathsf{RPQ}$ $q$ on a graph
database
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
over $\Sigma$ is the set $q(\operatorname{\mathcal{D}})=\\{(u,v)\mid u,v\in
V_{\operatorname{\mathcal{D}}},\operatorname{\mathcal{L}}((\operatorname{\mathcal{D}},u,v))\cap\operatorname{\mathcal{L}}(q)\neq\emptyset\\}$.

If we interpret $q$ as a _Boolean_ $\mathsf{RPQ}$, then the result is
$q_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}})=\mathsf{true}$ if
$q(\operatorname{\mathcal{D}})\neq\emptyset$ and
$q_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}})=\mathsf{false}$
otherwise. We consider the $\mathsf{RPQ}$-evaluation problems summarised in
Table 3. By _sorted $\operatorname{\textsc{RPQ-Enum}}$_ (or _semi-sorted_
$\operatorname{\textsc{RPQ-Enum}}$), we denote the variant of
$\operatorname{\textsc{RPQ-Enum}}$, where the pairs of
$q(\operatorname{\mathcal{D}})$ are to be enumerated in lexicographical order
with respect to $\preceq_{\operatorname{\mathcal{D}}}$ (or ordered only with
respect to their left elements, while successive pairs with the same right
element can be ordered arbitrarily, respectively).

Name | Input | Task
---|---|---
$\operatorname{\textsc{RPQ-Boole}}$ |  $\operatorname{\mathcal{D}}$, $q$ | Decide whether $q_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}})=\mathsf{true}$.
$\operatorname{\textsc{RPQ-Test}}$ |  $\operatorname{\mathcal{D}}$, $q$, $u,v$ | Decide whether $(u,v)\in q(\operatorname{\mathcal{D}})$.
$\operatorname{\textsc{RPQ-Witness}}$ |  $\operatorname{\mathcal{D}}$, $q$ | Compute a witness $(u,v)\in q(\operatorname{\mathcal{D}})$ or report that none exists.
$\operatorname{\textsc{RPQ-Eval}}$ |  $\operatorname{\mathcal{D}}$, $q$ | Compute the whole set $q(\operatorname{\mathcal{D}})$
$\operatorname{\textsc{RPQ-Count}}$ |  $\operatorname{\mathcal{D}}$, $q$ | Compute $|q(\operatorname{\mathcal{D}})|$.
$\operatorname{\textsc{RPQ-Enum}}$ |  $\operatorname{\mathcal{D}}$, $q$ | Enumerate the whole set $q(\operatorname{\mathcal{D}})$.
Table 3: The investigated $\mathsf{RPQ}$-evaluation problems
($\operatorname{\mathcal{D}}$ is a graph database, $q$ an $\mathsf{RPQ}$ and
$u,v$ two nodes from $\operatorname{\mathcal{D}}$).

######  Remark 4.

If an order $\preceq^{\prime}$ on $V_{\operatorname{\mathcal{D}}}$ is
explicitly given as a bijection
$\pi:V_{\operatorname{\mathcal{D}}}\to\\{1,\ldots,n\\}$, then we can modify
$\operatorname{\mathcal{D}}$ (in
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$) such that
$\preceq_{\operatorname{\mathcal{D}}}\;=\;\preceq^{\prime}$. In this regard,
sorted $\operatorname{\textsc{RPQ-Enum}}$ just models the case where we wish
the enumeration to be sorted according to some order. In particular, by
assuming the order $\preceq_{\operatorname{\mathcal{D}}}$ to be implicitly
represented by $\operatorname{\mathcal{D}}$, we _do not_ hide the complexity
of sorting $n$ elements.

A graph database $\operatorname{\mathcal{D}}$ is _well-formed_ if
$V_{\operatorname{\mathcal{D}}}=[n]$ for some $n\in\mathbb{N}$ and
$\preceq_{\operatorname{\mathcal{D}}}$ corresponds to $\leq$ on $[n]$.

######  Lemma 5.

Let $\operatorname{\mathcal{D}}$ be a graph database with
$|V_{\operatorname{\mathcal{D}}}|=n$. Then we can construct in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$ a well-formed graph database
$\operatorname{\mathcal{D}}^{\prime}$ and an isomorphism $\pi:[n]\to
V_{\operatorname{\mathcal{D}}}$ between $\operatorname{\mathcal{D}}^{\prime}$
and $\operatorname{\mathcal{D}}$.

######  Proof 2.3.

Let $\operatorname{\mathcal{D}}$ be a graph database with
$|V_{\operatorname{\mathcal{D}}}|=n$. We initialise an array $A$ of size $n$
that can be addressed with the elements of $V_{\operatorname{\mathcal{D}}}$
and the entries of which can store numbers of $[n]$, and an array $B$ of size
$n$ that can be addressed with the elements of $[n]$ and the entries of which
can store elements of $V_{\operatorname{\mathcal{D}}}$. Furthermore, we
initialise a counter $c=1$. Then we move through the list for
$V_{\operatorname{\mathcal{D}}}$ from left to right and for each element $u$
that we encounter, we set $A[u]=c$, $B[c]=u$ and increment $c$. Obviously, $A$
describes an isomorphism $\pi:V_{\operatorname{\mathcal{D}}}\to[n]$ and $B$
describes $\pi^{-1}$. Moreover, this can be done in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$.

Next, we make a copy $\operatorname{\mathcal{D}}^{\prime}$ of
$\operatorname{\mathcal{D}}$ but replace each $u\in
V_{\operatorname{\mathcal{D}}}$ by the number $A[u]$ (note that
$\operatorname{\mathcal{D}}$ is just a collection of lists that store elements
of $V_{\operatorname{\mathcal{D}}}$ along with pointers to lists). This can be
done in time $\operatorname{O}(|\operatorname{\mathcal{D}}|)$. Moreover,
$\operatorname{\mathcal{D}}^{\prime}$ is obviously isomorphic to
$\operatorname{\mathcal{D}}$ and $B$ describes an isomorphism $[n]\to
V_{\operatorname{\mathcal{D}}}$.

Lemma 5 means that with an overhead of time
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$, we can always assume that
our input graph databases are well-formed; in particular, note that with the
isomorphism $\pi$ ensured by the lemma, we can always translate elements from
$q(\operatorname{\mathcal{D}}^{\prime})$, where
$\operatorname{\mathcal{D}}^{\prime}$ is the well-formed graph database
isomorphic to $\operatorname{\mathcal{D}}$, back to the corresponding elements
of $q(\operatorname{\mathcal{D}})$. Thus, Lemma 5 justifies that whenever we
spend at least $\operatorname{O}(|\operatorname{\mathcal{D}}|)$ in some
preprocessing, we can always assume that the input graph database is well-
formed.

###  2.3 General Algorithmic Framework for $\mathsf{RPQ}$-Evaluation

We assume the RAM-model with logarithmic word-size as our computational model.
Let us next discuss our algorithmic framework for $\mathsf{RPQ}$-evaluation.
The input to our algorithms is a graph database
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
and an $\mathsf{RPQ}$ $q$ (and, for solving the problem
$\operatorname{\textsc{RPQ-Test}}$, also a pair $(u,v)\in
V_{\operatorname{\mathcal{D}}}$).

In the case of $\operatorname{\textsc{RPQ-Enum}}$, the algorithms have
routines $\operatorname{\mathsf{preprocess}}$ and
$\operatorname{\mathsf{enum}}$. Initially,
$\operatorname{\mathsf{preprocess}}$ performs some preliminary computations on
the input or constructs some auxiliary data-structures; the performance of
$\operatorname{\mathsf{preprocess}}$ is measured in its running-time depending
on the input size as usual (i. e., we treat
$\operatorname{\mathsf{preprocess}}$ as an individual algorithm). Then
$\operatorname{\mathsf{enum}}$ will produce an enumeration
$(u_{1},v_{1}),(u_{2},v_{2}),\ldots,(u_{\ell},v_{\ell})$ such that
$q(\operatorname{\mathcal{D}})=\\{(u_{i},v_{i})\mid 1\leq i\leq\ell\\}$, no
element occurs twice, and the algorithm reports when the enumeration is done.
We measure the performance of $\operatorname{\mathsf{enum}}$ in terms of its
_delay_ , which describes the time that (in the worst-case) elapses between
enumerating two consecutive elements, between the start of the enumeration and
the first element, and between the last element and the end of the enumeration
(or between start and end in case that
$q(\operatorname{\mathcal{D}})=\emptyset$). We say that (variants of)
$\operatorname{\textsc{RPQ-Enum}}$ can be solved _with preprocessing $p$ and
delay $d$_, where $p$ and $d$ are functions bounding the preprocessing
running-time and the delay. In the case that $p=\operatorname{O}(d)$, the
preprocessing complexity is absorbed by the delay; in this case, we say that
(variants of) $\operatorname{\textsc{RPQ-Enum}}$ can be solved _with delay
$d$_ and do not mention any bound on the preprocessing.

We also consider $\operatorname{\textsc{RPQ-Enum}}$ in the _dynamic setting_ ,
i. e., there is the possibility to perform _update_ operations on the input
graph database $\operatorname{\mathcal{D}}$, which trigger a routine
$\operatorname{\mathsf{update}}$. After an update and termination of the
$\operatorname{\mathsf{update}}$ routine, invoking
$\operatorname{\mathsf{enum}}$ is supposed to enumerate
$q(\operatorname{\mathcal{D}}^{\prime})$, where
$\operatorname{\mathcal{D}}^{\prime}$ is the updated graph database. The
performance of an algorithm for $\operatorname{\textsc{RPQ-Enum}}$ is then
measured in the running-times of routines $\operatorname{\mathsf{preprocess}}$
(to be initially carried out only once) and $\operatorname{\mathsf{update}}$,
as well as the delay. We only consider the following types of individual
updates: inserting a new arc between existing nodes, deleting an arc, adding a
new (isolated) node, deleting an (isolated) node. In particular, deleting or
adding a single non-isolated node $u$ may require a non-constant number of
updates.

##  3 The Product Graph Approach

The PG-approach has already been informally described in the introduction; for
our fine-grained perspective, we need to define it in detail. Let
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
be a graph database over some alphabet $\Sigma$ and let $q$ be an
$\mathsf{RPQ}$ over $\Sigma$. Furthermore, let
$(G_{q},p_{\operatorname{0}},p_{f})$ with $G_{q}=(V_{q},E_{q})$ be an
automaton for $q$. Recall that, according to Proposition 3, $G_{q}$ can be
obtained in time $\operatorname{O}(|q|)$ and it has $\operatorname{O}(|q|)$
states and $\operatorname{O}(|q|)$ arcs. The _product graph_ of
$\operatorname{\mathcal{D}}$ and $G_{q}$ is the $\Sigma$-graph
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)=(V_{\boxtimes}(\operatorname{\mathcal{D}},q),E_{\boxtimes}(\operatorname{\mathcal{D}},q))$,
where $V_{\boxtimes}(\operatorname{\mathcal{D}},q)=\\{(u,p)\mid u\in
V_{\operatorname{\mathcal{D}}},p\in V_{q}\\}$ and

$\displaystyle E_{\boxtimes}(\operatorname{\mathcal{D}},q)=\>$
$\displaystyle\\{((u,p),x,(v,p^{\prime}))\mid(u,x,v)\in
E_{\operatorname{\mathcal{D}}},(p,x,p^{\prime})\in E_{q}\\}\>\cup$
$\displaystyle\\{((u,p),\operatorname{\varepsilon},(u,p^{\prime}))\mid u\in
V_{\operatorname{\mathcal{D}}},(p,\operatorname{\varepsilon},p^{\prime})\in
E_{q}\\}\,.$

######  Remark 6.

The arc labels in $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ are
superfluous in the sense that we only need the underlying graph of
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ (see Lemma 8). We define it
nevertheless as $\Sigma$-graph, since then all our definitions and terminology
for $\Sigma$-graphs introduced above apply as well.

######  Lemma 7.

$|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||q|)$,
$|E_{\boxtimes}(\operatorname{\mathcal{D}},q)|=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$
and $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ can be computed in time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

######  Proof 3.1.

We first note that
$|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|\leq|V_{\operatorname{\mathcal{D}}}||q|$
directly follows from the definition. Moreover, the following is also
immediate by definition:

$\displaystyle|\\{((u,p),\operatorname{\varepsilon},(u,p^{\prime}))\mid u\in
V_{\operatorname{\mathcal{D}}},(p,\operatorname{\varepsilon},p^{\prime})\in
E_{q}\\}|=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||E_{q}|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)\text{
and }$ $\displaystyle|\\{((u,p),x,(v,p^{\prime}))\mid(u,x,v)\in
E_{\operatorname{\mathcal{D}}},(p,x,p^{\prime})\in
E_{q}\\}|=\operatorname{O}(|E_{\operatorname{\mathcal{D}}}||E_{q}|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)\,.$

Consequently,
$|E_{\boxtimes}(\operatorname{\mathcal{D}},q)|=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

For the question how $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ can be
computed, we have to keep in mind our list-based implementation of
$\Sigma$-graphs (see Section 2). For every $u\in
V_{\operatorname{\mathcal{D}}}$ and every $p\in V_{q}$, we add $(u,p)$ to the
list that stores $V_{\boxtimes}(\operatorname{\mathcal{D}},q)$. This can be
done by moving $|V_{\operatorname{\mathcal{D}}}|$ times through the list for
$V_{q}$. Thus, time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||V_{q}|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$
is sufficient.

In order to construct the adjacency lists, we proceed as follows. Let $u\in
V_{\operatorname{\mathcal{D}}}$, $p\in V_{q}$ and $x\in\Sigma$. Then we add
all $(v,p^{\prime})$ to the $x$-adjacency list of $(u,p)$, where $v$ is an
element of the $x$-adjacency list of $u$, and $p^{\prime}$ is an element of
the $x$-adjacency list of $p$. Moreover, we add all $(u,p^{\prime})$ to the
$\operatorname{\varepsilon}$-adjacency list of $(u,p)$, where $p^{\prime}$ is
an element of the $\operatorname{\varepsilon}$-adjacency list of $p$. This can
be done by moving once through the lists of adjacency lists for
$E_{\operatorname{\mathcal{D}}}$ and, for each encountered element, to move
through the lists of adjacency lists for $E_{q}$. Since each insertion to a
list can be done in constant time, the whole procedure can be carried out in
time
$\operatorname{O}(|\Sigma||\operatorname{\mathcal{D}}||q|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

The following lemma, which is an immediate consequence of the construction,
shows how $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ can be used for
solving $\mathsf{RPQ}$-evaluation tasks (recall that $E^{*}$ is the reflexive-
transitive closure of the underlying unlabelled graph).

######  Lemma 8.

For every $u,v\in V_{\operatorname{\mathcal{D}}}$, $(u,v)\in
q(\operatorname{\mathcal{D}})$ if and only if
$((u,p_{\operatorname{0}}),(v,p_{f}))\in(E_{\boxtimes}(\operatorname{\mathcal{D}},q))^{*}$.

##  4 Fine-grained Complexity and Conditional Lower Bounds

We now state several computational problems along with hypotheses regarding
their complexity, which are commonly used in the framework of fine-grained
complexity to obtain conditional lower bounds. We discuss some details and
give background information later on.

  * •

Orthogonal Vectors ($\operatorname{\textsf{OV}}$): Given sets $A,B$ each
containing $n$ Boolean-vectors of dimension $d$, check whether there are
vectors $\vec{a}\in A$ and $\vec{b}\in B$ that are orthogonal.
$\operatorname{\textsf{OV}}$-Hypothesis: For every $\epsilon>0$ there is no
algorithm solving $\operatorname{\textsf{OV}}$ in time
$\operatorname{O}(n^{2-\epsilon}\operatorname{\mathsf{poly}}(d))$.

  * •

Boolean Matrix Multiplication ($\operatorname{\textsf{BMM}}$): Given Boolean
$n\times n$ matrices $A,B$, compute $A\times B$.
$\operatorname{\textsf{com-BMM}}$-Hypothesis: For every $\epsilon>0$ there is
no combinatorial algorithm that solves $\operatorname{\textsf{BMM}}$ in time
$\operatorname{O}(n^{3-\epsilon})$.

  * •

Sparse Boolean Matrix Multiplication ($\operatorname{\textsf{SBMM}}$): Like
$\operatorname{\textsf{BMM}}$, but all matrices are represented as sets
$\\{(i,j)\mid A[i,j]=1\\}$ of $1$-entries.
$\operatorname{\textsf{SBMM}}$-Hypothesis: There is no algorithm that solves
$\operatorname{\textsf{SBMM}}$ in time $\operatorname{O}(m)$ (where $m$ is the
total number of $1$-entries, i. e., $m=|\\{(i,j)\mid
A[i,j]=1\\}|+|\\{(i,j)\mid B[i,j]=1\\}|+|\\{(i,j)\mid(A\times B)[i,j]=1\\}|$).

  * •

Online Matrix-Vector Multiplication ($\operatorname{\textsf{OMv}}$): Given
Boolean $n\times n$-matrix $M$ and a sequence
$\vec{v}^{1},\vec{v}^{2},\ldots,\vec{v}^{n}$ of $n$-dimensional Boolean
vectors, compute the sequence $M\vec{v}^{1},M\vec{v}^{2},\ldots,M\vec{v}^{n}$,
where $M\vec{v}^{i}$ is produced as output before $\vec{v}^{i+1}$ is received
as input.
$\operatorname{\textsf{OMv}}$-Hypothesis: For every $\epsilon>0$ there is no
algorithm that solves $\operatorname{\textsf{OMv}}$ in time
$\operatorname{O}(n^{3-\epsilon})$.

We will reduce these problems to variants of $\mathsf{RPQ}$ evaluation
problems in such a way that algorithms with certain running-times for
$\mathsf{RPQ}$ evaluation would break the corresponding hypotheses mentioned
above. Thus, we obtain lower bounds for $\mathsf{RPQ}$ evaluation that are
conditional to these hypotheses. In the following, we give a very brief
overview of the relevance of these problems and corresponding hypotheses in
fine-grained complexity.

The problem $\operatorname{\textsf{OV}}$ can be solved by brute-force in time
$\operatorname{O}(n^{2}d)$ and the hypothesis that there is no subquadratic
algorithm is well-established. It exists in slightly different variants and
has been formulated in several different places in the literature (e. g., [21,
22, 54]). The variant used here is sometimes referred to as _moderate
dimension_ $\operatorname{\textsf{OV}}$-hypothesis in contrast to _low
dimension_ variants, where $d$ can be assumed to be rather small in comparison
to $n$. The relevance of the $\operatorname{\textsf{OV}}$-hypothesis is due to
the fact that it is implied by the Strong Exponential Time Hypothesis (SETH)
[50, 51], and therefore it is a convenient tool to prove SETH lower bounds
that has been applied in various contexts.

One of the most famous computational problems is
$\operatorname{\textsf{BMM}}$, which, unfortunately, is a much less suitable
basis for conditional lower bounds. The straightforward algorithm solves it in
time $\operatorname{O}(n^{3})$, but there are _fast matrix multiplication_
algorithms that run in time $\operatorname{O}(n^{2.373})$ [53, 32]. It is
unclear how much further this exponent can be decreased and there is even
belief that $\operatorname{\textsf{BMM}}$ can be solved in time
$n^{2+\operatorname{o}(1)}$ (see [52] and [13, Section 6]). However, these
theoretically fast algorithms cannot be considered efficient in a practical
sense, which motivates the mathematically informal notion of “ _combinatorial_
” algorithms (see, e. g., [56]).222The term “combinatorial algorithm” is not
well-defined, but intuitively such algorithms have running-times with low
constants in the $\operatorname{O}$-notation, and are feasibly implementable.
So far, no truly subcubic _combinatorial_
$\operatorname{\textsf{BMM}}$-algorithm exists and it has been shown in [56]
that $\operatorname{\textsf{BMM}}$ is contained in a class of problems
(including other prominent examples like Triangle Finding (also mentioned
below) and Context-Free Grammar Parsing) which are all equivalent in the sense
that if one such problem is solvable in truly subcubic time by a combinatorial
algorithm, then all of them are. Consequently, it is often possible to argue
that the existence of a certain combinatorial algorithm for some problem would
imply a major (and unlikely) algorithmic breakthrough with respect to
$\operatorname{\textsf{BMM}}$, Parsing, Triangle Finding, etc. Despite the
defect of relying on the vague notion of _combinatorial_ algorithms, this
lower bound technique is a common approach in fine-grained complexity (see, e.
g., [56, 34, 2, 3, 1, 35]). Whenever we use the $\operatorname{\textsf{com-
BMM}}$-hypothesis, our reductions will always be combinatorial, which is
necessary; moreover, whenever we say that a certain running time cannot be
achieved unless the $\operatorname{\textsf{com-BMM}}$-hypothesis fails, we
mean, of course, that it cannot be achieved by a combinatorial algorithm.

In order to make $\operatorname{\textsf{BMM}}$ suitable as base problem for
conditional lower bounds (that does not rely on _combinatorial_ algorithms)
one can formulate the weaker (i. e., more plausible) hypothesis that
$\operatorname{\textsf{BMM}}$ cannot be solved in time linear in the number of
$1$-entries of the matrices (therefore called _sparse_
$\operatorname{\textsf{BMM}}$ since matrices are represented in a sparse way);
see [4, 58]. Another approach is to require the output matrix $A\times B$ to
be computed column by column, i. e., formulating it as the online-version
$\operatorname{\textsf{OMv}}$. For $\operatorname{\textsf{OMv}}$, subcubic
algorithms are not known and would yield several major algorithmic
breakthroughs (see [34]).

A convenient tool to deal with $\operatorname{\textsf{BMM}}$ is the problem
$\operatorname{\textsf{Triangle}}$: check whether a given undirected graph $G$
has a triangle. This is due to the fact that these two problems are subcubic
equivalent with respect to combinatorial algorithms (see [56]), i. e., the
$\operatorname{\textsf{com-BMM}}$-hypothesis fails if and only if
$\operatorname{\textsf{Triangle}}$ can be solved by a combinatorial algorithm
in time $\operatorname{O}(n^{3-\epsilon})$ for some $\epsilon>0$. Thus, for
lower bounds conditional to the $\operatorname{\textsf{com-BMM}}$-hypothesis,
we can make use of both these problems. There is also a (non-combinatorial)
$\operatorname{\textsf{Triangle}}$-hypothesis that states that
$\operatorname{\textsf{Triangle}}$ cannot be solved in linear time in the
number of edges, but we were not able to apply it in the context of
$\mathsf{RPQ}$-evaluation (see [2] for different variants of
$\operatorname{\textsf{Triangle}}$).

##  5 Bounds for the Non-Enumeration Problem Variants

We now investigate how well the PG-approach performs with respect to the non-
enumeration variants of $\mathsf{RPQ}$-evaluation, and we give some evidence
that, in most cases, it can be considered optimal or almost optimal (subject
to the algorithmic hypotheses of Section 4).

###  5.1 Boolean Evaluation, Testing and Computing a Witness

It is relatively straightforward to see that the problems
$\operatorname{\textsc{RPQ-Test}}$ and $\operatorname{\textsc{RPQ-Boole}}$ are
equivalent and can both be reduced to $\operatorname{\textsc{RPQ-Witness}}$.
Hence, upper bounds for $\operatorname{\textsc{RPQ-Witness}}$ and lower bounds
for $\operatorname{\textsc{RPQ-Test}}$ or $\operatorname{\textsc{RPQ-Boole}}$
automatically apply to all three problem variants, which simplifies the proofs
for such bounds. We shall now formally prove this.

######  Lemma 9.

Let $(\operatorname{\mathcal{D}},q)$ be an $\operatorname{\textsc{RPQ-
Boole}}$-instance. Then we can construct an equivalent
$\operatorname{\textsc{RPQ-Test}}$-instance
$(\operatorname{\mathcal{D}}^{\prime},q^{\prime},u,v)$ with
$|\operatorname{\mathcal{D}}^{\prime}|=\operatorname{O}(|\operatorname{\mathcal{D}}|)$
and $|q^{\prime}|=\operatorname{O}(|q|)$ in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|+|q|)$.

######  Proof 5.1.

Let $\operatorname{\mathcal{D}}$ and $q$ be defined over $\Sigma$. We
transform $\operatorname{\mathcal{D}}$ into a graph database
$\operatorname{\mathcal{D}}^{\prime}$ over $\Sigma\cup\\{\\#\\}$ (where
$\\#\notin\Sigma$) by adding new nodes $u$ and $v$, and new arcs $(u,\\#,x)$
and $(x,\\#,v)$ for every $x\in V_{\operatorname{\mathcal{D}}}$. Moreover, we
set $q^{\prime}=\\#q\\#$. This construction can be carried out in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|+|q|)$ and we can also note that
$|\operatorname{\mathcal{D}}^{\prime}|=\operatorname{O}(|\operatorname{\mathcal{D}}|)$
and $|q^{\prime}|=\operatorname{O}(|q|)$.

It remains to show that
$q_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}})=\textsf{true}$ if
and only if $(u,v)\in q^{\prime}(\operatorname{\mathcal{D}}^{\prime})$. If
$q_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}})=\textsf{true}$,
then there is some $(u^{\prime},v^{\prime})\in q(\operatorname{\mathcal{D}})$,
which means that in $\operatorname{\mathcal{D}}$ there is a path
$u^{\prime},\ldots,v^{\prime}$ that is labelled with a word
$w\in\operatorname{\mathcal{L}}(q)$. Since there are arcs $(u,\\#,u^{\prime})$
and $(v^{\prime},\\#,v)$ in $\operatorname{\mathcal{D}}^{\prime}$, there is a
path $u,u^{\prime},\ldots,v^{\prime},v$ in
$\operatorname{\mathcal{D}}^{\prime}$ that is labelled with
$\\#w\\#\in\operatorname{\mathcal{L}}(q^{\prime})$. Therefore, $(u,v)\in
q^{\prime}(\operatorname{\mathcal{D}}^{\prime})$. On the other hand, if
$(u,v)\in q^{\prime}(\operatorname{\mathcal{D}}^{\prime})$, then there is some
path $u,u^{\prime},\ldots,v^{\prime},v$ in
$\operatorname{\mathcal{D}}^{\prime}$ that is labelled with
$\\#w\\#\in\operatorname{\mathcal{L}}(q^{\prime})$, so therefore also
$(u^{\prime},v^{\prime})\in q(\operatorname{\mathcal{D}})$ and
$q_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}})=\textsf{true}$
(note that $u^{\prime}=v^{\prime}$ and therefore
$w=\operatorname{\varepsilon}$ is also possible).

######  Lemma 10.

Let $(\operatorname{\mathcal{D}},q,u,v)$ be an $\operatorname{\textsc{RPQ-
Test}}$-instance. Then we can construct an equivalent
$\operatorname{\textsc{RPQ-Boole}}$-instance
$(\operatorname{\mathcal{D}}^{\prime},q^{\prime})$ with
$|\operatorname{\mathcal{D}}^{\prime}|=\operatorname{O}(|\operatorname{\mathcal{D}}|)$
and $|q^{\prime}|=\operatorname{O}(|q|)$ in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|+|q|)$.

######  Proof 5.2.

Let $\operatorname{\mathcal{D}}$ and $q$ be defined over $\Sigma$. We
transform $\operatorname{\mathcal{D}}$ into a graph database
$\operatorname{\mathcal{D}}^{\prime}$ over $\Sigma\cup\\{\\#\\}$ (where
$\\#\notin\Sigma$) by adding new nodes $s$ and $t$ with arcs $(s,\\#,u)$ and
$(v,\\#,t)$, and we define $q^{\prime}=\\#q\\#$. This construction can be
carried out in time $\operatorname{O}(|\operatorname{\mathcal{D}}|+|q|)$ and
we can also note that
$|\operatorname{\mathcal{D}}^{\prime}|=\operatorname{O}(|\operatorname{\mathcal{D}}|)$
and $|q^{\prime}|=\operatorname{O}(|q|)$.

It remains to show that $(u,v)\in q(\operatorname{\mathcal{D}})$ if and only
if
$q^{\prime}_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}}^{\prime})=\textsf{true}$.
If $(u,v)\in q(\operatorname{\mathcal{D}})$, then there is a path from $u$ to
$v$ in $\operatorname{\mathcal{D}}$ that is labelled with a word from
$\operatorname{\mathcal{L}}(q)$. Since there are arcs $(s,\\#,u)$ and
$(v,\\#,t)$ in $\operatorname{\mathcal{D}}^{\prime}$, there is a path in
$\operatorname{\mathcal{D}}^{\prime}$ from $s$ to $t$ labelled with a word
from $\operatorname{\mathcal{L}}(\\#q\\#)$; thus $(s,t)\in
q^{\prime}(\operatorname{\mathcal{D}}^{\prime})$ and therefore
$q^{\prime}_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}}^{\prime})=\textsf{true}$.
On the other hand, if
$q^{\prime}_{\operatorname{\textsf{B}}}(\operatorname{\mathcal{D}}^{\prime})=\textsf{true}$,
then we can conclude that $(s,t)\in
q^{\prime}(\operatorname{\mathcal{D}}^{\prime})$, which is due to the fact
that $q^{\prime}=\\#q\\#$, $q$ does not contain any occurrence of $\\#$ and
the only arcs labelled with $\\#$ have source $s$ and target $t$. This implies
that there is a path $s,u,\ldots,v,t$ labelled with a word $\\#w\\#$ with
$w\in\operatorname{\mathcal{L}}(q)$, which implies that there is a path from
$u$ to $v$ labelled with a word from $\operatorname{\mathcal{L}}(q)$, which
means that $(u,v)\in q(\operatorname{\mathcal{D}})$.

######  Theorem 11.

Let $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ be some polynomial function
with $f(n_{1},n_{2})=\Omega(n_{1}+n_{2})$.

  1. 1.

$\operatorname{\textsc{RPQ-Test}}$ can be solved in time
$f(|\operatorname{\mathcal{D}}|,|q|)$ if and only if
$\operatorname{\textsc{RPQ-Boole}}$ can be solved in time
$f(|\operatorname{\mathcal{D}}|,|q|)$.

  2. 2.

If $\operatorname{\textsc{RPQ-Witness}}$ can be solved in time
$f(|\operatorname{\mathcal{D}}|,|q|)$, then $\operatorname{\textsc{RPQ-
Boole}}$ and $\operatorname{\textsc{RPQ-Test}}$ can be solved in time
$f(|\operatorname{\mathcal{D}}|,|q|)$.

######  Proof 5.3.

Lemmas 9 and 10 directly imply Point 1. Moreover, an algorithm that solves
$\operatorname{\textsc{RPQ-Witness}}$ implicitly solves
$\operatorname{\textsc{RPQ-Boole}}$ as well. Together with Point 1, this
proves Point 2.

We are now ready to prove that the PG-approach yields the following upper
bound.

######  Theorem 12.

$\operatorname{\textsc{RPQ-Test}}$, $\operatorname{\textsc{RPQ-Boole}}$ and
$\operatorname{\textsc{RPQ-Witness}}$ can be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

######  Proof 5.4.

We only show the upper bound for $\operatorname{\textsc{RPQ-Witness}}$ (due to
Theorem 11 it applies to $\operatorname{\textsc{RPQ-Test}}$ and
$\operatorname{\textsc{RPQ-Boole}}$ as well). To this end, let
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
be a graph database over $\Sigma$ and let $q$ be an $\mathsf{RPQ}$ over
$\Sigma$. We construct $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which,
according to Lemma 7, can be done in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$. In the following
considerations, we interpret $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ as
its underlying non-labelled graph.

We add to $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ a node
$v_{\mathsf{source}}$ with an arc to each $(u,p_{0})$ with $u\in
V_{\operatorname{\mathcal{D}}}$. This can be done in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||q|)$ as follows. First, we
add $v_{\mathsf{source}}$ to the list that represents
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which requires constant time.
Then, we move through the list that represents
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$ and every node $(u,p_{0})$ that
we encounter is added to the adjacency list for $v_{\mathsf{source}}$.

Next, we perform a special kind of BFS in $v_{\mathsf{source}}$. First, we
construct an array $S$ of size $|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|$
the entries of which can store values from
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)\cup\\{0\\}$ and which can be
addressed by the nodes from $V_{\boxtimes}(\operatorname{\mathcal{D}},q)$.
Moreover, $S$ is initialised with every entry storing $0$. Then, for every
$u\in V_{\operatorname{\mathcal{D}}}$, we set $S[(u,p_{0})]=u$. This can be
done in time
$\operatorname{O}(|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.
We perform a BFS from $v_{\textsf{source}}$ and whenever we traverse an arc
$((u,p),(u^{\prime},p^{\prime}))$, we set
$S[(u^{\prime},p^{\prime})]=S[(u,p)]$. This can be done in time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.
Since $S[(u,p_{0})]=u$ for every $u\in V_{\operatorname{\mathcal{D}}}$, we can
conclude by induction that, for every $(v,p)\in
V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, if $(v,p)$ is reachable from
some node $(u,p_{0})$, then $S[(v,p)]=u^{\prime}$ for some $u^{\prime}\in
V_{\operatorname{\mathcal{D}}}$ such that $(v,p)$ is reachable from
$(u^{\prime},p_{0})$, and if $(v,p)$ is not reachable from any node
$(u,p_{0})$, then $S[(u,p)]=0$. Consequently, if there is some $v\in
V_{\operatorname{\mathcal{D}}}$ with $S[(v,p_{f})]=u\neq 0$, then there is a
path from $(u,p_{0})$ to $(v,p_{f})$ in
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which, according to Lemma 8,
means that $(u,v)\in q(\operatorname{\mathcal{D}})$ and therefore, we can
produce the output $(u,v)$. On the other hand, if there is no $v\in
V_{\operatorname{\mathcal{D}}}$ with $S[(v,p_{f})]\neq 0$, then there are no
$u,v\in V_{\operatorname{\mathcal{D}}}$ with a path from $(u,p_{0})$ to
$(v,p_{f})$; thus, $q(\operatorname{\mathcal{D}})=\emptyset$. Checking whether
there is some $v\in V_{\operatorname{\mathcal{D}}}$ with $S[(v,p_{f})]\neq 0$
can be done in time $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$.

More interestingly, we can complement this upper bound with lower bounds as
follows.

######  Theorem 13.

If any of the problems $\operatorname{\textsc{RPQ-Test}}$,
$\operatorname{\textsc{RPQ-Boole}}$ and $\operatorname{\textsc{RPQ-Witness}}$
can be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2})$ or
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$ for some
$\epsilon>0$, then the $\operatorname{\textsf{OV}}$-hypothesis fails. This
lower bound also holds for the restriction to sparse graph databases.

######  Proof 5.5.

We prove the lower bound for $\operatorname{\textsc{RPQ-Test}}$ only, since by
Theorem 11 it also applies to $\operatorname{\textsc{RPQ-Witness}}$ and
$\operatorname{\textsc{RPQ-Boole}}$. We first devise a general reduction from
the $\operatorname{\textsf{OV}}$-problem to $\operatorname{\textsc{RPQ-Test}}$
(which is similar to the reduction from [6] used for proving conditional lower
bounds of regular expression matching):

Let $A=\\{\vec{a}^{1},\ldots,\vec{a}^{n}\\}$ and
$B=\\{\vec{b}^{1},\ldots,\vec{b}^{n}\\}$ be an instance for the
$\operatorname{\textsf{OV}}$-problem. We define an $\mathsf{RPQ}$ $q$ and a
graph database $\operatorname{\mathcal{D}}$ over the alphabet
$\Sigma=\\{0,1,\\#\\}$ as follows. For every $i\in[n]$, let
$w_{i}=\vec{b}^{i}[1]\vec{b}^{i}[2]\ldots\vec{b}^{i}[d]$, and let
$q=\\#(w_{1}\operatorname{\vee}w_{2}\operatorname{\vee}\ldots\operatorname{\vee}w_{n})\\#$.
Moreover, let
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$,
where $V_{\operatorname{\mathcal{D}}}$ contains nodes $s$ and $t$ and, for
every $i\in[n]$, nodes $v_{i,0},v_{i,1},\ldots,v_{i,d}$. For every $i\in[n]$
and $j\in\\{0\\}\cup[d-1]$, there is an arc from $v_{i,j}$ to $v_{i,j+1}$
labelled with $0$ and, if $\vec{a}^{i}[j+1]=0$, also an arc from $v_{i,j}$ to
$v_{i,j+1}$ labelled with $1$. Finally, for every $i\in[n]$, there are arcs
labelled with $\\#$ from $s$ to $v_{i,0}$ and from $v_{i,d}$ to $t$. It can be
easily verified that there are orthogonal $\vec{a}\in A$ and $\vec{b}\in B$ if
and only if $(s,t)\in q(\operatorname{\mathcal{D}})$. Moreover,
$|\operatorname{\mathcal{D}}|=\operatorname{O}(|A|d)=\operatorname{O}(nd)$ and
$|q|=\operatorname{O}(|B|d)=\operatorname{O}(nd)$, and, furthermore,
$\operatorname{\mathcal{D}}$ and $q$ can also be constructed in time
$\operatorname{O}(nd)$, and, since
$|E_{\operatorname{\mathcal{D}}}|=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$,
$\operatorname{\mathcal{D}}$ is a sparse graph database.

We now assume that $\operatorname{\textsc{RPQ-Test}}$ can be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$ for some
$\epsilon>0$. Let again $A=\\{\vec{a}^{1},\ldots,\vec{a}^{n}\\}$ and
$B=\\{\vec{b}^{1},\ldots,\vec{b}^{n}\\}$ be an instance for the
$\operatorname{\textsf{OV}}$-problem, and let $\epsilon^{\prime}$ be
arbitrarily chosen with $0<\epsilon^{\prime}<\epsilon$. We divide $A$ into
$A_{1},A_{2},\ldots,A_{\lceil n^{\epsilon^{\prime}}\rceil}$ with
$|A_{i}|=\lceil n^{1-\epsilon^{\prime}}\rceil$ for every $i\in[\lceil
n^{\epsilon^{\prime}}\rceil]$ and such that $\bigcup^{\lceil
n^{\epsilon^{\prime}}\rceil}_{i=1}A_{i}=A$. Obviously, $(A,B)$ is a positive
$\operatorname{\textsf{OV}}$-instance if and only if at least one of
$(A_{1},B),(A_{2},B),\ldots,(A_{\lceil n^{\epsilon^{\prime}}\rceil},B)$ is a
positive $\operatorname{\textsf{OV}}$-instance. We can now separately reduce
each $(A_{i},B)$ to an $\operatorname{\textsc{RPQ-Test}}$-instance
$(\operatorname{\mathcal{D}}_{i},q)$ as described above and we note that
$|\operatorname{\mathcal{D}}_{i}|=\operatorname{O}(|A_{i}|d)=\operatorname{O}(\lceil
n^{1-\epsilon^{\prime}}\rceil d)$ and
$|q|=\operatorname{O}(|B|d)=\operatorname{O}(nd)$. Then we solve each instance
in the assumed time bound
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$, which
requires total time of $\operatorname{O}(\lceil
n^{\epsilon^{\prime}}\rceil((\lceil n^{1-\epsilon^{\prime}}\rceil
d)^{2}+(nd)^{2-\epsilon})=\operatorname{O}((n^{2-\epsilon^{\prime}}+n^{2-\epsilon+\epsilon^{\prime}})\operatorname{\mathsf{poly}}(d))=\operatorname{O}(n^{2-(\epsilon-\epsilon^{\prime})})\operatorname{\mathsf{poly}}(d))$,
where $(\epsilon-\epsilon^{\prime})>0$. This contradicts the
$\operatorname{\textsf{OV}}$-hypothesis.

The assumption that $\operatorname{\textsc{RPQ-Test}}$ can be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2})$ for some
$\epsilon>0$ can be handled analogously. We divide again $A$ into
$A_{1},A_{2},\ldots,A_{\lceil n^{\epsilon^{\prime}}\rceil}$ as described
above, but then we reduce the $\operatorname{\textsf{OV}}$-instances
$(B,A_{1}),(B,A_{2}),\ldots,(B,A_{\lceil n^{\epsilon^{\prime}}\rceil})$ to the
$\operatorname{\textsc{RPQ-Test}}$-instances
$(\operatorname{\mathcal{D}},q_{1}),(\operatorname{\mathcal{D}},q_{2}),\ldots,(\operatorname{\mathcal{D}},q_{\lceil
n^{\epsilon^{\prime}}\rceil})$. Note that
$|\operatorname{\mathcal{D}}|=\operatorname{O}(nd)$ and
$|q_{i}|=\operatorname{O}(|A_{i}|d)=\operatorname{O}(\lceil
n^{1-\epsilon^{\prime}}\rceil d)$. By assumption, each of these instances can
be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q_{i}|^{2})=\operatorname{O}((nd)^{2-\epsilon}+(\lceil
n^{1-\epsilon^{\prime}}\rceil d)^{2})$, which again leads to a total running-
time of $\operatorname{O}(\lceil
n^{\epsilon^{\prime}}\rceil((nd)^{2-\epsilon}+(\lceil
n^{1-\epsilon^{\prime}}\rceil
d)^{2}))=\operatorname{O}(n^{2-(\epsilon-\epsilon^{\prime})})\operatorname{\mathsf{poly}}(d))$,
where $(\epsilon-\epsilon^{\prime})>0$. This contradicts the
$\operatorname{\textsf{OV}}$-hypothesis.

Since
$(|\operatorname{\mathcal{D}}||q|)^{1-\epsilon}\leq((\max\\{|\operatorname{\mathcal{D}}|,|q|\\})^{2})^{1-\epsilon}=\max\\{|\operatorname{\mathcal{D}}|^{2-2\epsilon},|q|^{2-2\epsilon}\\}\leq|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2}$,
Theorem 13 also rules out running times of the form
$\operatorname{O}((|\operatorname{\mathcal{D}}||q|)^{1-\epsilon})$ and
$\operatorname{O}(\max\\{|\operatorname{\mathcal{D}}|,|q|\\}^{2-\epsilon})$,
but does not exclude a running time of
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+f(|q|))$ with
$f(|q|)=\Omega(|q|^{2})$. However, for $\epsilon<1$ this is super-linear in
$|\operatorname{\mathcal{D}}|$ (and therefore inferior to
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$ under the assumption
$|q|\ll|\operatorname{\mathcal{D}}|$, i. e., that the database is much larger
than the query), and for $\epsilon=1$, we would obtain
$\operatorname{O}(|\operatorname{\mathcal{D}}|+f(|q|))$, which, under the
assumption $|q|\ll|\operatorname{\mathcal{D}}|$, is a small and arguably
negligible asymptotic improvement over
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

If the size of $\operatorname{\mathcal{D}}$ is expressed in terms of
$|V_{\operatorname{\mathcal{D}}}|$, then Theorem 12 also gives an upper bound
of $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{2}|q|)$. In this
regard, we can show the following lower bound.

######  Theorem 14.

If any of the problems $\operatorname{\textsc{RPQ-Test}}$,
$\operatorname{\textsc{RPQ-Boole}}$ and $\operatorname{\textsc{RPQ-Witness}}$
can be solved in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$
for some $\epsilon>0$, then the $\operatorname{\textsf{com-BMM}}$-hypothesis
fails.

######  Proof 5.6.

We prove the lower bound for $\operatorname{\textsc{RPQ-Boole}}$ only, since
by Theorem 11 it also applies to $\operatorname{\textsc{RPQ-Witness}}$ and
$\operatorname{\textsc{RPQ-Boole}}$.

We assume that $\operatorname{\textsc{RPQ-Boole}}$ can be solved by a
combinatorial algorithm in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$
for some $\epsilon>0$. We can then solve $\operatorname{\textsf{Triangle}}$ on
some instance $G=(V,E)$ with $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ as follows
(the result will then follow from the combinatorial subcubic equivalence of
$\operatorname{\textsf{BMM}}$ and $\operatorname{\textsf{Triangle}}$ (see
Section 4)). We construct the graph database $\operatorname{\mathcal{D}}$ over
$\\{\mathtt{a},\\#\\}$ with nodes

$V_{\operatorname{\mathcal{D}}}=\\{s^{\prime},t^{\prime}\\}\cup\\{s_{j},t_{j},\mid
1\leq j\leq n\\}\cup\\{(u,i)\mid 0\leq i\leq 3,u\in V\\}$

and arcs

$\displaystyle E_{\operatorname{\mathcal{D}}}=$
$\displaystyle\\{((u,i),\mathtt{a},(u^{\prime},i+1))\mid 0\leq i\leq
2,(u,u^{\prime})\in E\\}\>\cup$
$\displaystyle\\{(s^{\prime},\\#,s_{1}),(s_{i},\mathtt{a},s_{i+1}),(t_{i},\mathtt{a},t_{i+1}),(t_{n},\\#,t^{\prime})\mid
1\leq i\leq n-1\\}\>\cup$
$\displaystyle\\{(s_{i},\mathtt{a},(v_{i},0)),((v_{i},3),\mathtt{a},t_{i})\mid
1\leq i\leq n\\}\,.$

Furthermore, we define the $\mathsf{RPQ}$ $q=\\#\mathtt{a}^{n+4}\\#$.

By definition, $q(\operatorname{\mathcal{D}})=\\{(s^{\prime},t^{\prime})\\}$
or $q(\operatorname{\mathcal{D}})=\emptyset$. We call any path $p$ from
$s^{\prime}$ to $t^{\prime}$ an _$i$ -$j$-path_ for some $i,j\in[n]$ if there
are $\ell_{1},\ell_{2}\in[n]$ such that

$p=(s^{\prime},s_{1},\ldots,s_{i},v_{i,0},v_{\ell_{1},1},v_{\ell_{2},2},v_{j,3},t_{j},\ldots,t_{n},t^{\prime})\,.$

It can be easily seen that any path from $s^{\prime}$ to $t^{\prime}$ is an
$i$-$j$-path for some $i,j\in[n]$, and that any $i$-$j$-path is labelled with
$\\#\mathtt{a}^{i}\mathtt{a}^{3}\mathtt{a}^{n-j+1}\\#=\\#\mathtt{a}^{i+n-j+4}\\#$.
Hence, $q(\operatorname{\mathcal{D}})\neq\emptyset$ if and only if there is an
$i$-$i$-path for some $i\in[n]$. Since, for every $i\in[n]$, there is an
$i$-$i$-path if and only if there is a path
$(v_{i,0},v_{\ell_{1},1},v_{\ell_{2},2},v_{i,3})$, we see that, for every
$i\in[n]$, there is an $i$-$i$-path if and only if $G$ has triangle that
contains $v_{i}$. Consequently, $q(\operatorname{\mathcal{D}})\neq\emptyset$
if and only if $G$ has a triangle.

This means that by first constructing $\operatorname{\mathcal{D}}$ and $q$ in
time $\operatorname{O}(|D|+|q|)=\operatorname{O}(|G|+|V|)$ and then solving
$\operatorname{\textsc{RPQ-Boole}}$ for instance
$(\operatorname{\mathcal{D}},q)$ in the assumed time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$
for some $\epsilon>0$, means that we can solve
$\operatorname{\textsf{Triangle}}$ by a combinatorial algorithm in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})=\operatorname{O}(|V|^{3-\epsilon})$.

With Lemma 11, we can conclude that the assumptions that
$\operatorname{\textsc{RPQ-Test}}$ or $\operatorname{\textsc{RPQ-Witness}}$
can be solved in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$
for some $\epsilon>0$, leads to a combinatorial
$\operatorname{O}(|V|^{3-\epsilon})$ algorithm for
$\operatorname{\textsf{Triangle}}$ as well. Thus, due to the combinatorial
subcubic equivalence of $\operatorname{\textsf{BMM}}$ and
$\operatorname{\textsf{Triangle}}$ (see Section 4), there is a combinatorial
$\operatorname{O}(n^{3-\epsilon})$ algorithm for
$\operatorname{\textsf{BMM}}$, contradicting the $\operatorname{\textsf{com-
BMM}}$-hypothesis.

Since
$\operatorname{O}((|\operatorname{\mathcal{D}}||q|)^{1-\epsilon})\subseteq\operatorname{O}((|V_{\operatorname{\mathcal{D}}}|^{2}|q|)^{1-\epsilon})\subseteq\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$,
such running-times are also ruled out under the $\operatorname{\textsf{com-
BMM}}$-hypothesis. Especially, a combinatorial algorithm with running-time
$\operatorname{O}((|\operatorname{\mathcal{D}}||q|)^{1-\epsilon})$ refutes
_both_ the $\operatorname{\textsf{OV}}$\- and the $\operatorname{\textsf{com-
BMM}}$-hypothesis; thus, such an algorithm does not exist provided that at
least one of these hypotheses is true (basing lower bounds on several
hypotheses is common in fine-grained complexity, see, e. g., [3]).

The lower bounds discussed above are only meaningful for combined complexity.
However, the upper bound of Theorem 12 already yields the optimum of _linear_
data complexity.

###  5.2 Full Evaluation and Counting

The following upper bound is again a straightforward application of the PG-
approach.

######  Theorem 15.

$\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}||q|)$.

######  Proof 5.7.

Let
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
be a graph database over $\Sigma$ and let $q$ be an $\mathsf{RPQ}$ over
$\Sigma$. We construct $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which,
according to Lemma 7, can be done in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$. We interpret
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ as its underlying non-labelled
graph. According to Lemma 8, we can now compute
$q(\operatorname{\mathcal{D}})$ by performing a BFS from each node $(u,p_{0})$
with $u\in V_{\operatorname{\mathcal{D}}}$. Each such BFS requires time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$,
which means that the total running-time is
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}||q|)$.

Instead of using graph-searching techniques on
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, we could also compute the
complete transitive closure of $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$
with fast matrix multiplication.

######  Theorem 16.

If $\operatorname{\textsf{BMM}}$ can be solved in time
$\operatorname{O}(n^{\omega})$ with $\omega\geq 2$, then
$\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{\omega}|q|^{\omega})$.

######  Proof 5.8.

We assume that $\operatorname{\textsf{BMM}}$ can be solved in time
$\operatorname{O}(n^{\omega})$. Let
$\operatorname{\mathcal{D}}=(V_{\operatorname{\mathcal{D}}},E_{\operatorname{\mathcal{D}}})$
be a graph database over $\Sigma$ and let $q$ be an $\mathsf{RPQ}$ over
$\Sigma$. We construct $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which,
according to Lemma 7, can be done in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$, and we interpret it as
its underlying non-labelled graph. Obviously, we can turn the adjacency list-
based representation of $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ into an
adjacency matrix-based representation in time
$\operatorname{O}(|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|^{2})=\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{2})=\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{\omega})$.
Then, we compute the transitive closure
$(E_{\boxtimes}(\operatorname{\mathcal{D}},q))^{*}$ of
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which can be done in time
$\operatorname{O}(|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|^{\omega})=\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{\omega})$
(see [45]). In order to obtain $q(\operatorname{\mathcal{D}})$, it is
sufficient to go through all elements
$((u,p),(v,p^{\prime}))\in(E_{\boxtimes}(\operatorname{\mathcal{D}},q))^{*}$
and add $(u,v)$ to a new set if and only if $p=p_{0}$ and $p^{\prime}=p_{f}$
(see Lemma 8). Since
$|(E_{\boxtimes}(\operatorname{\mathcal{D}},q))^{*}|\leq|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|^{2}=\operatorname{O}(|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|^{\omega})=\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{\omega})$,
this can be done in time
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||q|)^{\omega})$.

We mention this theoretical upper bound for completeness, but stress the fact
that our main interest lies in _combinatorial_ algorithms. In addition to the
limitation that algorithms for fast matrix multiplication are not practical,
we also observe that the approach of Theorem 16 is only better if the graph
database is not too sparse, i. e., only if
$|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|=\Omega(|V_{\operatorname{\mathcal{D}}}|^{\omega})$.

Next, we investigate the question whether
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}||q|)$
is optimal for $\operatorname{\textsc{RPQ-Eval}}$ at least with respect to
combinatorial algorithms. Since for $\operatorname{\textsc{RPQ-Eval}}$ the PG-
approach does not yield an algorithm that is linear in data complexity (like
it was the case with respect to the problems of Section 5.1), the question
arises whether the
$|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|$ part can be
improved at the cost of spending more time in $|q|$. It seems necessary that
respective _data complexity lower bounds_ need reductions that do not use $q$
to represent a non-constant part of the instance, as it was the case for both
the $\operatorname{\textsf{OV}}$ and the $\operatorname{\textsf{Triangle}}$
reduction from Section 5.1.

It is not difficult to see that multiplying two $n\times n$ Boolean matrices
reduces to $\operatorname{\textsc{RPQ-Eval}}$ as formally stated by the next
lemma.

######  Lemma 17.

If $\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{\omega}f(|q|))$ for some
function $f$ and $\omega\geq 2$, then $\operatorname{\textsf{BMM}}$ can be
solved in time $\operatorname{O}(n^{\omega})$.

######  Proof 5.9.

We assume that $\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{\omega}f(|q|))$ for some
function $f$. Let $A$ and $B$ be $n\times n$ Boolean matrices. Then we
construct the graph database $\operatorname{\mathcal{D}}_{A,B}$ over
$\\{\mathtt{a}\\}$ with
$V_{\operatorname{\mathcal{D}}_{A,B}}=\\{(i,0),(i,1),(i,2)\mid i\in[n]\\}$ and
$E_{\operatorname{\mathcal{D}}_{A,B}}=\\{((i,0),\mathtt{a},(j,1))\mid
A[i,j]=1\\}\cup\\{((i,1),\mathtt{a},(j,2))\mid B[i,j]=1\\}$, and the
$\mathsf{RPQ}$ $q=\mathtt{a}\mathtt{a}$. Obviously,
$q(\operatorname{\mathcal{D}}_{A,B})\subseteq\\{((i,0),(j,2))\mid
i,j\in[n]\\}$ and $((i,0),(j,2))\in q(\operatorname{\mathcal{D}}_{A,B})$ if
and only if $(A\times B)[i,j]=1$. Hence, we can construct $A\times B$ from
$q(\operatorname{\mathcal{D}}_{A,B})$ in time
$\operatorname{O}(|q(\operatorname{\mathcal{D}}_{A,B})|)=\operatorname{O}(n^{2})$.
By assumption, the set $q(\operatorname{\mathcal{D}})$ can be computed in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}_{A,B}}|^{\omega}f(|q|))=\operatorname{O}(n^{\omega}f(2))=\operatorname{O}(n^{\omega})$.

From this, we can conclude the following lower bound.

######  Theorem 18.

If $\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon}f(|q|))$
for some function $f$ and some $\epsilon>0$, then the
$\operatorname{\textsf{com-BMM}}$-hypothesis fails.

######  Proof 5.10.

If $\operatorname{\textsc{RPQ-Eval}}$ can be solved by a combinatorial
algorithm in time
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon}f(|q|))$
for some function $f$ and some $\epsilon>0$, then, since
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon}f(|q|))=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$,
Lemma 17 implies that $\operatorname{\textsf{BMM}}$ can be solved in time
$\operatorname{O}(n^{3-\epsilon})$. Thus, the $\operatorname{\textsf{com-
BMM}}$-hypothesis fails.

If we drop the restriction to combinatorial algorithms, we can nevertheless
show (with more or less the same construction) that linear time in data
complexity is impossible, unless the $\operatorname{\textsf{SBMM}}$-hypothesis
fails. However, since the size of the output $q(\operatorname{\mathcal{D}})$
might be super-linear in $|\operatorname{\mathcal{D}}|$, we should interpret
_linear_ as linear in
$|\operatorname{\mathcal{D}}|+|q(\operatorname{\mathcal{D}})|$.

######  Lemma 19.

If $\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}((|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)^{\omega}f(|q|))$
for some function $f$ and $\omega\geq 1$, then $\operatorname{\textsf{SBMM}}$
can be solved in time $\operatorname{O}(m^{\omega})$.

######  Proof 5.11.

We assume that $\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}((|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)^{\omega}f(|q|))$
for some function $f$. Let $A$ and $B$ be $n\times n$ Boolean matrices given
as sets of their $1$-entries and let $m$ be the total number of $1$-entries in
$A$, $B$ and $A\times B$. Then we can construct a graph database
$\operatorname{\mathcal{D}}_{A,B}$ over $\\{\mathtt{a}\\}$ as follows. For
every $i\in[n]$, the set $V_{\operatorname{\mathcal{D}}_{A,B}}$ contains a
node $(i,0)$ if the $i^{\text{th}}$ row of $A$ contains at least one
$1$-entry, a node $(i,1)$ if the $i^{\text{th}}$ column of $A$ contains at
least one $1$-entry or the $i^{\text{th}}$ row of $B$ contains at least one
$1$-entry, and a node $(i,2)$ if the $i^{\text{th}}$ column of $B$ contains at
least one $1$-entry. The set of arcs is defined by
$E_{\operatorname{\mathcal{D}}_{A,B}}=\\{((i,0),\mathtt{a},(j,1))\mid
A[i,j]=1\\}\cup\\{((i,1),\mathtt{a},(j,2))\mid B[i,j]=1\\}$. We observe that
$|E_{\operatorname{\mathcal{D}}_{A,B}}|=\operatorname{O}(m)$ and, since every
node in $V_{\operatorname{\mathcal{D}}_{A,B}}$ has degree at least $1$,
$|V_{\operatorname{\mathcal{D}}_{A,B}}|=\operatorname{O}(|E_{\operatorname{\mathcal{D}}_{A,B}}|)$.
Consequently, $|\operatorname{\mathcal{D}}_{A,B}|=\operatorname{O}(m)$ and
$\operatorname{\mathcal{D}}_{A,B}$ can be constructed in time
$\operatorname{O}(m)$. Further, we define $q=\mathtt{a}\mathtt{a}$.

We can observe that
$q(\operatorname{\mathcal{D}}_{A,B})\subseteq\\{((i,0),(j,2))\mid
i,j\in[n]\\}$ and, for every $i,j\in[n]$, $((i,0),(j,2))\in
q(\operatorname{\mathcal{D}}_{A,B})$ if and only if $(A\times B)[i,j]=1$.
Thus, $|q(\operatorname{\mathcal{D}}_{A,B})|=\operatorname{O}(m)$ and we can
obtain a set of exactly the $1$-entries of $A\times B$ from
$q(\operatorname{\mathcal{D}}_{A,B})$ in time
$\operatorname{O}(|q(\operatorname{\mathcal{D}}_{A,B})|)=\operatorname{O}(m)$.

By assumption, we can compute $q(\operatorname{\mathcal{D}}_{A,B})$ in time
$\operatorname{O}((|q(\operatorname{\mathcal{D}}_{A,B})|+|\operatorname{\mathcal{D}}_{A,B}|)^{\omega}f(|q|))$
for some function $f$ and $\omega\geq 1$. This implies that we can obtain a
set of exactly the $1$-entries of $A\times B$ in time
$\operatorname{O}((|q(\operatorname{\mathcal{D}}_{A,B})|+|\operatorname{\mathcal{D}}_{A,B}|)^{\omega}f(|q|))=\operatorname{O}(m^{\omega}f(2))=\operatorname{O}(m^{\omega})$.

Lemma 19 directly implies the following lower bound.

######  Theorem 20.

If $\operatorname{\textsc{RPQ-Eval}}$ can be solved in time
$\operatorname{O}((|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)f(|q|))$
for some function $f$, then the $\operatorname{\textsf{SBMM}}$-hypothesis
fails.

Surprisingly, we can obtain a more complete picture for the problem
$\operatorname{\textsc{RPQ-Count}}$. First, we observe that obviously all
upper bounds carry over from $\operatorname{\textsc{RPQ-Eval}}$ to
$\operatorname{\textsc{RPQ-Count}}$. On the other hand, a combinatorial
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon}f(q))$
algorithm or a general
$\operatorname{O}((|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)f(|q|))$
algorithm for $\operatorname{\textsc{RPQ-Count}}$ does not seem to help for
solving Boolean matrix multiplication (and therefore, the lower bounds do not
carry over). Fortunately, it turns out that $\operatorname{\textsf{OV}}$ is a
suitable problem to reduce to $\operatorname{\textsc{RPQ-Count}}$, although by
a rather different reduction compared to the one used for Theorem 13.

######  Theorem 21.

If $\operatorname{\textsc{RPQ-Count}}$ can be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}f(|q|))$ for some
function $f$ and $\epsilon>0$, then the
$\operatorname{\textsf{OV}}$-hypothesis fails.

######  Proof 5.12.

We assume that $\operatorname{\textsc{RPQ-Count}}$ can be solved in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}f(|q|))$ for some
function $f$ and $\epsilon>0$. Let
$A=\\{\vec{a}_{1},\vec{a}_{2},\ldots,\vec{a}_{n}\\}$ and
$B=\\{\vec{b}_{1},\vec{b}_{2},\ldots,\vec{b}_{n}\\}$ be an
$\operatorname{\textsf{OV}}$-instance, i. e., for every $i\in[n]$,
$\vec{a}_{i}$ and $\vec{b}_{i}$ are $d$-dimensional Boolean vectors. Now let
$A^{\prime}$ be the Boolean matrix having rows
$\vec{a}_{1},\vec{a}_{2},\ldots,\vec{a}_{n}$ and let $B^{\prime}$ be the
Boolean matrix having columns $\vec{b}_{1},\vec{b}_{2},\ldots,\vec{b}_{n}$. It
can be easily seen that, for every $i,j\in[n]$, $(A^{\prime}\times
B^{\prime})[i,j]=0$ if and only if $\vec{a}_{i}$ and $\vec{b}_{j}$ are
orthogonal. Moreover, $A^{\prime}$ and $B^{\prime}$ can be constructed in time
$\operatorname{O}(nd)$.

Next, we construct $\operatorname{\mathcal{D}}_{A^{\prime},B^{\prime}}$ as in
the proof of Lemma 17, and we note that
$V_{\operatorname{\mathcal{D}}_{A^{\prime},B^{\prime}}}=\operatorname{O}(n+d)$
and
$E_{\operatorname{\mathcal{D}}_{A^{\prime},B^{\prime}}}=\operatorname{O}(nd)$;
in particular, we construct
$\operatorname{\mathcal{D}}_{A^{\prime},B^{\prime}}$ in time
$\operatorname{O}(nd)$. Since, for every $i,j\in[n]$, $((i,0),(j,2))\in
q(\operatorname{\mathcal{D}}_{A,B})$ if and only if $(A\times B)[i,j]=1$, we
know that, for every $i,j\in[n]$, $((i,0),(j,2))\in
q(\operatorname{\mathcal{D}}_{A,B})$ if and only if $\vec{a}_{i}$ and
$\vec{b}_{j}$ are not orthogonal. Furthermore, since
$q(\operatorname{\mathcal{D}}_{A,B})\subseteq\\{((i,0),(j,2))\mid
i,j\in[n]\\}$, $|q(\operatorname{\mathcal{D}}_{A,B})|=n^{2}$ if and only if
there are no $\vec{a}\in A$ and $\vec{b}\in B$ that are orthogonal.
Consequently, we can check whether there are no $\vec{a}\in A$ and $\vec{b}\in
B$ that are orthogonal by computing $|q(\operatorname{\mathcal{D}}_{A,B})|$,
which, by assumption, can be done in time
$\operatorname{O}(|\operatorname{\mathcal{D}}_{A,B}|^{2-\epsilon}f(|q|))=\operatorname{O}((nd)^{2-\epsilon}f(2))=\operatorname{O}(n^{2-\epsilon}\operatorname{\mathsf{poly}}(d))$.

Since Theorem 21 also excludes running time
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)^{1-\epsilon}f(|q|))$
for any function $f$ and $\epsilon>0$ (without restriction to combinatorial
algorithms), it also shows that, subject to the
$\operatorname{\textsf{OV}}$-hypothesis,
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)$
is a tight bound for the data complexity of $\operatorname{\textsc{RPQ-
Count}}$.

##  6 Bounds for the Enumeration of $\mathsf{RPQ}$s

By using the PG-approach for enumeration, we can obtain the following upper
bound.

######  Theorem 22.

Sorted $\operatorname{\textsc{RPQ-Enum}}$ can be solved with
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$ delay and
$\operatorname{O}(1)$ updates.

######  Proof 6.1.

Let $\operatorname{\mathcal{D}}$ be a graph database over $\Sigma$, let $q$ be
an $\mathsf{RPQ}$ over $\Sigma$ and let $\preceq$ be the order on
$V_{\operatorname{\mathcal{D}}}$. We assume that
$V_{\operatorname{\mathcal{D}}}=[n]$ with $1\preceq 2\preceq\ldots\preceq n$
(see Lemma 5).
Preprocessing:

  1. 1.

We compute $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which, according to
Lemma 7, can be done in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$, and we interpret
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ as its underlying non-labelled
graph.

  2. 2.

We construct two arrays $S$ and $T$ of size $|V_{\operatorname{\mathcal{D}}}|$
such that, for every $i\in[n]$, $S[i]=(i,p_{0})$ and $T[i]=(i,p_{f})$. Note
that this also means that pointers to the corresponding adjacency lists are
stored along with the nodes in $S$ and $T$. Computing $S$ and $T$ can be done
in time $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||q|)$ as follows. We
move through the list that represents
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$ and for every node $(i,p_{0})$,
we set $S[i]=(i,p_{0})$, and for every node $(i,p_{f})$, we set
$T[i]=(i,p_{f})$.

  3. 3.

We modify $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ by adding a new node
$v_{\mathsf{sink}}$ with an arc from each $(i,p_{f})$ with $i\in[n]$. This can
be done in time $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ as
follows. We first add $v_{\mathsf{sink}}$ to the list that represents
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which requires constant time.
Then, for every node $(i,p_{f})$ of $T$, we add $v_{\mathsf{sink}}$ to the
adjacency list for $(i,p_{f})$. Again, this can be done in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$.

  4. 4.

We obtain $(G_{\boxtimes}(\operatorname{\mathcal{D}},q))^{R}$, which,
according to Lemma 2, can be done in time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.
Then we initialise a Boolean array $S^{\prime}$ of size
$|V_{\operatorname{\mathcal{D}}}|$ with entries $0$ everywhere. We then
perform a BFS in $(G_{\boxtimes}(\operatorname{\mathcal{D}},q))^{R}$ starting
in $v_{\mathsf{sink}}$ and, for every visited node $(i,p_{0})$, we set
$S^{\prime}[i]=1$. For every $i\in V_{\operatorname{\mathcal{D}}}$,
$S^{\prime}[i]=1$ if and only if $v_{\mathsf{sink}}$ and therefore some node
from $T$ can be reached from $(i,p_{0})$. This step can be done in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

  5. 5.

We initialise a Boolean array $T^{\prime}$ of size
$|V_{\operatorname{\mathcal{D}}}|$ with entries $0$ everywhere, which can be
done in time $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$.

Enumeration: In the enumeration phase, we carry out the following procedure.

  * •

For every $i=1,2,\ldots,n$:

    * –

If $S^{\prime}[i]=1$, then

      * *

perform a BFS in $(i,p_{0})$ and for every $(j,p_{f})$ that we visit, we set
$T^{\prime}[j]=1$,

      * *

for every $j=1,2,\ldots,n$: produce $(i,j)$ as output if $T^{\prime}[j]=1$,

      * *

Set all entries of $T^{\prime}$ to $0$.

Correctness: In the enumeration phase we perform a BFS from each $(i,p_{0})$
that can reach at least one node $(j,p_{f})$ (i. e., from each $(i,p_{0})$
with $S^{\prime}[i]=1$) and after termination of this BFS, we output exactly
the pairs $(i,j)$ for which $(j,p_{f})$ is visited in this BFS. This directly
shows that we correctly enumerate $q(\operatorname{\mathcal{D}})$ without
repetitions. Furthermore, since we consider the start vertices for the BFSs in
increasing order with respect to $\preceq$, and since after termination of a
BFS started in $(i,p_{0})$ we output the pairs $(i,j)$ in increasing order by
the second element, the enumeration is sorted by lexicographic order.

Next, we estimate the delay of the enumeration. Each iteration of the main
loop with $S^{\prime}[i]=1$ requires time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)$ for
performing the BFS, $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ for
producing the output and $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$
for resetting $T^{\prime}$. Thus, the total running-time is
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$
in the case that $S^{\prime}[i]=1$. If, on the other hand, $S^{\prime}[i]=0$,
then the iteration terminates after constant time. Moreover, since
$S^{\prime}[i]=1$ implies that $i$ can reach $v_{\mathsf{sink}}$ and since
$v_{\mathsf{sink}}$ can only be reached via some $(j,p_{f})$, we produce at
least one output in such an iteration. Consequently, the delay between two
outputs is bounded by the total running time for one iteration of the main
loop, which is $\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.
Updates: If $\operatorname{\mathcal{D}}$ is changed to
$\operatorname{\mathcal{D}}^{\prime}$ by an update, then we can again perform
the whole preprocessing (with respect to
$\operatorname{\mathcal{D}}^{\prime}$) followed by the enumeration procedure.
Technically, the preprocessing is done as a first step of the enumeration
procedure (since our algorithmic framework does not allow to re-run the
preprocessing after an update), which is possible since its running time of
$\operatorname{O}(|\operatorname{\mathcal{D}}^{\prime}||q|)$ is completely
subsumed by the time available for the first delay.

This enumeration algorithm is easy to implement and has some nice features
like linear preprocessing (in data complexity), sorted enumeration and
constant updates. Unfortunately, these features come more or less for free
with the disappointing delay bound. Is the PG-approach therefore the wrong
tool for $\mathsf{RPQ}$-enumeration? Or can we give evidence that linear delay
is a barrier we cannot break? The rest of this work is devoted to this
question.

Since running an algorithm for $\operatorname{\textsc{RPQ-Enum}}$ until we get
the first element yields an algorithm for $\operatorname{\textsc{RPQ-Boole}}$
(with preprocessing plus delay as running time), and since running such an
algorithm completely solves $\operatorname{\textsc{RPQ-Eval}}$ in time
preprocessing plus $|q(\operatorname{\mathcal{D}})|$ times delay, we can
inherit several lower bounds directly from Section 5.

######  Theorem 23.

If, for some function $f$ and $\epsilon\geq 0$, $\operatorname{\textsc{RPQ-
Enum}}$ can be solved with

  1. 1.

delay $\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2})$ or
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$, then
the $\operatorname{\textsf{OV}}$-hypothesis fails.

  2. 2.

delay
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$,
then the $\operatorname{\textsf{com-BMM}}$-hypothesis fails.

  3. 3.

preprocessing $\operatorname{O}(|\operatorname{\mathcal{D}}|f(|q|))$ and delay
$\operatorname{O}(f(|q|))$, then the $\operatorname{\textsf{SBMM}}$-hypothesis
fails.

  4. 4.

preprocessing
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$ and
delay $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))$,
then the $\operatorname{\textsf{com-BMM}}$-hypothesis fails.

######  Proof 6.2.

We prove the four lower bounds of Theorem 23 separately.

  1. 1.

Let us assume that $\operatorname{\textsc{RPQ-Enum}}$ can be solved with delay
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2})$ (or
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$) for
some $\epsilon>0$. Then we can solve $\operatorname{\textsc{RPQ-Boole}}$ on an
instance $(\operatorname{\mathcal{D}},q)$ as follows. We run the assumed
enumeration algorithm for $\operatorname{\textsc{RPQ-Enum}}$ on
$(\operatorname{\mathcal{D}},q)$, but stop as soon as the first pair (if any)
is produced. By assumption, this requires time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2})$ (or
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$).
Moreover, $(\operatorname{\mathcal{D}},q)$ is a positive
$\operatorname{\textsc{RPQ-Boole}}$ instance if and only if the interrupted
enumeration algorithm produces a pair. Thus, we can solve
$\operatorname{\textsc{RPQ-Boole}}$ in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2-\epsilon}+|q|^{2})$ (or
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{2}+|q|^{2-\epsilon})$) for
some $\epsilon>0$, which, according to Theorem 13 means that the
$\operatorname{\textsf{OV}}$-hypothesis fails.

  2. 2.

Let us assume that $\operatorname{\textsc{RPQ-Enum}}$ can be solved with delay
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$
for some $\epsilon>0$. Then we can solve $\operatorname{\textsc{RPQ-Boole}}$
on an instance $(\operatorname{\mathcal{D}},q)$ as follows. We run the assumed
enumeration algorithm for $\operatorname{\textsc{RPQ-Enum}}$ on
$(\operatorname{\mathcal{D}},q)$, but stop as soon as the first pair (if any)
is produced. By assumption, this requires time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$.
Moreover, $(\operatorname{\mathcal{D}},q)$ is a positive
$\operatorname{\textsc{RPQ-Boole}}$ instance if and only if the interrupted
enumeration algorithm produces a pair. Thus, we can solve
$\operatorname{\textsc{RPQ-Boole}}$ in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}+|q|^{3-\epsilon})$
for some $\epsilon>0$, which, according to Theorem 14 means that the
$\operatorname{\textsf{com-BMM}}$-hypothesis fails.

  3. 3.

We assume that $\operatorname{\textsc{RPQ-Enum}}$ can be solved with
preprocessing $\operatorname{O}(|\operatorname{\mathcal{D}}|f(|q|))$ and delay
$\operatorname{O}(f(|q|))$ for some function $f$. By completely running the
corresponding enumeration algorithm, we can solve $\operatorname{\textsc{RPQ-
Eval}}$ in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|f(|q|))+\operatorname{O}(|q(\operatorname{\mathcal{D}})|f(|q|))=\operatorname{O}((|q(\operatorname{\mathcal{D}})|+|\operatorname{\mathcal{D}}|)f(|q|))$.
According to Theorem 20 this means that
$\operatorname{\textsf{SBMM}}$-hypothesis fails.

  4. 4.

Assume that $\operatorname{\textsc{RPQ-Enum}}$ can be solved with
preprocessing
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$ and
delay $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))$
for some function $f$ and $\epsilon\geq 0$. By completely running the
corresponding enumeration algorithm, we can solve $\operatorname{\textsc{RPQ-
Eval}}$ in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|)+|q(\operatorname{\mathcal{D}})||V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$.
According to Lemma 17, this means that $\operatorname{\textsf{BMM}}$ can be
solved in time $\operatorname{O}(n^{3-\epsilon})$.

The first two bounds only tell us that we might not be able to lower the delay
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$ in terms of combined
complexity. While this point of view was justified for the problems discussed
in Section 5, it does not say anything regarding delays of the form
$\operatorname{O}(|\operatorname{\mathcal{D}}|^{1-\epsilon}f(|q|))$. The third
bound, conditional to the $\operatorname{\textsf{SBMM}}$-hypothesis, is much
more relevant, since it suggests that the optimum of linear preprocessing and
constant delay is not reachable. For combinatorial algorithms, the fourth
bound at least answers our main question with $|\operatorname{\mathcal{D}}|$
replaced by $|V_{\operatorname{\mathcal{D}}}|$: with linear preprocessing, we
cannot get below a delay of
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$.

These lower bounds can be improved significantly, if we also want to handle
updates (within some reasonable time bounds).

######  Theorem 24.

If $\operatorname{\textsc{RPQ-Enum}}$ can be solved with

  1. 1.

arbitrary preprocessing,
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))$
updates and
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))$ delay
for some function $f$ and $\epsilon\geq 0$, then the
$\operatorname{\textsf{OMv}}$-hypothesis fails.

  2. 2.

$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$
preprocessing,
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{2-\epsilon}f(|q|))$
updates and
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{2-\epsilon}f(|q|))$ delay
for some function $f$ and $\epsilon\geq 0$, then the
$\operatorname{\textsf{com-BMM}}$-hypothesis fails.

######  Proof 6.3.

We prove the two parts of Theorem 24 separately.

  1. 1.

Assume that there is an algorithm that solves $\operatorname{\textsc{RPQ-
Enum}}$ with preprocessing $t_{p}$, delay $t_{d}$ and update time $t_{u}$. We
can then solve $\operatorname{\textsf{OMv}}$ on some instance $M$ and
$\vec{v}^{1},\vec{v}^{2},\ldots,\vec{v}^{n}$ as follows. We initialise the
empty graph database (over alphabet $\\{\mathtt{a}\\}$) and the $\mathsf{RPQ}$
$q=\mathtt{a}\mathtt{a}$, and then we perform the preprocessing in constant
time. Then, by performing $\operatorname{O}(n^{2})$ updates, we transform the
current graph database into the graph database
$\operatorname{\mathcal{D}}_{M,\vec{v}^{1}}$ over $\\{\mathtt{a}\\}$ with
nodes $\\{u_{i},v_{i},w\mid 1\leq i\leq n\\}$ and arcs
$\\{(u_{i},\mathtt{a},v_{j})\mid
M[i,j]=1\\}\cup\\{(v_{j},\mathtt{a},w)\mid\vec{v}_{1}[j]=1\\}$, which requires
time $\operatorname{O}(n^{2}t_{u})$. Since
$q(\operatorname{\mathcal{D}}_{M,\vec{v}^{1}})=\\{(u_{i},w)\mid(M\vec{v}^{1})[i]=1\\}$,
we can now compute $M\vec{v}^{1}$ by enumerating
$q(\operatorname{\mathcal{D}}_{M,\vec{v}^{1}})$ in time
$\operatorname{O}(nt_{d})$. In the same way, for every $i$ with $2\leq i\leq
n$, we can obtain $M\vec{v}^{i}$ by enumerating
$q(\operatorname{\mathcal{D}}_{M,\vec{v}^{i}})$, where every
$\operatorname{\mathcal{D}}_{M,\vec{v}^{i+1}}$ can be obtained from
$\operatorname{\mathcal{D}}_{M,\vec{v}^{i}}$ by $n$ updates in time
$\operatorname{O}(nt_{u})$. Consequently, the whole procedure requires time
$\operatorname{O}(n^{2}t_{u}+nt_{d}+(n-1)(nt_{u}+nt_{d}))$, and the number of
nodes always satisfies
$|V_{\operatorname{\mathcal{D}}}|\in\operatorname{O}(n)$. With the assumption
that
$t_{d}=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))$
and
$t_{u}=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))$
for some $\epsilon>0$ and some function $f$, this leads to a total running-
time of
$\operatorname{O}(n^{2}|V_{\operatorname{\mathcal{D}}}|^{1-\epsilon}f(|q|))=\operatorname{O}(n^{3-\epsilon})$.

  2. 2.

Assume that there is an algorithm that solves $\operatorname{\textsc{RPQ-
Enum}}$ with preprocessing $t_{p}$, delay $t_{d}$ and update time $t_{u}$. We
can then solve $\operatorname{\textsf{Triangle}}$ on some instance $G=(V,E)$
with $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ as follows (the result will then
follow from the combinatorial subcubic equivalence of
$\operatorname{\textsf{BMM}}$ and $\operatorname{\textsf{Triangle}}$ (see
Section 4)). We construct the graph database
$\operatorname{\mathcal{D}}_{v_{1}}$ over $\\{\mathtt{a}\\}$ with nodes
$V_{\operatorname{\mathcal{D}}_{v_{1}}}=\\{s,t,(u,i)\mid 0\leq i\leq 3,u\in
V\\}$ and arcs
$E_{\operatorname{\mathcal{D}}_{v_{1}}}=\\{((u,i),\mathtt{a},(u^{\prime},i+1))\mid
0\leq i\leq 2,(u,u^{\prime})\in
E\\}\cup\\{(s,\mathtt{a},(v_{1},0)),((v_{1},3),\mathtt{a},t)\\}$. Furthermore,
we define the $\mathsf{RPQ}$
$q=\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}$. It can be easily seen
that $q(\operatorname{\mathcal{D}}_{v_{1}})=\\{(s,t)\\}$ if there is a
triangle that contains $v_{1}$, and
$q(\operatorname{\mathcal{D}}_{v_{1}})=\emptyset$ otherwise. In particular,
this means that enumerating $q(\operatorname{\mathcal{D}}_{v_{1}})$ can be
done in time $\operatorname{O}(t_{d})$.

Analogously, by constructing
$\operatorname{\mathcal{D}}_{v_{2}},\ldots,\operatorname{\mathcal{D}}_{v_{n}}$
and enumerating
$q(\operatorname{\mathcal{D}}_{v_{2}}),\ldots,q(\operatorname{\mathcal{D}}_{v_{n}})$,
we can therefore check whether $G$ contains a triangle. For every $i$ with
$2\leq i\leq n$, we can obtain $\operatorname{\mathcal{D}}_{v_{i+1}}$ from
$\operatorname{\mathcal{D}}_{v_{i}}$ by performing a constant number of
updates (we just have to remove arcs $(s,\mathtt{a},(v_{i},0))$ and
$((v_{i},3),\mathtt{a},t)$ and instead add arcs $(s,\mathtt{a},(v_{i+1},0))$
and $((v_{i+1},3),\mathtt{a},t)$). Consequently, this whole procedure requires
the preprocessing for a graph database with $\operatorname{O}(|V|)$ nodes and
$\operatorname{O}(|E|)$ arcs, $|V|$ many delays and $|V|$ many updates, i. e.,
the total running time of this procedure is
$\operatorname{O}(t_{p}+|V|(t_{d}+t_{u}))$. With the assumption that
$t_{p}=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$
and
$t_{d}=t_{u}=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{2-\epsilon}f(|q|))$
for some $\epsilon>0$ and some function $f$, this leads to a total running-
time of
$\operatorname{O}(|V|^{3-\epsilon}f(|q|)+|V||V_{\operatorname{\mathcal{D}}}|^{2-\epsilon}f(|q|))=\operatorname{O}(|V|^{3-\epsilon})$.

The first bound rules out that we can get below
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ for delay _and_ update
time, regardless of the preprocessing; the second one analogously rules out
anything below $\operatorname{O}(|\operatorname{\mathcal{D}}|)$ (for
combinatorial algorithms and linear preprocessing). While all these lower
bounds suggest that improving on the linear delay may be rather difficult,
they leave the following case open.

Can $\operatorname{\textsc{RPQ-Enum}}$ be solved with
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$ preprocessing and
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ delay in data complexity?

What is a reasonable conjecture with respect to this question? A combinatorial
algorithm that answers it in the positive does not seem to have any unlikely
consequences. Indeed, it would just entail an
$\operatorname{O}(|\operatorname{\mathcal{D}}||V_{\operatorname{\mathcal{D}}}|)$
algorithm for $\operatorname{\textsc{RPQ-Eval}}$ (which exactly fits to
Theorem 15), an $\operatorname{O}(|V||G|)$ algorithm for computing transitive
closures and an $O(n^{3})$ algorithm for multiplying Boolean $n\times n$
matrices, which is the state of the art for combinatorial algorithms (this is
due to the obvious reductions from these problems to
$\operatorname{\textsc{RPQ-Enum}}$). However, since Question 6 is about
enumeration, a positive answer also means that after $\operatorname{O}(|G|)$
preprocessing, we can enumerate the transitive closure of a graph with delay
$\operatorname{O}(|V|)$, and that after $\operatorname{O}(n^{2})$
preprocessing, all $1$-entries of the Boolean matrix multiplication can be
enumerated with delay $\operatorname{O}(n)$. Are such enumeration algorithms
unlikely, so that we should rather expect a negative answer to Question 6? In
fact not, since for the simple $\mathsf{RPQ}$s $q=\mathtt{a}^{*}$ or
$q=\mathtt{a}\mathtt{a}$, which are sufficient to encode transitive closures
and Boolean matrix multiplications, linear preprocessing and delay
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ is indeed possible, as we
shall obtain as byproducts of the results in the next section.

We close this section by the following remark that points out some similarity
(and differences) of reductions used in Sections 5 and 6.

######  Remark 25.

As already mentioned in Section 5.1, the reduction used for the combined
complexity lower bounds of Theorems 13 (and therefore Point $1$ of Theorem 23)
is similar to the reduction from [6] used for proving conditional lower bounds
of regular expression matching. Also note that [28] improves the bound of [6]
by showing that sub-quadratic algorithms for finding a path in a graph
labelled by a given pattern string are most likely impossible, even if we are
allowed to build indexes in polynomial time. The paper [27] strengthens the
bound of [6] by restricting the structure of the graphs. Moreover, the
$\operatorname{\textsf{OV}}$-lower bound for $\operatorname{\textsc{RPQ-
Count}}$ of Theorem 21 is similiar to a lower bound on counting the results of
certain conjunctive queries from [14], and the
$\operatorname{\textsf{OMv}}$-lower bound from Point $1$ of Theorem 24 is
similiar to a lower bound on enumerating certain conjunctive queries from
[14].

The quite simple observation that Boolean matrix multiplication can be
expressed as querying a bipartite graph (with conjunctive queries) has also
been used in [8] (see also [13, Section 6]) and is also the base for the
$\operatorname{\textsf{OMv}}$-lower bound of [14]. In the context of this
paper, this connection has been used in the bounds of Theorems 18, 20 and
Points $3$ and $4$ of 23.

The obvious connection between evaluating (non-acyclic) conjunctive queries
and finding triangles (or larger cliques) has already been observed in [20]
(see also [13, Section 6]). However, the
$\operatorname{\textsf{Triangle}}$-lower bounds of this paper are quite
different, since $\mathsf{RPQ}$s cannot explicitly express the structure of a
triangle (or a larger clique, for that matter) by using conjunction.
Therefore, our respective lower bounds (Theorems 14, Point $2$ of Theorem 23,
and Point $2$ of Theorem 24) need to encode this aspect in a different way.
With respect to Theorems 14 and Point $2$ of Theorem 23 this is done by using
non-constant queries (which explains why the lower bounds are not for data
complexity, in contrast to the case of conjunctive queries), and with respect
to Point $2$ of Theorem 24, which _does_ work for data complexity, it is done
by using updates. Moreover, our $\operatorname{\textsf{Triangle}}$-lower
bounds do not seem to extend to larger cliques like it is the case for
conjunctive queries (see [13, Section 6]).

Finally, we wish to point out that although some of the reductions used in
this paper are similar to reductions used in the context of conjunctive
queries, due to the difference of $\mathsf{RPQ}$s and $\mathsf{CQ}$s, none of
the lower bounds directly carry over. Furthermore, note that the lower bound
reductions in [8, 14] have been used for obtaining dichotomies and therefore
have been stated in a much more general way.

##  7 Enumeration with Sub-Linear Delay

We now explore three different approaches towards enumeration of
$q(\operatorname{\mathcal{D}})$ with delay strictly better than
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$ (in data complexity):

  1. 1.

allowing super-linear preprocessing,

  2. 2.

enumerating a representative subset of $q(\operatorname{\mathcal{D}})$, and

  3. 3.

restricting the $\mathsf{RPQ}$s.

###  7.1 Super-Linear Preprocessing

Regarding the first approach, we can improve the delay from
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$ to
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ by increasing the linear
preprocessing by a factor of
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}}))$
(in data complexity). Recall that
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$
is the average degree of $\operatorname{\mathcal{D}}$.

######  Theorem 26.

Sorted $\operatorname{\textsc{RPQ-Enum}}$ can be solved with
$\operatorname{O}(|q|^{2}\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|)\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|\operatorname{\mathcal{D}}|)$
preprocessing and $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ delay.

######  Proof 7.1.

Let $\operatorname{\mathcal{D}}$ be a graph database over $\Sigma$, let $q$ be
an $\mathsf{RPQ}$ over $\Sigma$ and let $\preceq$ be the order on
$V_{\operatorname{\mathcal{D}}}$. We assume that
$V_{\operatorname{\mathcal{D}}}=[n]$ with $1\preceq 2\preceq\ldots\preceq n$
(see Lemma 5). Recall that
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$
denotes the average degree of $\operatorname{\mathcal{D}}$, which in
particular means that
$\operatorname{O}(|E_{\operatorname{\mathcal{D}}}|)=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}}))$.
Preprocessing:

  1. 1.

Compute $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ and interpret it as its
underlying non-labelled graph. We also compute the number
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$,
which can be done by moving through the adjacency lists of
$\operatorname{\mathcal{D}}$ and counting all edges.

  2. 2.

Let $H=(V_{H},E_{H})$ be the DAG of
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$’s strongly connected components.
Without loss of generality, we assume that connected components are numbered
with $1,2,\ldots,\ell$ for some $\ell\in\mathbb{N}$, i. e., $V_{H}=[\ell]$,
and we further assume that $1,2,\ldots,\ell$ is a reverse topological sorting
of $H$. We can compute $H$ as follows.

    1. (a)

By the algorithm of Tarjan [49], we first compute the strongly connected
components $K_{1},K_{2},\ldots,K_{\ell}\subseteq
V_{\boxtimes}(\operatorname{\mathcal{D}},q)$ of
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$. Since the finishing times of
the depth-first searches of this algorithm determine a reverse topological
sorting of $H$, we can assume that $K_{1},K_{2},\ldots,K_{\ell}$ describes a
reverse topological sorting. We represent the strongly connected components
$K_{1},K_{2},\ldots,K_{\ell}$ by an array $L$ of size
$|V_{\operatorname{\mathcal{D}}}||q|$ addressable by the nodes of
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, i. e., for every $(i,p)\in
V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, we set $L[(i,p)]=j$ if and only
if $(i,p)\in K_{j}$.

    2. (b)

In order to construct the actual graph $H$, we first initialise an empty
adjacency list for every node $j\in V_{H}=[\ell]$ and also an additional empty
list $P_{j}$. Then we iterate through the list that represents
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$ and add every node $(i,p)$ that
we encounter to the list $P_{L[(i,p)]}$. For every $j\in[\ell]$, $P_{j}$ now
represents $K_{j}$ as a list. Next, we initialise an empty integer array $W$
of size $\ell$. Then, for each $j\in[\ell]$, we iterate through the list
$P_{j}$ and for each node $(i,p)$ that we encounter, we do the following. For
every $(i^{\prime},p^{\prime})$ in the adjacency list of $(i,p)$, if
$W[L[i^{\prime},p^{\prime}]]\neq j$, then we add $L[(i^{\prime},p^{\prime})]$
to the adjacency list of $j$ and set $W[L[i^{\prime},p^{\prime}]]=j$ (the
array $W$ makes sure that we do not add the same arc between strongly
connected components more than once, i. e., for each individual $j\in[\ell]$
considered in the above procedure, $W$ stores for each strongly connected
component $j^{\prime}\in[\ell]$ whether we have already added the arc
$(j,j^{\prime})$).

  3. 3.

Construct $H^{R}$.

  4. 4.

Initialise for each node $j$ in $H^{R}$ an empty AVL tree $A_{j}$ (or any
search tree that allows the operations insert, delete, lookup, delete-min and
delete-max in worst-case time that is logarithmic in its size), and store
pointers to the roots of these trees and a counter for their size in an array
$A$ of size $\ell$, such that finding the tree associated to a specific node
can be done in constant time. For every $i\in[n]$, insert $i$ into the tree
$A_{L[(i,p_{f})]}$, and at each point where the size of $A_{L[(i,p_{f})]}$
exceeds
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
during these insertions, delete the node of largest index from
$A_{L[(i,p_{f})]}$.

  5. 5.

For $j=1,\dots,\ell$ go through the adjacency list of node $j$ in $H^{R}$. For
each arc $(j,j^{\prime})$ in this list, insert one by one all entries from
$A_{j}$ into $A_{j^{\prime}}$ (first lookup to avoid duplicates). Update also
the size counter of the tree $A_{j^{\prime}}$ accordingly, and at each point
where this size exceeds
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
during these insertions, delete the node of largest index from
$A_{j^{\prime}}$. This ensures that $A_{j^{\prime}}$ is kept at a size at most
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$.

  6. 6.

Initialise a Boolean array $S$ of size $\ell$ with entries $0$ everywhere.
Create for each $j\in[\ell]$ a sorted array $Z_{j}$ of all entries in $A_{j}$
by successively extracting and deleting the smallest entry. If $Z_{j}$ is not
empty, set $S[j]=1$.

  7. 7.

Initialise a Boolean array $T$ of size $|V_{\operatorname{\mathcal{D}}}|$ with
entries $0$ everywhere.

Enumeration: In the enumeration phase, we carry out the following procedure.

  * •

For every $i=1,2,\ldots,n$:

    * –

If $S[L[(i,q_{0})]]=1$, then

      * *

If $Z_{L[(i,q_{0})]}$ has size less than
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$,
output all $(i,j)$ for all $j$ stored in $Z_{i}$ (in the sorted order).

      * *

If $Z_{L[(i,q_{0})]}$ has size
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
perform a BFS in $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ starting at
node $(i,p_{0})$ and for every visited $(i^{\prime},p_{f})$, set
$T[i^{\prime}]=1$. Output during this BFS, all pairs $(i,i^{\prime})$ for all
$i^{\prime}$ stored in $Z_{L[(i,q_{0})]}$ (in the sorted order) to keep the
desired delay, i.e., start with $k=1$ and whenever the delay of
$|V_{\operatorname{\mathcal{D}}}||q|$ has expired output $(i,Z_{i}[k])$ and
set $k=k+1$.

      * *

for every $i^{\prime}=Z_{L[(i,q_{0})]}[k],\ldots,n$: produce $(i,i^{\prime})$
as output if $T[i^{\prime}]=1$,

      * *

Set all entries of $T$ to $0$.

Running time: We first note that Steps 1 to 3 can be done in time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$:
Lemma 7 ensures that $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ can be
computed in $\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$, Lemma 2
ensures that $H^{R}$ can be computed in
$\operatorname{O}(|H|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$, and
it can be easily seen that in order to construct $H$, we only have to move
through $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ a constant number of
times; thus, time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$
is sufficient.

Since the search trees never exceed a size of
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$,
each operation supported by the search trees can be carried out in time
$\operatorname{O}(\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))$.
In Step 4, we first initialise the search trees, which can be done in
$\operatorname{O}(|V_{H}|)=\operatorname{O}(|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|)$.
Then, adding $i$ to the search tree $A_{L[(i,p_{f})]}$ for every $i\in[n]$ can
be done in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))$.
In Step 5, we have to perform
$\operatorname{O}(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|)$
search tree operations per arc of $H$, i. e., we need time
$\operatorname{O}(|E_{H}|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))=\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))$.

Step 6, we have to copy, for every $j\in[\ell]$, the elements from $A_{j}$ to
$Z_{j}$, which requires a total of
$\ell\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
search tree operations, so time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))$
is sufficient (note that the time needed for initialising and filling $S$ is
clearly subsumed by this). Finally, Step 7 can obviously be carried out in
time $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$. Hence, the total
running time for the preprocessing is
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))=\operatorname{O}(|\operatorname{\mathcal{D}}||q|^{2}\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))$.
Correctness: We first show that after the preprocessing terminates, for every
$i\in[n]$, $Z_{L[(i,p_{0})]}$ contains the first
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
nodes $i^{\prime}$ (“first” in the sense of smallest index) such that the node
$(i^{\prime},p_{f})$ is reachable from $(i,p_{0})$. In other words,
$Z_{L[(i,p_{0})]}$ contains the first
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
elements of a lexicographically sorted enumeration of $\\{(i,i^{\prime})\mid
i^{\prime}\in[n],(i,i^{\prime})\in q(\operatorname{\mathcal{D}})\\}$. To this
end, we will show if $i^{\prime}$ is among the
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
smallest reachable nodes from $(i,p_{0})$, then $i^{\prime}$ is at some point
inserted into $A_{L[i,p_{0}]}$, which means that $i^{\prime}$ is among the
nodes that are copied to $Z_{L[(i,p_{0})]}$ in Step 6 (recall that we only
remove largest elements from some $A_{j}$ if its size exceeds
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$).

If $(i,p_{0})$ and $(i^{\prime},p_{f})$ are in the same strongly connected
component in $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$, then
$L[(i,p_{0})]=L[(i^{\prime},p_{f})]$ which means that in Step 4 the index
$i^{\prime}$ is inserted into $A_{L[(i^{\prime},p_{f})]}=A_{L[(i,p_{0})]}$.
Otherwise there is a path in $H$ from $L[(i,p_{0})]$ to
$L[(i^{\prime},p_{f})]$, and reversing this path yields a path from
$L[(i^{\prime},p_{f})]$ to $L[(i,p_{0})]$ in $H^{R}$. Denote by
$L[(i^{\prime},p_{f})]=i_{1},i_{2},\dots,i_{x}=L[(i,p_{0})]$ the vertices on
the path from $L[(i^{\prime},p_{f})]$ to $L[(i,p_{0})]$ in $H^{R}$. By the
reverse topological sorting on $H$, it follows that
$i_{1}<i_{2}<\ldots<i_{x}$. In Step 4, $i^{\prime}$ is put in
$A_{i_{1}}=A_{L[(i^{\prime},p_{f})]}$, and iteratively in Step 5, $i^{\prime}$
is copied from $A_{i_{h}}$ to $A_{i_{h+1}}$ for $1\leq h<x$, and therefore
also into $A_{i_{x}}=A_{L[i,p_{0}]}$.

In the enumeration procedure, we go through _phases_ $i=1,2,\ldots,n$ and we
will next show that in phase $i$, we enumerate without duplicates exactly the