pairs $(i,i^{\prime})\in q(\operatorname{\mathcal{D}})$ sorted by their right
element (this means that the enumeration procedure enumerates
$q(\operatorname{\mathcal{D}})$ without duplicates and lexicographically
sorted).

If the size of $Z_{L[(i,p_{0})]}$ is less than
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$,
then, by the considerations above, we know that $Z_{L[(i,p_{0})]}$ contains
_all_ $i^{\prime}$ with $(i,i^{\prime})\in q(\operatorname{\mathcal{D}})$.
Thus, we enumerate all pairs $(i,i^{\prime})$ with $i^{\prime}\in
Z_{L[(i,p_{0})]}$ sorted by their right elements. On the other hand, if the
size of $Z_{L[(i,p_{0})]}$ is at least
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$,
we perform a BFS starting in $(i,p_{0})$. After termination of this BFS, we
output exactly the pairs $(i,i^{\prime})$ for which $(i^{\prime},p_{f})$ is
visited in this BFS and that are not already contained in $Z_{L[(i,p_{0})]}$.
This shows that we correctly enumerate $q(\operatorname{\mathcal{D}})$ without
duplicates. Furthermore, since we list again the pairs $(i,i^{\prime})$ by
increasing index $i^{\prime}$ (the first
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
by the sorting provided by $Z_{L[(i,p_{0})]}$, and the possibly further by the
sorted array $T$), the enumeration is again sorted by the right elements of
the pairs.

It only remains to estimate the delay of the enumeration procedure, and it is
sufficient to do this for each phase $i$ separately. If $S[L[(i,q_{0})]=0$
then phase $i$ terminates in constant time, which also means that in case that
$S[L[(i,q_{0})]=0$ for all phases $i$, we need at most time in
$O(|V_{\operatorname{\mathcal{D}}}|)$ to determine that the enumeration has
terminated. If the size of $Z_{L[(i,p_{0})]}$ is less than
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$,
then we enumerate all pairs with constant delay. If, on the other hand, the
size of $Z_{L[(i,p_{0})]}$ is
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$,
then this array contains enough solutions to pay for the BFS we run for
$(i,p_{0})$, in the sense that producing the output form $Z_{L[(i,p_{0})]}$
with delay $|V_{\operatorname{\mathcal{D}}}|$ yields time
$|V_{\operatorname{\mathcal{D}}}|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|=|E_{\operatorname{\mathcal{D}}}||q|$
which is enough to completely run the BFS. The possibly further solutions
stored in $T$ are then produced with delay at most
$|V_{\operatorname{\mathcal{D}}}|$ (for running through this list to find the
non-zero entries).

Obviously, in the worst case we can have
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})=\Omega(|V_{\operatorname{\mathcal{D}}}|)$
and then the preprocessing of the algorithm of Theorem 26 is
$\Omega(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)$ (in
data complexity) and therefore no improvement over just computing the complete
set $q(\operatorname{\mathcal{D}})$ in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||\operatorname{\mathcal{D}}|)$.
However, for graph databases with low average degree, we can decrease the
delay significantly from $\operatorname{O}(|\operatorname{\mathcal{D}}|)$ to
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ at the cost of a slightly
super-linear preprocessing time. As another remark about Theorem 26, we
observe that the pre-computed information becomes worthless if
$\operatorname{\mathcal{D}}$ is updated.

Finally, we discuss a minor modification of the algorithm of Theorem 26, which
yields a slightly different result that is interesting in its own right (we
state this result as a corollary after the remark).

######  Remark 27.

At the cost of additional space (in $O(|V_{\operatorname{\mathcal{D}}}|^{2})$)
and giving up on sorted enumeration, we can use the lazy array initialisation
technique (see, e. g., the textbook [44]) in order to reduce the preprocessing
time in Theorem 26 by a factor
$\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|)$
to
$\operatorname{O}(|q|^{2}\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|\operatorname{\mathcal{D}}|)$.
This can be done by replacing each AVL-tree $A_{j}$ in step 4 by an array
$A_{j}$ (with lazy initialization) of size $|V_{\operatorname{\mathcal{D}}}|$,
and completely dropping step 6. Instead of the arrays $Z_{j}$, we use in the
enumeration phase the unsorted lists $\widehat{A}_{j}$ of the elements stored
in the arrays $A_{j}$. In step 4 and 5, we simply stop filling the arrays
$A_{j}$ as soon as their counter exceeds
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$.
This reduces the running time for these steps to
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$, and
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|)$,
respectively. Note that the lazy initialization allows us to avoid duplicates
in constant time (which before was achieved by looking up the elements in the
AVL-trees which required time
$\operatorname{O}(\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|))$).
In every phase $i$ of the enumeration procedure instead of a sorted list
$Z_{L[(i,p_{0})]}$ with the (at most)
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
smallest nodes $i^{\prime}$ with $(i,i^{\prime})\in
q(\operatorname{\mathcal{D}})$ we only have an unsorted list
$\widehat{A}_{L[(i,p_{0})]}$ of at most
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
nodes $i^{\prime}$ (not necessarily the smallest ones) with $(i,i^{\prime})\in
q(\operatorname{\mathcal{D}})$. In the case where less than
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})|q|$
elements are stored in $\widehat{A}_{L[(i,p_{0})]}$, we can just produce all
$(i,i^{\prime})$ for all $i^{\prime}$ stored in $\widehat{A}_{L[(i,p_{0})]}$.
On the other hand, if $\widehat{A}_{L[(i,p_{0})]}$ stores more elements, then
again we use the elements stored in $\widehat{A}_{L[(i,p_{0})]}$ in order to
pay for a BFS and store in the array $T$ the new elements found by the BFS.
However, since we do not produce the elements in a sorted way, we use $T$ to
also track which elements have been produced already. Whenever we output
$(i,i^{\prime})$ with $i^{\prime}$ from $\widehat{A}_{L[(i,p_{0})]}$ during
the run of the BFS for $i$, we set $T[i^{\prime}]=2$ (and never overwrite a
2-entry in $T$). In order to list the pairs produced by the BFS after its
termination, we pass once through $T$ and only produce $(i,i^{\prime})$ if
$T[i^{\prime}]=1$. As last technical detail, we change step 7 to initialise
$T$ as integer array (so we can actually have 2-entries in $T$).

######  Corollary 28.

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

###  7.2 Enumeration of Representative Subsets

Evaluating an $\mathsf{RPQ}$ $q$ on a graph database
$\operatorname{\mathcal{D}}$ aims to find for each node $u$ _all_ its
$q$-successors, i. e., nodes reachable by a $q$-path. It is therefore a
natural restriction to ask for only _at least one_ (if any) such successor.
Likewise, we could also ask for at least one (if any) $q$-predecessor for
every node. More precisely, instead of the whole set
$q(\operatorname{\mathcal{D}})$, the task is to enumerate a
_$q(\operatorname{\mathcal{D}})$ -approximation_, which is a set $A\subseteq
q(\operatorname{\mathcal{D}})$ such that, for every $u,v\in
V_{\operatorname{\mathcal{D}}}$, if $(u,v)\in q(\operatorname{\mathcal{D}})$,
then also $(u,v^{\prime}),(u^{\prime},v)\in A$ for some
$u^{\prime},v^{\prime}\in V_{\operatorname{\mathcal{D}}}$. Such a set is
representative for $q(\operatorname{\mathcal{D}})$, since it contains for
_every_ node the information, whether it is involved as a source and whether
it is involved as a target in some reachable pair from
$q(\operatorname{\mathcal{D}})$. The problem of enumerating any
$q(\operatorname{\mathcal{D}})$-approximation for given
$\operatorname{\mathcal{D}}$ and $q$ will be denoted by
$\operatorname{\textsc{App-RPQ-Enum}}$.

######  Lemma 29.

Given a graph database $\operatorname{\mathcal{D}}$ and an $\mathsf{RPQ}$ $q$,
we can compute a $q(\operatorname{\mathcal{D}})$-approximation in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

######  Proof 7.2.

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).

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. 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})$.

We modify $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ by adding a new node
$v_{\mathsf{source}}$ with an arc to each $(i,p_{0})$ with $i\in[n]$, and 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{source}}$ and $v_{\mathsf{sink}}$ to the
list that represents $V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, which
requires constant time. Then we add all vertices from $S$ to the adjacency
list for $v_{\mathsf{source}}$, which requires time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$. Finally, for every node
$(i,p_{f})$ in $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}}}|)$.

Let $S^{\prime}$ and $T^{\prime}$ be arrays of size
$|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|$ the entries of which can store
values from $[n]\cup\\{0\\}$ and can be addressed by the nodes from
$V_{\boxtimes}(\operatorname{\mathcal{D}},q)$. We wish to fill these arrays
such that they satisfy the following properties. For every $(u,p)\in
V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, if $(u,p)$ is reachable from
some node from $S$, then $S^{\prime}[(u,p)]=i$ for some $i\in[n]$ such that
$(u,p)$ is reachable from $(i,p_{0})$, and if $(u,p)$ is not reachable from
any node from $S$, then $S^{\prime}[(u,p)]=0$. Analogously, for every
$(u,p)\in V_{\boxtimes}(\operatorname{\mathcal{D}},q)$, if $(u,p)$ can reach
some node from $T$, then $T^{\prime}[(u,p)]=i$ for some $i\in[n]$ such that
$(u,p)$ can reach $(i,p_{f})$, and if $(u,p)$ cannot reach any node from $T$,
then $T^{\prime}[(u,p)]=0$.

This means that $S^{\prime}$ and $T^{\prime}$ contain all the information we
need to construct a $q(\operatorname{\mathcal{D}})$-approximation. More
precisely, let

$A=\\{(i,T^{\prime}[(i,p_{0})])\mid i\in[n],T^{\prime}[(i,p_{0})]\neq
0\\}\cup\\{(S^{\prime}[(i,p_{f})],i)\mid i\in[n],S^{\prime}[(i,p_{f})]\neq
0\\}\,.$

It can be easily seen that $A\subseteq q(\operatorname{\mathcal{D}})$ and, for
every $u,v\in V_{\operatorname{\mathcal{D}}}$,

$(u,v)\in q(\operatorname{\mathcal{D}})\implies(\exists v^{\prime}\in
V_{\operatorname{\mathcal{D}}}:(u,v^{\prime})\in A)\wedge(\exists
u^{\prime}\in V_{\operatorname{\mathcal{D}}}:(u^{\prime},v)\in A)\,.$

Thus, $A$ is a $q(\operatorname{\mathcal{D}})$-approximation. Moreover,
provided that we have the arrays $S^{\prime}$ and $T^{\prime}$ at our
disposal, we can compute $A$ in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$. Consequently, in order
to conclude the proof, it remains to explain how the arrays $S^{\prime}$ and
$T^{\prime}$ can be computed in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

We assume that $S^{\prime}$ and $T^{\prime}$ are initialised with every entry
storing $0$. For every $i\in[n]$, we set $S^{\prime}[(i,p_{0})]=i$ and
$T^{\prime}[(i,p_{f})]=i$. This can be done in time
$\operatorname{O}(|V_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|V_{\operatorname{\mathcal{D}}}||q|)$.
Next, we perform a BFS from $v_{\textsf{source}}$ and whenever we traverse an
arc $((u,p),(u^{\prime},p^{\prime}))$, we set
$S^{\prime}[(u^{\prime},p^{\prime})]=S^{\prime}[(u,p)]$. This can be done in
time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.
Interpreting the initialisation that ensures $S^{\prime}[(i,p_{0})]=i$, for
every $i\in[n]$, as the base of an induction and the assignments
$S^{\prime}[(u^{\prime},p^{\prime})]=S^{\prime}[(u,p)]$ for traversed arcs
$((u,p),(u^{\prime},p^{\prime}))$ as the step of the induction, we can
directly conclude by induction that after termination of this BFS,
$S^{\prime}$ has the desired property. In order to compute $T^{\prime}$, we
first have to construct $(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 perform a BFS from $v_{\textsf{sink}}$ and whenever we traverse an arc
$((u,p),(u^{\prime},p^{\prime}))$, we set
$T^{\prime}[(u^{\prime},p^{\prime})]=T^{\prime}[(u,p)]$. Hence, computing
$S^{\prime}$ and $T^{\prime}$ can be done in time
$\operatorname{O}(|G_{\boxtimes}(\operatorname{\mathcal{D}},q)|)=\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.

Lemma 29 directly implies the following result.

######  Theorem 30.

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

######  Proof 7.3.

Let $\operatorname{\mathcal{D}}$ be a graph database over $\Sigma$ and let $q$
be an $\mathsf{RPQ}$ over $\Sigma$. In the preprocessing, we can compute a
$q(\operatorname{\mathcal{D}})$-approximation $A$, which, according to Lemma
29, can be done in time $\operatorname{O}(|\operatorname{\mathcal{D}}||q|)$.
In the enumeration, we simply enumerate the set $A$ with constant delay.

Interestingly, it seems rather difficult to also support updates while keeping
a low delay (the following bounds are due to the same reductions used for
Theorem 24, simply because these reductions produce instances for which all
$q(\operatorname{\mathcal{D}})$-approximations are equal to
$q(\operatorname{\mathcal{D}})$).

######  Theorem 31.

If $\operatorname{\textsc{App-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,
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 7.4.

We prove the two lower bounds of Theorem 31 separately.

  1. 1.

We observe that exactly the same reduction used in the proof of Point $1$ of
Theorem 24 works as well. Since we assume the same bound on the time required
for updates, we can construct the graph database
$\operatorname{\mathcal{D}}_{M,\vec{v}^{1}}$ in the same way as in the proof
of Point $1$ of Theorem 24. Recall that
$q(\operatorname{\mathcal{D}}_{M,\vec{v}^{1}})=\\{(u_{i},w)\mid(M\vec{v}^{1})[i]=1\\}$.
However, since for every $i\in[n]$, either no node is reachable by a path
labelled with $11$ or only the node $w$ is reachable by a path labelled with
$11$, we know that $A\subseteq q(\operatorname{\mathcal{D}})$ is a
$q(\operatorname{\mathcal{D}}_{M,\vec{v}^{1}})$-approximation if and only if
$A=q(\operatorname{\mathcal{D}}_{M,\vec{v}^{1}})$. Thus, we can compute
$M\vec{v}^{1}$ by enumerating a
$q(\operatorname{\mathcal{D}}_{M,\vec{v}^{1}})$-approximation in time
$\operatorname{O}(nt_{d})$. Repeating this step in the same way as done in the
proof of Point $1$ of Theorem 24 leads to an algorithm solving
$\operatorname{\textsf{OMv}}$ in time $\operatorname{O}(n^{3-\epsilon})$.

  2. 2.

We observe that exactly the same reduction used in the proof of Point $2$ of
Theorem 24 works as well. We construct the graph database
$\operatorname{\mathcal{D}}_{v_{1}}$ over $\\{\mathtt{a}\\}$ and the
$\mathsf{RPQ}$ $q=\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}\mathtt{a}$ in the
same way. Recall 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. This also means
that any $q(\operatorname{\mathcal{D}}_{v_{1}})$-approximation $A$ is equal to
$\\{(s,t)\\}$ if there is a triangle that contains $v_{1}$, and $A=\emptyset$
otherwise. Thus, the assumption that $\operatorname{\textsc{App-RPQ-Enum}}$
can be solved with preprocessing
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$,
$\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$, leads to combinatorial subcubic
algorithm for $\operatorname{\textsf{Triangle}}$ in the same way as in the
proof of Point $2$ of Theorem 24.

###  7.3 Restricted $\mathsf{RPQ}$s

As our third approach, we show that for restricted $\mathsf{RPQ}$, we can
solve $\operatorname{\textsc{RPQ-Enum}}$ with delay much smaller than
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$. We first need some
definitions. For any class $Q\subseteq\mathsf{RPQ}$, we denote by
$\operatorname{\textsc{Enum}}(Q)$ the problem $\operatorname{\textsc{RPQ-
Enum}}$ where the input $\mathsf{RPQ}$ is from $Q$. Moreover, $\bigvee(Q)$ is
the set of all $\mathsf{RPQ}$s of the form
$(q_{1}\operatorname{\vee}\ldots\operatorname{\vee}q_{m})$ with $q_{i}\in Q$
for every $i\in[m]$. An $\mathsf{RPQ}$ $q$ over $\Sigma$ is a _basic
transitive $\mathsf{RPQ}$_ (over $\Sigma$) if
$q=(x_{1}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})^{*}$ or
$q=(x_{1}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})^{+}$, where
$x_{1},\ldots,x_{k}\in\Sigma$; and $q$ is a _short $\mathsf{RPQ}$_ (over
$\Sigma$) if $q=(x_{1}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})$ or
$q=(x_{1}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})(y_{1}\operatorname{\vee}\ldots\operatorname{\vee}y_{k^{\prime}})$,
where $x_{1},\ldots,x_{k},y_{1},\ldots,y_{k^{\prime}}\in\Sigma$. By
$\mathsf{BT\text{-}RPQ}$ and $\mathsf{S\text{-}RPQ}$, we denote the class of
basic transitive $\mathsf{RPQ}$ and the class of short $\mathsf{RPQ}$,
respectively.

We show that for the class
$\bigvee(\mathsf{S\text{-}RPQ}\cup\mathsf{BT\text{-}RPQ})$ (which, e. g.,
contains $\mathsf{RPQ}$s of the form
$q=(\mathtt{a}\mathtt{b}\operatorname{\vee}\mathtt{c}^{*}\operatorname{\vee}\mathtt{b}(\mathtt{c}\operatorname{\vee}\mathtt{d})\operatorname{\vee}(\mathtt{a}\operatorname{\vee}\mathtt{b}\operatorname{\vee}\mathtt{d})^{+})$),
semi-sorted $\operatorname{\textsc{RPQ-Enum}}$ can be solved with linear
preprocessing and delay $\operatorname{O}(\Delta(\operatorname{\mathcal{D}}))$
in data complexity (recall _semi-sorted_ from Section 2). To this end, we
first prove a general upper bound for semi-sorted
$\operatorname{\textsc{Enum}}(\bigvee(Q))$ in terms of the
$\operatorname{\textsc{Enum}}(Q)$.

######  Lemma 32.

Let $Q\subseteq\mathsf{RPQ}$ be such that semi-sorted
$\operatorname{\textsc{Enum}}(Q)$ can be solved with preprocessing
$p(|\operatorname{\mathcal{D}}|,|q|)$ and delay
$d(|\operatorname{\mathcal{D}}|,|q|)$, then semi-sorted
$\operatorname{\textsc{Enum}}(\bigvee(Q))$ can be solved with preprocessing
$\operatorname{O}((|q|p(|\operatorname{\mathcal{D}}|,|q|))+|V_{\operatorname{\mathcal{D}}}|)$
and delay $\operatorname{O}(|q|d(|\operatorname{\mathcal{D}}|,|q|))$.

######  Proof 7.5.

We assume that semi-sorted $\operatorname{\textsc{Enum}}(Q)$ can be solved
with preprocessing $p(|\operatorname{\mathcal{D}}|,|q|)$ and delay
$d(|\operatorname{\mathcal{D}}|,|q|)$. Let $q\in\bigvee(Q)$, i. e.,
$q=(q_{1}\operatorname{\vee}q_{2}\operatorname{\vee}\ldots\operatorname{\vee}q_{m})$
with $q_{i}\in Q$ for every $i\in[m]$. By assumption, there are enumeration
algorithms $A_{1},A_{2},\ldots,A_{m}$ that, for any input graph database
$\operatorname{\mathcal{D}}$, perform some preprocessing in time
$p(|\operatorname{\mathcal{D}}|,|q_{i}|)$ and then enumerate the pairs
$q_{i}(\operatorname{\mathcal{D}})$ ordered by their first elements with delay
$d(|\operatorname{\mathcal{D}}|,|q_{i}|)$. We describe now an enumeration
algorithm $A$ that, for any input graph database $\operatorname{\mathcal{D}}$,
performs some preprocessing in time
$\operatorname{O}(|q|p(|\operatorname{\mathcal{D}}|,|q|))$ and then enumerates
the pairs in $q(\operatorname{\mathcal{D}})$ ordered by their first elements
with delay $\operatorname{O}(|q|d(|\operatorname{\mathcal{D}}|,|q|))$. Note
that
$q(\operatorname{\mathcal{D}})=\bigcup^{m}_{i=1}q_{i}(\operatorname{\mathcal{D}})$.

Let $\operatorname{\mathcal{D}}$ be the input graph database over $\Sigma$. We
assume that $V_{\operatorname{\mathcal{D}}}=[n]$ with $1\preceq
2\preceq\ldots\preceq n$ (see Lemma 5).
Intuitive Explanation: The algorithm $A$ uses size-$m$ arrays $L$ and $R$ that
store nodes from $V_{\operatorname{\mathcal{D}}}=[n]$, and size-$n$ Boolean
arrays $X$ and $Y$ that represent subsets of $[n]$. We construct these in the
preprocessing, in addition to performing the preprocessing procedures of the
algorithms $A_{1},A_{2},\ldots,A_{m}$. Since the enumeration algorithms
$A_{1},A_{2},\ldots,A_{m}$ provide a semi-ordered enumeration, each
enumeration of $q_{j}(\operatorname{\mathcal{D}})$ can be seen as a table with
two columns whose rows correspond to the pairs from
$q_{j}(\operatorname{\mathcal{D}})$, ordered by the first column. The
enumeration then produces the rows of this table from top to bottom.
Therefore, the enumeration proceeds in $n$ phases, where the $i^{\text{th}}$
phase consists in producing all rows with $i$ in the left column (note that
for some $i$ such rows might not exist). Consequently, we can also interpret
phase $i$ of the algorithms $A_{j}$ as an enumeration of only single elements
from $V_{\operatorname{\mathcal{D}}}$, since the left elements of the pairs
are always $i$. The enumeration procedure of $A$ also proceeds in $n$ phases,
where the $i^{\text{th}}$ phase consists in having the enumeration algorithms
$A_{1},A_{2},\ldots,A_{m}$ perform their $i^{\text{th}}$ phases in an
interleaved manner, i. e., we let each $A_{i}$ produce the next element one
after the other, and then we repeat this step until all $A_{j}$ have finished
their $i^{\text{th}}$ phase. We maintain in array $L$ the current phases (i.
e., the current left element of the produced pairs) of the algorithms $A_{j}$
(this is necessary, since only a subset may participate in phase $i$ for a
fixed $i$ and some $A_{j}$ may finish it earlier than others) and we store in
array $R$ the elements produced most recently by the algorithms $A_{j}$. Once
all $A_{j}$ (that are still in phase $i$) have produced one new element, we
disregard all those elements $v$ among them such that $A$ has already produced
$(i,v)$ in phase $i$ (these already produced elements will be stored in $Y$),
and we store all other elements in $X$. Then $A$ picks some element $v\in X$,
produces $(i,v)$ (and therefore “buys” another delay), marks $v$ as already
produced by adding it to $Y$ and removes it from $X$. Then, again each $A_{j}$
will produce the next element and this goes on until all $A_{j}$ have finished
phase $i$, and therefore we can move on to the next phase.

Due to the sets $X$ and $Y$, we do not produce duplicates. However, in order
to bound the delay, we have to produce at least one pair in each iteration of
the main loop in each phase, and therefore we have to show that it cannot
happen that $X$ is empty when $A$ needs to produce the next pair. We shall now
define this algorithm more formally.
Preprocessing: First, $A$ performs all preprocessing procedures of the
algorithms

$A_{1},A_{2},\ldots,A_{m}\,,$

which can be done in time
$\sum^{m}_{i=1}p(|\operatorname{\mathcal{D}}|,|q_{i}|)=\operatorname{O}(|q|p(|\operatorname{\mathcal{D}}|,|q|))$.
Then we construct arrays $L$ and $R$ each of size $m$ the entries of which can
store values from $[n]\cup\\{0,n+1\\}$, and we initialise all entries with
$0$. Furthermore, we construct Boolean arrays $X$ and $Y$ of size $n$ that
initially store $0$ in every entry (note that these arrays shall be used for
storing subsets of $[n]$). This can clearly be done in time
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|+|q|)$. Consequently, the
total preprocessing time is
$\operatorname{O}(|q|p(|\operatorname{\mathcal{D}}|,|q|)+|V_{\operatorname{\mathcal{D}}}|)$.
Enumeration: Firstly, we set $c=0$, where $c$ will be a counter that indicates
the current phase. Then we iterate the following main loop until it
terminates:

  1. 1.

For every $i\in[m]$ with $L[i]=c$, we request the next element from the
enumeration procedure of $A_{i}$. If such an element $(u,v)$ is returned, we
set $L[i]=u$ and $R[i]=v$, and if no element is returned (i. e., the
enumeration of $A_{i}$ is done), we set $L[i]=R[i]=n+1$.

  2. 2.

If $c<\min\\{L[i]\mid i\in[m]\\}$, then

    1. (a)

for every $v\in X$, remove $v$ from $X$ and produce $(c,v)$,

    2. (b)

set $Y=\emptyset$,

    3. (c)

set $c=\min\\{L[i]\mid i\in[m]\\}$.

  3. 3.

If $c=n+1$, interrupt.

  4. 4.

For every $i\in[m]$, if $L[i]=c$ and $R[i]\notin Y$, add $R[i]$ to $X$.

  5. 5.

Choose some element $v\in X$, produce $(c,v)$ as output, remove $v$ from $X$
and add $v$ to $Y$.

  6. 6.

Move to Step 1.

Correctness: We first note that in the first iteration of the main loop, we
have $L[i]=c=0$ for every $i\in[m]$, so we request the first pairs from _all_
$A_{j}$ and store the respective left and right elements in $L$ and $R$,
respectively (or store $n+1$ in both $L$ and $R$, if the enumeration procedure
has already terminated without producing any pair). In any subsequent
iteration, this only happens with respect to those $A_{j}$ that are in phase
$c$. If condition $c<\min\\{L[i]\mid i\in[m]\\}$ is satisfied in Step 2, then
this means that by performing Step 1, we have reached a new phase (note that
also in the very first iteration, we reach a new phase, i. e., phase $i$ for
the smallest left element $i\in[n]$ in any pair produced by some $A_{j}$) and
therefore we produce all elements of $X$ as output (paired with $c$) and then
empty the sets $X$ and $Y$ (which were only storing elements that are relevant
for phase $c$ that just terminated). Moreover, we have to determine the next
phase, which is done by setting $c=\min\\{L[i]\mid i\in[m]\\}$. In the very
first iteration, $X$ is empty, so nothing happens in these steps except
setting $c$ to the current phase (which must be strictly larger than $0$, but
not necessarily $1$). Next, Step 3 would now interrupt the whole procedure, if
$c=n+1$, which means that all enumeration procedures of the algorithms $A_{j}$
have already terminated. Note that if this happens for the first time, i. e.,
the last still active enumeration procedures of some $A_{j}$ terminate by
requesting their last elements in Step 1, then we necessarily also have
$c<\min\\{L[i]\mid i\in[m]\\}$ in Step 2, which means that we have produced
all elements from $X$ as output before the interruption is invoked in Step 3.
If, on the other hand, we reach Step 4, then we collect in the set $X$ the
right elements from all new pairs produced by $A_{j}$ that are in phase $c$,
but only if these are not already stored in $Y$, since then they would have
already been produced as right element in a pair with $c$ as left element.
Step 5 then chooses and actually produces (paired with $c$) one of the
elements from $X$ (and removes it from $X$ and adds it to $Y$ to store that is
has already been produced). Finally, in Step 6, we move back to Step 1, which
triggers a new iteration.

These considerations show that the procedure from above will enumerate
$q(\operatorname{\mathcal{D}})$. In particular, note that if we enter Step 5
with $X$ being empty, then we do not produce an output at this point, but, due
to Step 2, we will nevertheless completely enumerate
$q(\operatorname{\mathcal{D}})$. Since we synchronise the enumerations of the
$A_{j}$ with respect to their phases, the enumeration of
$q(\operatorname{\mathcal{D}})$ produces _all_ pairs from
$q(\operatorname{\mathcal{D}})$ with left element $i$, then all pairs with
left element $i^{\prime}>i$ and so on; thus, the enumeration of
$q(\operatorname{\mathcal{D}})$ is semi-ordered. Furthermore, the book keeping
done in sets $X$ and $Y$ guarantees that we do not produce duplicates. It only
remains to analyse the delay of this enumeration procedure.

We first observe that Step 2b, i. e., setting $Y=\emptyset$, is problematic
since it requires time $\operatorname{O}(n)$ (we have to set $Y[i]=0$ for
every $i\in[n]$). Therefore, we implement the array $Y$ as follows. Instead of
letting it be Boolean, we assume that it can store elements from
$[n]\cup\\{0\\}$. The idea is that $Y[i]=0$ means that $i\notin Y$ (just as
for the Boolean case), while $Y[i]=j$ with $j\in[n]$ means $i\in Y$ in the
case that we are currently in phase $j$, i. e., $c=j$, and $i\notin Y$
otherwise. With this interpretation, Step 2b is not necessary anymore, since
setting $c=\min\\{L[i]\mid i\in[m]\\}$ in Step 2c has the same effect as
erasing all elements from $Y$. Consequently, we can ignore Step 2b altogether
(or rather interpret as a mere comment in the pseudo code above to indicate
what is happening at Step 2b). In particular, we note that with this
implementation of $Y$, we can still check for both $X$ and $Y$ whether they
contain a specific element, and we can add or erase specific elements in
constant time (adding $i$ to $Y$ in phase $c$ just means to set $Y[i]=c$
instead of $Y[i]=1$).

However, in Steps 2a and 5, we also have to retrieve _some_ element from $X$.
In order to do this efficiently (and not by moving through the array from left
to right to find some elements, which requires time $\operatorname{O}(n)$), we
also store the elements of $X$ as an unsorted list (which is initialised in
the preprocessing). This means that we can always obtain some element of $X$
in constant time (by just retrieving the first list element). Keeping the
array and the list for $X$ synchronised is no problem: Whenever we add some
$i$ to $X$ (Step 4), we set $X[i]=1$ and add $x$ at the end of the list for
$X$; whenever we want to retrieve some element from $X$ (Steps 2a and 5), we
retrieve and remove the first list element, say $i$, and then we set $X[i]=0$.
Consequently, all operations with respect to the lists $X$ and $Y$ can be
performed in constant time.

We estimate the running-time for each of the separate steps of an iteration.
Step 1 requires time
$\operatorname{O}(\sum^{m}_{j=1}d(|\operatorname{\mathcal{D}}|,|q_{j}|))=\operatorname{O}(md(|\operatorname{\mathcal{D}}|,|q|))$.
The total running time of Steps 2 to 2c is $\operatorname{O}(m+k)$, where $k$
is the number of pairs $(c,v)$ produced in Step 2a and $\operatorname{O}(m)$
is needed to compute $\min\\{L[i]\mid i\in[m]\\}$. Note that the pairs that
are produced in Step 2 are output with constant delay in Step 2a and pay for
the running time dependence on $k$, hence in the worst case, $k=0$ where Step
2 requires time in $\operatorname{O}(m)$. Step 4 requires time
$\operatorname{O}(m)$. All other steps can be carried out in constant time.
This means that if in each iteration at least one pair is produced by Step 6,
then the delay of the whole enumeration procedure of algorithm $A$ is
$\operatorname{O}(md(|\operatorname{\mathcal{D}}|,|q|))$. Obviously, if we can
never reach the situation that $X=\emptyset$ in Step 5, then in each iteration
at least one pair is produced. Therefore, it is sufficient to prove this
property.

Let us assume that the enumeration procedure has just finished Step 3 and we
are in some iteration of phase $i$, i. e., $c=i$. Moreover, we assume that so
far, we have not encountered the situation that $X=\emptyset$ in Step 5. For
every $j\in[m]$, let $a_{j}=R[j]$ if $L[j]=c$ where $a_{j}=\bot$ indicates the
situation that element $a_{j}$ does not exist. This means that all existing
elements $a_{j}$ with $j\in[m]$ are exactly those elements that have most
recently been produced in phases $i$ of the enumeration procedures from the
algorithms $A_{j}$ (this can have happened in Step 1 of the same iteration or,
if this is the first iteration of phase $i$, also in applications of Step 1 in
previous iterations). In particular, the existing elements $a_{j}$ with
$j\in[m]$ have not yet been handeled in the sense of Step 4, i. e., we have
not yet checked whether they have already been produced as output and, if not,
have added them to $X$. We can also note that there must be at least one
$j\in[m]$ with $a_{j}\neq\bot$, since otherwise $c<\min\\{L[i]\mid
i\in[m]\\}$.

In addition to these elements $a_{j}$, for every $j\in[m]$, let
$b_{j,1},b_{j,2},\ldots,b_{j,\ell_{j}}$ (note that $\ell_{j}=0$ is possible)
be exactly the elements already produced in phase $i$ of the enumeration
procedure of $A_{j}$ in some previous iterations. In other words, for every
$j\in[m]$, we have requested in applications of Step 1 exactly the elements
$b_{j,1},b_{j,2},\ldots,b_{j,\ell_{j}},a_{j}$ from phase $i$ of the
enumeration procedure of $A_{j}$ (note that $a_{j}=\bot$ is possible, which
means that $a_{j}$ does not exist and therefore has not been requested).
Moreover, this has happened in $\ell=\max\\{\ell_{j}\mid j\in[m]\\}$ previous
(i. e., not counting the current one) iterations of the main loop of the
enumeration procedure of algorithm $A$. In particular, this means that we have
in phase $i$ so far only produced $\ell$ pairs with $i$ as left element.

Let $K=\\{b_{j,p}\mid j\in[m],p\in[\ell_{j}]\\}$ and let $M=\\{a_{j}\mid
j\in[m]\\}$. Since $\ell=\max\\{\ell_{j}\mid j\in[m]\\}$, there is at least
one $j^{\prime}\in[m]$ with $\ell_{j^{\prime}}=\ell$ and therefore
$|\\{b_{j^{\prime},1},b_{j^{\prime},2},\ldots,b_{j^{\prime},\ell_{j^{\prime}}}\\}|=\ell$.
This is true since the elements
$b_{j^{\prime},1},b_{j^{\prime},2},\ldots,b_{j^{\prime},\ell_{j^{\prime}}}$
are part of the $i^{\text{th}}$ phase of the enumeration of $A_{j^{\prime}}$
and therefore must be distinct. Thus, $|K|\geq\ell$. Furthermore, we can
choose $j^{\prime}$ such that $a_{j^{\prime}}\neq\bot$. This is the case since
we have $a_{j}=\bot$ if and only if $\ell_{j}<\ell$ (i. e., phase $i$ of the
enumeration of $A_{j}$ has already terminated) and, as observed above, there
must be at least one $j\in[m]$ with $a_{j}\neq\bot$.

For every $b\in K$, either $(i,b)$ has been produced as output, or $b\in X$.
Since so far we have only produced $\ell$ pairs as output, this directly
implies that if $|K|>\ell$, then $X\neq\emptyset$, which means that we reach
Step 5 with $X\neq\emptyset$. If, on the other hand, $|K|=\ell$, then
$K=\\{b_{j^{\prime},1},b_{j^{\prime},2},\ldots,b_{j^{\prime},\ell_{j^{\prime}}}\\}$,
which also means that $a_{j^{\prime}}\notin K$ since
$b_{j^{\prime},1},b_{j^{\prime},2},\ldots,b_{j^{\prime},\ell_{j^{\prime}}},a_{j^{\prime}}$
is an enumeration of distinct elements provided by algorithm $A_{j^{\prime}}$
(recall that $a_{j^{\prime}}\neq\bot$, as observed above). Consequently, we
also have $a_{j^{\prime}}\notin Y$ and therefore $a_{j^{\prime}}$ is added to
$X$ in Step 4. Hence, we reach Step 5 with $X\neq\emptyset$.

Now, we give upper bounds for
$\operatorname{\textsc{Enum}}(\mathsf{BT\text{-}RPQ})$ and
$\operatorname{\textsc{Enum}}(\mathsf{S\text{-}RPQ})$ separately.

######  Theorem 33.

Semi-sorted $\operatorname{\textsc{Enum}}(\mathsf{BT\text{-}RPQ})$ can be
solved with delay $\operatorname{O}(\Delta(\operatorname{\mathcal{D}}))$ (and
without preprocessing).

######  Proof 7.6.

Let $\operatorname{\mathcal{D}}$ be a graph database and let
$q=(x_{1}\operatorname{\vee}x_{2}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})^{*}$
and
$q^{\prime}=(x_{1}\operatorname{\vee}x_{2}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})^{+}$,
where $x_{1},x_{2},\ldots,x_{k}\in\Sigma$. It can be easily seen that
enumerating $q(\operatorname{\mathcal{D}})$ or
$q^{\prime}(\operatorname{\mathcal{D}})$ is the same as enumerating the
reflexive-transitive closure $(E_{\operatorname{\mathcal{D}}^{\prime}})^{*}$
or the transitive closure $(E_{\operatorname{\mathcal{D}}^{\prime}})^{+}$,
where $\operatorname{\mathcal{D}}^{\prime}$ is obtained from
$\operatorname{\mathcal{D}}$ by deleting all $x$-adjacency lists with
$x\notin\\{x_{1},x_{2},\ldots,x_{k}\\}$. In [24], it is shown for general
directed graphs $G=(V,E)$ how to enumerate $E^{*}$ and $E^{+}$ sorted by first
coordinate (denoted by “row-wise”) with delay $\operatorname{O}(\Delta(G))$.
This approach translates to a semi-sorted enumeration and can be used on
$\operatorname{\mathcal{D}}$ in such a way that all $x$-adjacency lists with
$x\notin\\{x_{1},x_{2},\ldots,x_{k}\\}$ are ignored (so without
preprocessing). Thus, by using this procedure on $\operatorname{\mathcal{D}}$,
we can enumerate $q(\operatorname{\mathcal{D}})$ and
$q^{\prime}(\operatorname{\mathcal{D}})$ semi-sorted with delay
$\operatorname{O}(\Delta(\operatorname{\mathcal{D}}))$.

######  Theorem 34.

Semi-sorted $\operatorname{\textsc{Enum}}(\mathsf{S\text{-}RPQ})$ can be
solved with preprocessing $\operatorname{O}(|\operatorname{\mathcal{D}}|)$ and
delay $\operatorname{O}(\operatorname{\Delta}(\operatorname{\mathcal{D}}))$.

######  Proof 7.7.

Let $\operatorname{\mathcal{D}}$ be a graph database over $\Sigma$. We assume
that $V_{\operatorname{\mathcal{D}}}=[n]$ with $1\preceq 2\preceq\ldots\preceq
n$ (see Lemma 5).

Let
$q=(x_{1}\operatorname{\vee}x_{2}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})$
with $x_{1},x_{2},\ldots,x_{k}\in\Sigma$. Then
$q(\operatorname{\mathcal{D}})=\\{(u,v)\mid(u,x_{i},v)\in
E_{\operatorname{\mathcal{D}}},1\leq i\leq k\\}$. Obviously, we can in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$ compute this whole set by
moving trough the list for $V_{\operatorname{\mathcal{D}}}$ and for every
encountered node $u$ and every $i\in[k]$, we access the $x_{i}$-adjacency list
for $u$ and for all $v$ it contains, we add $(u,v)$ to a list. This list
contains exactly the elements from $q(\operatorname{\mathcal{D}})$ and is also
semi-sorted. Thus, we can compute $q(\operatorname{\mathcal{D}})$ completely
in the preprocessing and therefore enumerate it semi-sorted with constant
delay.

Next, we assume that

$q=(x_{1}\operatorname{\vee}x_{2}\operatorname{\vee}\ldots\operatorname{\vee}x_{k})(y_{1}\operatorname{\vee}y_{2}\operatorname{\vee}\ldots\operatorname{\vee}y_{k^{\prime}})$

with $x_{1},\ldots,x_{k},y_{1},\ldots,y_{k^{\prime}}\in\Sigma$, for which the
algorithm is more difficult.
Preprocessing: First, we construct
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ in time
$\operatorname{O}(|\operatorname{\mathcal{D}}||q|)=\operatorname{O}(|\operatorname{\mathcal{D}}|)$.
Since $G_{q}$, the underlying $\Sigma$-graph of the
$\operatorname{\mathsf{NFA}}$ for $q$, can be assumed to have nodes
$\\{1,2,3\\}$, where $1$ is the initial and $3$ the accepting state, and arcs
$\\{(1,x_{i},2)\mid 1\leq i\leq k\\}\cup\\{(2,y_{i},3)\mid 1\leq i\leq
k^{\prime}\\}$, we can assume that the underlying non-labelled graph of
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ has the following simple
structure: $V_{\boxtimes}(\operatorname{\mathcal{D}},q)=V_{1}\cup V_{2}\cup
V_{3}$ with $V_{i}=\\{(u,i)\mid u\in V_{\operatorname{\mathcal{D}}}\\}$ for
every $i\in[3]$, and $E_{\boxtimes}(\operatorname{\mathcal{D}},q)=E_{1}\cup
E_{2}$ with $E_{1}=\\{((u,1),(v,2))\mid\exists i\in[k]:(u,x_{i},v)\in
E_{\operatorname{\mathcal{D}}}\\}$ and $E_{2}=\\{((u,2),(v,3))\mid\exists
i\in[k^{\prime}]:(u,y_{i},v)\in E_{\operatorname{\mathcal{D}}}\\}$. The task
of enumerating $q(\operatorname{\mathcal{D}})$ reduces now to the task of
enumerating all reachable pairs $((u,1),(v,3))$ or, equivalently, to enumerate
$(E_{\boxtimes}(\operatorname{\mathcal{D}},q))^{*}\cap(V_{1}\times V_{3})$. We
further assume that the sets $V_{1}$, $V_{2}$ and $V_{3}$ are stored in
individual lists. This can be easily achieved during the construction of
$G_{\boxtimes}(\operatorname{\mathcal{D}},q)$: for every $u\in
V_{\operatorname{\mathcal{D}}}$ we add $(u,1)$ to a list that stores $V_{1}$,
then we construct lists for $V_{2}$ and $V_{3}$ analogously.

Finally, we modify $G_{\boxtimes}(\operatorname{\mathcal{D}},q)$ as follows.
We construct a Boolean array $S_{\text{in}}$ of size
$|V_{\operatorname{\mathcal{D}}}|$ (that can be addressed by the elements from
$V_{\operatorname{\mathcal{D}}}$) initialised with $0$ in all entries. Then,
we move through the list for $V_{1}$ and for every $(u,1)$ we encounter, we
move through its adjacency list and for every $(v,2)$ we encounter in this
adjacency list, we set $S_{\text{in}}[v]=1$. This procedure can be carried out
in $\operatorname{O}(|\operatorname{\mathcal{D}}|)$ and after its termination,
we have that $S_{\text{in}}[v]=0$ if and only if the in-degree of $(v,2)$ is
$0$. Next, we construct a Boolean array $S_{\text{out}}$ of size
$|V_{\operatorname{\mathcal{D}}}|$ (that can be addressed by the elements from
$V_{\operatorname{\mathcal{D}}}$) initialised with $0$ in all entries. Then,
we move through the list for $V_{2}$ and for every $(u,2)$ we encounter that
has a non-empty adjacency list, we set $S_{\text{out}}[u]=1$. This procedure
can be carried out in $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ and
after its termination, we have that $S_{\text{out}}[u]=0$ if and only if the
out-degree of $(u,2)$ is $0$. We move again through the list for $V_{2}$ and
we remove every encountered node $(v,2)$ if $S_{\text{in}}[v]=0$ or
$S_{\text{out}}[v]=0$; moreover, we move through the list for $V_{1}$ and for
every $(u,1)$ we encounter, we move through its adjacency list and we remove
every $(v,2)$ that we encounter if $S_{\text{in}}[v]=0$ or
$S_{\text{out}}[v]=0$. These two steps can again be carried out in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$. We have now removed all
nodes from $V_{2}$ with in-degree or out-degree $0$, and all arcs adjacent to
such nodes. Next, we remove all isolated nodes from $V_{1}$ and $V_{3}$. This
can be done by first computing all nodes from $V_{1}$ with out-degree $0$ and
all nodes from $V_{3}$ with in-degree $0$, which can be done in the same way
as we did for nodes from $V_{2}$ in time
$\operatorname{O}(|\operatorname{\mathcal{D}}|)$.
Enumeration: Let $Q$ be an empty queue. For every $i=1,2,\ldots,n$, we start a
BFS from $(i,1)$. Such a BFS is carried out until all nodes from the
neighbourhood of $(i,1)$ have been visited; thus, the BFS proceeds by visiting
all the neighbourhoods $N((j,2))$ for every $(j,2)\in N((i,1))$. From now on,
we add $(i,k)$ to $Q$ for every node $(k,3)$ that we visit for the first time.
Whenever $\operatorname{\Delta}(\operatorname{\mathcal{D}})$ steps are made by
the BFS after the last output while visiting a neighbourhood $N((j,2))$, we
produce after visiting this whole neighbourhood the first element from $Q$ as
output and remove this element from $Q$. In order to do this efficiently, we
store the elements of $Q$ not just as a list but also maintain two lists of
size $[n]$ over $\\{1,\dots,n\\}$ storing the elements currently in and the
elements already produced and deleted from $Q$, respectively. When the BFS
terminates, i. e., all neighbourhoods of the nodes from $N((i,1))$ have been
visited, then we produce the remaining elements in $Q$ (and thus emptying it)
and proceed with the BFS for the next node from $V_{1}$.
Correctness: The enumeration procedure goes through $n$ phases, where in each
such phase we perform a BFS in some vertex $u\in V_{1}$ and produce only pairs
of the form $(i,j)$, where $u=(i,1)$. This means it is sufficient to show for
each phase separately that we will produce all pairs of the form $(i,j)$
(where $u=(i,1)\in V_{1}$ is the BFS-start-node of this phase) without
duplicates and with the desired delay. Moreover, note that the enumeration is
obviously semi-sorted. Further, if $Q$ is never empty when we request the next
element, the delay is obviously in
$O(\operatorname{\Delta}(\operatorname{\mathcal{D}}))$ since visiting one
neighbourhood $N((j,2))$ requires at most
$\operatorname{\Delta}(\operatorname{\mathcal{D}})$ steps.

Let $u\in V_{1}$ and consider the phase of the enumeration procedure that
performs the BFS in $u$. The BFS visits all nodes of the neighbourhood
$N(u)=\\{v_{1},v_{2},\ldots,v_{h}\\}$ and marks them as visited, which can be
done in time
$\operatorname{O}(h)=\operatorname{O}(\operatorname{\Delta}(\operatorname{\mathcal{D}}))$.
Then it visits the complete neighbourhood $N(v_{1})$, then the complete
neighbourhood $N(v_{2})$ and so on until all nodes $\bigcup^{h}_{i=1}N(v_{i})$
are visited. For each $i\in[h]$, the BFS performs
$k_{i}=\sum_{j=1}^{i}|N(v_{j})|$ steps to visit all neighbourhoods
$N(v_{1}),\dots,N(v_{i})$, while producing at least
$q_{i}=\max\\{|N(v_{j})|\mid 1\leq j\leq i\\}$ different elements for $Q$. To
show that $Q$ is never empty, it suffices to show that
$\sum_{j=1}^{i}k_{j}\leq
q_{i}\operatorname{\Delta}(\operatorname{\mathcal{D}})$ for all $i$; note that
we request an element from $Q$ exactly after $\sum_{j=1}^{r_{i}}k_{j}$ steps
for some $r_{1},\dots,r_{x}\in[h]$ where $1=r_{1}<r_{2}<\dots,r_{x}$ and
$\sum_{j=r_{i}}^{r_{i+1}+1}k_{j}\geq\operatorname{\Delta}(\operatorname{\mathcal{D}})$
for each $i\in[x]$. Since the degree of $u$ is at most
$\operatorname{\Delta}(\operatorname{\mathcal{D}})$, we know that
$h\leq\operatorname{\Delta}(\operatorname{\mathcal{D}})$ which means
$\sum_{j=1}^{i}k_{j}\leq i\max\\{|N(v_{j})|\mid 1\leq j\leq
i\\}\leq\operatorname{\Delta}(\operatorname{\mathcal{D}})q_{i}$.

Finally, by using Lemma 32, we can plug together Theorems 33 and 34 in order
to obtain the following upper bound for
$\operatorname{\textsc{Enum}}(\bigvee(\mathsf{S\text{-}RPQ}\cup\mathsf{BT\text{-}RPQ}))$.

######  Theorem 35.

Semi-sorted
$\operatorname{\textsc{Enum}}(\bigvee(\mathsf{S\text{-}RPQ}\cup\mathsf{BT\text{-}RPQ}))$
can be solved with preprocessing
$\operatorname{O}(|q|^{2}|\operatorname{\mathcal{D}}|)$ and delay
$\operatorname{O}(|q|^{2}\Delta(\operatorname{\mathcal{D}}))$.

######  Proof 7.8.

Due to Theorems 33 and 34, both semi-sorted
$\operatorname{\textsc{Enum}}(\mathsf{S\text{-}RPQ})$ and semi-sorted
$\operatorname{\textsc{Enum}}(\mathsf{BT\text{-}RPQ})$ can be solved with
preprocessing $\operatorname{O}(|q||\operatorname{\mathcal{D}}|)$ and delay
$\operatorname{O}(\Delta(\operatorname{\mathcal{D}}))$. This obviously also
means that semi-sorted
$\operatorname{\textsc{Enum}}(\mathsf{S\text{-}RPQ}\cup\mathsf{BT\text{-}RPQ})$
can be solved with preprocessing
$\operatorname{O}(|q||\operatorname{\mathcal{D}}|)$ and delay
$\operatorname{O}(\Delta(\operatorname{\mathcal{D}}))$. Lemma 32 now implies
that semi-sorted
$\operatorname{\textsc{Enum}}(\bigvee(\mathsf{S\text{-}RPQ}\cup\mathsf{BT\text{-}RPQ}))$
can be solved with preprocessing
$\operatorname{O}(|q|^{2}|\operatorname{\mathcal{D}}|)$ and delay
$\operatorname{O}(|q|^{2}\Delta(\operatorname{\mathcal{D}}))$.

Since $q=\mathtt{a}\mathtt{a}\in\mathsf{S\text{-}RPQ}$ is sufficient to
express $\operatorname{\textsf{BMM}}$ as $\mathsf{RPQ}$-evaluation, Theorem 35
implies that enumerating (the $1$-entries of) Boolean matrix products can be
solved with linear preprocessing and $\operatorname{O}(n)$ delay, but, on the
other hand, this also immediately implies a matching data complexity lower
bound for the upper bound of Theorem 35.

######  Theorem 36.

If $\operatorname{\textsc{RPQ-Enum}}(\mathsf{S\text{-}RPQ})$ can be solved
with prep.
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$ and
delay
$\operatorname{O}(|\operatorname{\Delta}(\operatorname{\mathcal{D}})|^{1-\epsilon}f(|q|))$
for some function $f$ and $\epsilon\geq 0$, then the
$\operatorname{\textsf{com-BMM}}$-hypothesis fails.

######  Proof 7.9.

If $\operatorname{\textsc{RPQ-Enum}}(\mathsf{S\text{-}RPQ})$ can be solved
with preprocessing
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))$ and
with delay
$\operatorname{O}(|\operatorname{\Delta}(\operatorname{\mathcal{D}})|^{1-\epsilon}f(|q|))$
for some function $f$ and $\epsilon\geq 0$, then we can also compute
$q(\operatorname{\mathcal{D}})$ in total time
$\operatorname{O}((|V_{\operatorname{\mathcal{D}}}|^{3-\epsilon}f(|q|))+(|q(\operatorname{\mathcal{D}})||\operatorname{\Delta}(\operatorname{\mathcal{D}})|^{1-\epsilon}f(|q|)))$.
For the reduction of Lemma 17 this implies that we can solve
$\operatorname{\textsf{com-BMM}}$ in time
$\operatorname{O}(n^{3-\epsilon}+(n^{2}n^{1-\epsilon}))=\operatorname{O}(n^{3-\epsilon})$.

Compared to the full class of $\mathsf{RPQ}$s, the class
$\bigvee(\mathsf{S\text{-}RPQ}\cup\mathsf{BT\text{-}RPQ})$ is quite
restricted. However, comprehensive experimental analyses of query logs suggest
that quite restricted $\mathsf{RPQ}$s are still practically relevant: in the
corpus of more than $50$ million $\mathsf{RPQ}$s analysed in [18, Table $4$],
roughly $50\%$ of the $\mathsf{RPQ}$s are from $\mathsf{BT\text{-}RPQ}$ and
another $25\%$ are of the form $q=x_{1}x_{2}\ldots x_{k}$. Many of these
$\mathsf{RPQ}$s of the form $q=x_{1}x_{2}\ldots x_{k}$ also satisfy $k\leq 2$,
which means that they are $\mathsf{S\text{-}RPQ}$s [38].

## Conclusions

In this work, we thoroughly investigated the fine-grained complexity of
evaluating regular path queries. We focussed on what can be considered the
most simple case of $\mathsf{RPQ}$s, i. e., the solution set contains only
node pairs (and no witness paths) that are connected by _arbitrary_ paths (in
contrast to simple path semantics, trail semantics etc.). As explained in the
introduction, more powerful $\mathsf{RPQ}$s become computationally
intractable, so this simple setting is suitable for a fine-grained complexity
analysis. On the other hand, it can still be considered as a core
functionality to be found in typical graph query languages. We considered the
evaluation problems typically investigated in database theory (see Table 3):
the basic decision problems of Boolean evaluation and testing, and the
function problems of computing and counting the solution set, and finally the
enumeration variant.

For the non-enumeration variants, we were able to complement the upper bounds
obtained by the product-graph approach by conditional lower bounds (see Table
1). Hence, an algorithmic approach leading to strictly better upper complexity
bounds than the product-graph approach seems to require unlikely improvements
with respect to computing orthogonal vectors and Boolean matrices.

Our picture is much less complete for the enumeration variant of
$\mathsf{RPQ}$-evaluation (see Table 2). Although we produce many individual
conditional lower bounds (which rule out many algorithms), it is still open
whether enumeration with $\operatorname{O}(|\operatorname{\mathcal{D}}|)$
preprocessing and $\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ delay
(or any delay truly sublinear in the size of the graph database) is possible
(in data complexity); see also Question 6. Since finding an enumeration
algorithm that achieves a sublinear delay is definitely a worthwhile research
task (or, conversely, an enumeration algorithm with a delay bound as large as
the whole database seems disappointing), we investigated several approaches to
find enumeration algorithms with a sublinear delay. Our first such approach is
to drop the restriction of linear preprocessing and it turns out that if we
allow an additional factor of
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$
in the preprocessing (or
$\log(\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}}))\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$
if we do not want to use lazy-initialisation), then a delay of
$\operatorname{O}(|V_{\operatorname{\mathcal{D}}}|)$ is indeed possible (see
Theorem 26 and Corollary 28).333Recall that
$\operatorname{\overline{\operatorname{\Delta}}}(\operatorname{\mathcal{D}})$
is the average degree of $\operatorname{\mathcal{D}}$. Our second approach
shows that even linear preprocessing and constant delay is possible, if we are
satisfied with enumerating just a representative subset of the solution set
(see Theorem 30). Here, _representative_ means that if $u$ can reach any node
$v$ with a correctly labelled path, then at least one such witness pair exists
in the set (and likewise if $u$ can be reached by any node $v$ with a
correctly labelled path). While this variant is quite restricted in comparison
to the full evaluation task, it might be a worthwhile query result to start
with (e. g., before running a complete enumeration algorithm _without_
constant delay, we could first enumerate all these witnesses in constant delay
and see whether this information is already enough). Finally, in our third
approach, we identify a class of $\mathsf{RPQ}$s that can be enumerated with
linear preprocessing and delay
$\operatorname{O}(\Delta(\operatorname{\mathcal{D}}))$ (see Theorem
35).444Recall that $\Delta(\operatorname{\mathcal{D}})$ is the degree of
$\operatorname{\mathcal{D}}$. This result points out that the simplicity of
the regular expression of the query might be exploited to achieve a better
delay. This is particularly interesting given the fact that very simple
$\mathsf{RPQ}$s are already sufficient for conditional lower bound reductions
with respect to data complexity. Moreover, empirical work has shown that in
practical scenarios where regular expressions are used as means of querying
graph databases it is often the case that the regular expressions are rather
simple. In case that Question 6 can be answered in the negative, and if
enumeration algorithms with sublinear delay are of high relevance, we should
concentrate on algorithms that only work for a special and simple class of
$\mathsf{RPQ}$s.

A possible future research task with respect to the topic of this paper is to
answer Question 6. We conjecture that an algorithm that answers the question
in the affirmative will be non-trivial and likely to yield more general
algorithmic insights with respect to querying graphs with regular expressions.
If, by a conditional lower bound, it can be shown that the answer to the
question is negative, then the question arises for which $\mathsf{RPQ}$s a
sublinear delay is possible and for which it is (conditionally) not. Our
Theorem 35 constitutes a partial result in this regard.

## Acknowledgment

We wish to thank the anonymous reviewers of the conference version [25] of
this work for their valuable feedback. In particular, following the reviewer’s
comments and suggestions, we have included more background information and
comprehensive explanations of certain aspects, which substantially improved
the overall exposition of this paper.

## References

  * [1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams.  If the current clique algorithms are optimal, so is valiant’s parser.  SIAM J. Comput., 47(6):2527–2555, 2018.
  * [2] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443, 2014.
  * [3] Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu.  Matching triangles and basing hardness on an extremely popular conjecture.  SIAM J. Comput., 47(3):1098–1122, 2018.
  * [4] Rasmus Resen Amossen and Rasmus Pagh.  Faster join-projects and sparse matrix multiplications.  In Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, pages 121–126, 2009\.
  * [5] Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc.  Foundations of modern query languages for graph databases.  ACM Comput. Surv., 50(5):68:1–68:40, 2017.
  * [6] Arturs Backurs and Piotr Indyk.  Which regular expression patterns are hard to match?  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 457–466, 2016.
  * [7] Guillaume Bagan, Angela Bonifati, and Benoît Groz.  A trichotomy for regular simple path queries on graphs.  J. Comput. Syst. Sci., 108:29–48, 2020.
  * [8] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, pages 208–222, 2007.
  * [9] Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, and Michaël Thomazo.  Answering conjunctive regular path queries over guarded existential rules.  In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 793–799, 2017.
  * [10] Pablo Barceló.  Querying graph databases.  In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA \- June 22 - 27, 2013, pages 175–188, 2013.
  * [11] Pablo Barceló, Diego Figueira, and Miguel Romero.  Boundedness of conjunctive regular path queries.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 104:1–104:15, 2019.
  * [12] Pablo Barceló, Leonid Libkin, Anthony Widjaja Lin, and Peter T. Wood.  Expressive languages for path queries over graph-structured data.  ACM Transactions on Database Systems (TODS), 37(4):31:1–31:46, 2012.
  * [13] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt.  Constant delay enumeration for conjunctive queries: a tutorial.  ACM SIGLOG News, 7(1):4–33, 2020.
  * [14] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303–318, 2017.
  * [15] Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus.  Regular path queries in lightweight description logics: Complexity and algorithms.  J. Artif. Intell. Res., 53:315–374, 2015.
  * [16] Meghyn Bienvenu and Michaël Thomazo.  On the complexity of evaluating regular path queries over linear existential rules.  In Web Reasoning and Rule Systems - 10th International Conference, RR 2016, Aberdeen, UK, September 9-11, 2016, Proceedings, pages 1–17, 2016.
  * [17] Angela Bonifati, Wim Martens, and Thomas Timm.  An analytical study of large SPARQL query logs.  PVLDB, 11(2):149–161, 2017.
  * [18] Angela Bonifati, Wim Martens, and Thomas Timm.  Navigating the maze of wikidata query logs.  In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 127–138, 2019.
  * [19] Angela Bonifati, Wim Martens, and Thomas Timm.  An analytical study of large SPARQL query logs.  VLDB J., 29(2-3):655–679, 2020.
  * [20] Johann Brault-Baron.  De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order).  PhD thesis, University of Caen Normandy, France, 2013.
  * [21] Karl Bringmann.  Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661–670, 2014.
  * [22] Karl Bringmann.  Fine-grained complexity theory (tutorial).  In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 4:1–4:7, 2019.
  * [23] Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi.  Reasoning on regular path queries.  SIGMOD Record, 32(4):83–92, 2003.
  * [24] Katrin Casel, Tobias Friedrich, Stefan Neubert, and Markus L. Schmid.  Shortest distances as enumeration problem.  CoRR, abs/2005.06827, 2020.
  * [25] Katrin Casel and Markus L. Schmid.  Fine-grained complexity of regular path queries.  In 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, pages 19:1–19:20, 2021.
  * [26] Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood.  A graphical query language supporting recursion.  In Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987, pages 323–330, 1987.
  * [27] Massimo Equi, Roberto Grossi, Veli Mäkinen, and Alexandru I. Tomescu.  On the complexity of string matching for graphs.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 55:1–55:15, 2019.
  * [28] Massimo Equi, Veli Mäkinen, and Alexandru I. Tomescu.  Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails.  In SOFSEM 2021: Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25-29, 2021, Proceedings, pages 608–622, 2021.
  * [29] Diego Figueira.  Containment of UC2RPQ: the hard and easy cases.  In 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark, pages 9:1–9:18, 2020.
  * [30] Diego Figueira, Adwait Godbole, Shankara Narayanan Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner.  Containment of simple conjunctive regular path queries.  In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020, pages 371–380, 2020.
  * [31] Dominik D. Freydenberger and Nicole Schweikardt.  Expressiveness and static analysis of extended conjunctive regular path queries.  J. Comput. Syst. Sci., 79(6):892–909, 2013.
  * [32] François Le Gall.  Powers of tensors and fast matrix multiplication.  In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014, pages 296–303. ACM, 2014.
  * [33] Grzegorz Gluch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja.  The first order truth behind undecidability of regular path queries determinacy.  In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 15:1–15:18, 2019.
  * [34] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21–30, 2015.
  * [35] Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams.  Conditional hardness for sensitivity problems.  In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 26:1–26:31, 2017\.
  * [36] Leonid Libkin, Wim Martens, and Domagoj Vrgoc.  Querying graphs with data.  Journal of the ACM, 63(2):14:1–14:53, 2016.
  * [37] Katja Losemann and Wim Martens.  The complexity of regular expressions and property paths in SPARQL.  ACM Transactions on Database Systems (TODS), 38(4):24:1–24:39, 2013.
  * [38] Wim Martens.  Personal communication by email, October 28, 2019.
  * [39] Wim Martens, Matthias Niewerth, and Tina Trautner.  A trichotomy for regular trail queries.  In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, pages 7:1–7:16, 2020.
  * [40] Wim Martens and Tina Trautner.  Evaluation and enumeration problems for regular path queries.  In 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, pages 19:1–19:21, 2018.
  * [41] Wim Martens and Tina Trautner.  Bridging theory and practice with query log analysis.  SIGMOD Rec., 48(1):6–13, 2019.
  * [42] Wim Martens and Tina Trautner.  Dichotomies for evaluating simple regular path queries.  ACM Trans. Database Syst., 44(4):16:1–16:46, 2019.
  * [43] Alberto O. Mendelzon and Peter T. Wood.  Finding regular simple paths in graph databases.  SIAM Journal on Computing (SICOMP), 24(6):1235–1258, 1995.
  * [44] Bernard M. E. Moret and Henry D. Shapiro.  Algorithms from P to NP (Vol. 1): Design and Efficiency.  Benjamin-Cummings Publishing Co., Inc., USA, 1991.
  * [45] J. Ian Munro.  Efficient determination of the transitive closure of a directed graph.  Inf. Process. Lett., 1(2):56–58, 1971.
  * [46] Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi.  Regular queries on graph databases.  Theory of Computing Systems (ToCS), 61(1):31–83, 2017.
  * [47] Miguel Romero, Pablo Barceló, and Moshe Y. Vardi.  The homomorphism problem for regular graph patterns.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12, 2017\.
  * [48] Luc Segoufin.  Constant delay enumeration for conjunctive queries.  SIGMOD Record, 44(1):10–17, 2015.
  * [49] Robert Endre Tarjan.  Depth-first search and linear graph algorithms.  SIAM J. Comput., 1(2):146–160, 1972.
  * [50] Ryan Williams.  A new algorithm for optimal constraint satisfaction and its implications.  In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, pages 1227–1237, 2004.
  * [51] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theor. Comput. Sci., 348(2-3):357–365, 2005.
  * [52] Virginia Vassilevska Williams.  Algorithms column: An overview of the recent progress on matrix multiplication.  SIGACT News, 43(4):57–59, 2012.
  * [53] Virginia Vassilevska Williams.  Multiplying matrices faster than coppersmith-winograd.  In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887–898. ACM, 2012.
  * [54] Virginia Vassilevska Williams.  Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk).  In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 17–29, 2015.
  * [55] Virginia Vassilevska Williams.  Some open problems in fine-grained complexity.  SIGACT News, 49(4):29–35, 2018.
  * [56] Virginia Vassilevska Williams and R. Ryan Williams.  Subcubic equivalences between path, matrix, and triangle problems.  J. ACM, 65(5):27:1–27:38, 2018.
  * [57] Peter T. Wood.  Query languages for graph databases.  SIGMOD Rec., 41(1):50–60, 2012.
  * [58] Raphael Yuster and Uri Zwick.  Fast sparse matrix multiplication.  ACM Trans. Algorithms, 1(1):2–13, 2005.


# Fractional Stochastic Loewner Evolution and Scaling Curves

M. Ghasemi Nezhadhaghighi<EMAIL_ADDRESS>Department of Physics, Faculty
of Science, Shiraz University, Shiraz 71454, Iran

###### Abstract

The Stochastic Loewner equation, introduced by Schramm, gives us a powerful
way to study and classify critical random curves and interfaces in two-
dimensional statistical mechanics. New kind of stochastic Loewner equation,
called fractional stochastic Loewner evolution (FSLE), has been proposed for
the first time. Using the fractional time series as the driving function of
the Loewner equation and local fractional integrodifferential operators, we
introduce a large class of fractal curves. We argue that the FSLE curves,
besides the fractal dimension calculations, have crucial differences which
caused by the Hurst index of the driving function. This extension opens a new
way to classify different types of scaling curves based on the Hurst index of
the corresponding driving function. Such formalism appear to be suitable to
deal with the study of a wide range of two-dimensional curves appearing in
statistical mechanics or natural phenomena.

##  I Introduction

Studying the critical interfaces in two dimensions is in the interest of both
physicists and mathematicians because of at least two reasons: firstly because
of application in the physical systems such as domain walls in statistical
models bernard0 , iso-hight lines in rough surfaces rajab , zero-vorticity
lines of Navier-Stokes turbulence bernard , the continuum limit watersheds
dividing drainage basins hermaan2012 , iso-height contour lines of suspended
graphene sheets hermaan2016  and the two-dimensional projection of cumulus
clouds hermaan2021 . Secondly these interfaces when they posses conformal
symmetry can be studied by the exact methods of conformal field theory
(CFT)BPZ  and rigorous methods of Schramm-Loewner evolution (SLE)schramm .
Both of the above methods are based on the conformal symmetry of the
interfaces which is the property of the most of the systems at the critical
point in two dimensions.

However, it seems that systems with just scaling symmetry and not conformal
symmetry is also ubiquitous, some examples are rough surfaces rajab2 , two-
dimensional theory of elasticity Riva cardy , fractures in highly disordered
materials hermaan20121 , percolation with long-range correlated disorder
hermaan2013 , perimeters of multilayered and directed percolation clusters
hermaan20162 , and off-critical statistical systems shibasa2020 .

Figure 1: FSLE trace for FBM with $\kappa=2$, $71000$ steps for $H=0.25$ and
$H=0.5$ and $30000$ steps for $H=0.75$.

The non-locality or non-unitarity of the interaction are necessary to have a
system with such behavior. One way to study these systems is by using Loewner
equation similar as the ordinary SLE but with drift which is now just scale
invariant and not conformal invariant. Schramm-Loewner evolution is based on
describing curves in the upper half plane $\mathcal{H}$ by using a map
$g_{t}(z)$ which is mapping upper half plan minus hull to the upper half
plane. By hull we mean the curve and the region of the upper half plane which
is separated from infinity by the curve. This map satisfies the Loewner
equation

$\displaystyle\partial_{t}g_{t}(z)=\frac{2}{g_{t}(z)-U_{t}}$ (1)

with initial condition $g_{0}(z)=z$. Note that $U_{t}$ as a drift of the
process can be any continuous real function of time, which will be called
driving function. For ordinary SLE which is describing conformal Markov curves
$U_{t}$ is chosen to be the rescaled Brownian motion $\sqrt{\kappa}B_{t}$
(Brownian motion is a Gaussian Markov stochastic process with mean zero and
$E[B_{t}B_{s}=\min(t,s)$), then the hulls are fractal curves, whose properties
depend on $\kappa$ (for instance, their fractal dimension is
$d_{f}=\min(1+\frac{\kappa}{8},2)$) beffara .

In this paper we would like to use fractional Brownian motion and fractional
Weierstrass function as drifts of the stochastic Loewner equation. Such a
generalization is not new, SLE with Lévy drift was already discussed in both
physics and mathematics literature, see Gruzberg2 ; guan . Since the
introduced curves in these papers are not continues and not scale invariant
they are not useful to describe continues scale invariant objects.

Although several researches have been suggested that the corresponding driving
function to some fractal curves, display very distinctive anomalous diffusive
hermaan20162  or chaotic shibasa2020  behaviors.

In this paper we would like to study SLE with fractional Brownian motion (FBM)
and also fractional Weierstrass function as a drift. Fractional Brownian
motion is the continues generalization of Brownian motion and has scale
invariancy. The Weierstrass function is a real-valued function that is
continuous everywhere but differentiable nowhere. It is an example of a
fractal time series. To make SLE appropriate for these processes we will
introduce a new parametrization for the SLE curve to produce a scale invariant
hull. To study the special properties of the curve such as the probability of
hitting the real line and fractal properties of the scaling curves, we use
qualitative arguments in the spirit of our numerical experiment. The paper
organized as follows: first we will briefly review FBM and fractional
Weierstrass function and then we will introduce fractional SLE. Then we will
study some global properties of the fractional SLE curves such as the hitting
the boundary and fractal properties. We will confirm our qualitative arguments
by extensive numerical experiments. Finally in Section we give the main
conclusions of our work.

Figure 2: FSLE trace with fractional Weierstrass-Mandelbrot (FWM) function as
a drift with 60000 steps (in all plots $\alpha=H$).

##  II Fractional time series

This article develops a new version of stochastic Loewner evolution, obtained
by taking as driving function a fractional time series. Here we use two
different ways to generate a time series with the desired fractional
properties. The first is fractional Brownian motion and the latter is
fractional Weierstrass-Mandelbrot function. In this section, we discuss the
properties of these variations of fractional time series.

$I$. Fractional Brownian motion:

There are different representations for fractional Brownian motion, in this
paper we will use the definition by Mandelbrot and Van Ness MV ,

$\displaystyle
B_{t}^{H}=\frac{1}{\Gamma(H+\frac{1}{2})}\\{\int_{-\infty}^{0}((t-s)^{H-\frac{1}{2}}-(-s)^{H-\frac{1}{2}})dB_{s}$
$\displaystyle+\int_{0}^{t}(t-s)^{H-\frac{1}{2}}dB_{s}\\},$ (2)

where $B_{s}$ is the normal Brownian motion and $0<H\leq 1$. The $H=1$ has a
very simple form and it is called ballistic motion $B_{t}^{H}=\xi t$, where
$\xi$ is the random Gaussian noise. Fractional Brownian motion is not a Markov
process, however, it does have stationary increments. The autocorrelation is

$\displaystyle\langle
B^{H}_{t+T}B^{H}_{t}\rangle=\frac{1}{2}((t+T)^{2H}+t^{2H}-T^{2H}).$ (3)

For $T=0$, this implies anomalous diffusion with mean-square-displacement
$\langle B_{H}^{2}(t)\rangle=t^{2H}$, where the anomalous diffusion exponent
$\alpha=2H$ can take values between $0$ and $2$. In the sub-diffusive case,
$0<\alpha<1$, the increments are anti-correlated (anti-persistent) while the
motion is persistent (positive correlations between the steps) in the super-
diffusive case $1<\alpha<2$ Wada .

The FBM admits a version whose sample paths are almost surely Hölder
continuous of order strictly less than $H$. We should mention that up to the
level of numerical calculations most of the forthcoming arguments are also
valid for the generic drifts with scaling property, such as, non-stationary
FBM, Levy processes and continues time random walk Metzler .

$II$. Fractional Weierstrass-Mandelbrot function:

The fractional Weierstrass-Mandelbrot (FWM) function, is a random continuous
non differentiable mono fractal function. The discrete scale invariance (DSI)
properties of FWM function which was studied by Berry and Lewis in weierstrass
, is the key difference between FWM and FBM time series. A wide range of
physical phenomena such as sediment and turbulence Sornette1 ; Sornette2 ,
fractal properties of the landscapes and other enviromental data Burrough ,
contact analysis of elastic-plastic fractal surfaces Yan  and propagation and
localization of waves in fractal media Garcia , could be modeled by the
Weierstrass-Mandelbrot (WM) function.

The FWM function which is not Markov but has stationary increments can be
defined as follows

$\displaystyle
W(h,t)=\sum_{n=-\infty}^{\infty}\lambda^{-nH}(h(0)-h(\lambda^{n}t))e^{i\phi_{n}}$
(4)

where $h(t)$ can be any periodic function which is differentiable at zero and
$\phi_{n}$ is a random phase chosen from the interval $[0,2\pi]$ uniformly, to
make the series convergent we need to consider $0<H<1$ ($H$ is the Hurst index
of the process and the fractal dimension of the process is $2-H$). It was
proved in weierstrass ; Szulga  that the above process with $h(x)=e^{ix}$
converges to the fractional Brownian motion in the limit $\lambda\to 1$. In
our numerical calculation we will take $h(x)=e^{ix}$, however, our results are
extendable to the most generic cases nezhadgaghighi .

##  III Fractional Stochastic Loewner Evolution

In recent years, growing attention has been focused on the processes that take
place in random disordered environments Bressloff . As a result of this highly
irregular processes, the anomalous properties of transport processes, occurs.
Fractional calculus, (for example the appearance of the fractional time
derivative by a simple change $\frac{\partial}{\partial
t}\to\frac{\partial^{\alpha}}{\partial t^{\alpha}}$), is a powerful
mathematical tool for the investigation of these kinds of physical phenomena
such as motion in disordered media Barkai2008 . The history of fractional
calculus began in 1695 by Leibniz and after that several mathematicians have
defined fractional order derivatives. The well known definition is the
Riemann–Liouville, which can be derived considering the so-called
differintegral operators hilfer . The Riemann–Liouville definition is as
follows:

$\displaystyle\frac{d^{\alpha}f(t)}{[d(t-t_{0})]^{\alpha}}=\frac{1}{\Gamma(1-\alpha)}\frac{d}{dt}\int_{t_{0}}^{t}\frac{f(t^{\prime})}{(t-t^{\prime})^{\alpha}}dt^{\prime}.$
(5)

It is obvious, the operator ${d^{\alpha}}/{[d(t-t_{0})]^{\alpha}}$ is non-
local and further ${d^{\alpha}f(t)}/{[d(t-t_{0})]^{\alpha}}\neq 0$ for
$f(t)=$const. In order to correct this feature a new notion of local
fractional derivative (LFD) was introduced by Kolwankar . The definition of
the left-sided local fractional derivative of order $\alpha$ was defined by

$\mathbf{D}^{\alpha}f(t)=\lim_{{t\rightarrow
t^{\prime}}}\frac{d^{\alpha}[f(t)-f(t^{\prime})]}{[d(t-t^{\prime})]^{\alpha}}$
(6)

where the operatore in the RHS is the Riemann-Liouville derivative (5). An
easy calculation shows that

$\displaystyle\mathbf{D}^{\alpha}f(x)=\Gamma(1-\alpha)\lim_{{}_{\Delta\rightarrow
0}}\frac{f(x-\Delta)-f(x)}{\Delta^{\alpha}}.$ (7)

If one choose fractional Brownian motion or fractional Weierstrass-Mandelbrot
function as a drift of normal stochastic Loewner evolution (1), then the
result is just a simple curve with fractal dimension equal to one for
$H>\frac{1}{2}$ and it is space filling for $H<\frac{1}{2}$ (see ref.
nattaghfsle ). This is consistent with the Marshall-Rohde theorem which states
that if the drift is better than Hölder-1/2, then it defines a smooth (in some
appropriate sense) slit MR . To make SLE scale invariant under the fractional
drift we shall choose new parametrization for the equation by changing the
capacity of the conformal maps, i.e. $cap(K_{t}):=c$, as $dc=2(dt)^{2H}$. One
can write the SLE equation in the new parametrization as follows

$\displaystyle\mathbf{D}^{2H}g_{t}(z)=\frac{2}{g_{t}(z)-\sqrt{\kappa}B_{t}^{H}},$
(8)

where we used local fractional derivative (6). If one is further interested in
computing the discretized version of above equation (see 7), one can simply
use

$\displaystyle dg_{t}(z)=\frac{2(dt)^{2H}}{g_{t}(z)-\sqrt{\kappa}B_{t}^{H}}.$
(9)

We call the above equations, fractional Stochastic Loewner evolution (FSLE),
the velocity of the growing curve is different from the ordinary SLE.

The equation (9) has the scaling property in the following sense: the
conformal map
$\tilde{g}_{t}(z)=\frac{1}{\alpha^{4H^{2}}}g_{\alpha^{4H}t}(\alpha^{4H^{2}}z)$
with $\tilde{B}^{H}(t):=\frac{1}{\alpha^{4H^{2}}}B^{H}(\alpha^{4H}t)$
satisfies the same Loewner equation as (9). Using the above scaling property
one could claim that $\tilde{g}_{t}(z)$ is the conformal map that takes the
complement of the hull $\tilde{K}_{t}:=K_{\alpha^{4H}t}/\alpha^{4H^{2}}$ on to
the half plane in the way that $cap(\tilde{K}_{t})=2(dt)^{2H}$. In other words
by using the new parametrization we generated scaling conformal maps with
scaling hulls. If we take the FBM or FWM with stationary increments as a drift
then it is possible to generate also stationary FSLE, see Figs. (1) and (2).
The important point to get simple curves for a fractal drift is matching the
power of $dt$ with the fractal dimension of the drift. For example for a
fractal drift, deterministic or stochastic, with fractal dimension $d_{f}$ we
need to consider $(dt)^{4-2d_{f}}$ as a parametrization of FSLE, any other
choice will lead to a space filling hull or trivial curve with fractal
dimension one.

##  IV Results

In this section, we investigate the statistical properties of FSLE curves.
More precisely, we will study the problem of hitting time the real line which
shows a special properties and then we will study the fractal properties of
the scaling curves generated by fractional stochastic Loewner evolution.

###  IV.1 The problem of hitting the real line

One of the simplest properties of the above stochastic curves is the
probability of hitting the real line. As it is well known from the SLE
literature the problem of hitting the real line is equivalent to calculating
the probability that one arbitrary point $x$ on the real line is part of the
hull after finite time or not. This is equivalent to the probability that the
process $f_{t}(x)=g_{t}(x)-\sqrt{\kappa}B_{t}$ hits the origin schrammrhode .
A crude way to investigate this problem is to look at the drift and stochastic
terms of the equation

$df_{t}(x)=\frac{2(dt)^{2H}}{f_{t}(x)}-\sqrt{\kappa}dB_{t}^{H},$ (10)

if the drift term in RHS dominates then the curve will not touch the real line
otherwise it will touch the real line, let us review first the case
$H=\frac{1}{2}$. For $\kappa\leq 4$ the drift term will dominate and for
$\kappa>4$ the Brownian motion term so any change in the power of $dt$ in the
SLE, like
$df_{t}(x)=\frac{2(dt)^{1+\alpha}}{f_{t}(x)}-\sqrt{\kappa}dB_{t}^{\frac{1}{2}}$
will affect crucially the global properties of the curve. For positive
$\alpha$ the curve will touch the real line for any value of the $\kappa$ and
for negative $\alpha$ it will not touch the real line, hull is smooth curve.
The fractal dimension of the hull for positive $\alpha$ is two and for
negative $\alpha$ is one. The similar argument is tractable also for FSLE. For
small $\delta t$ the $H$ order of the fractional derivative of $B_{t}^{H}$ is
independent of the Hurst exponent, i.e.

$\displaystyle\frac{B_{t+\delta t}-B_{t}}{(\delta
t)^{H}}\approx\mathcal{O}((2\ln|\ln\delta t|)^{1/2}).$ (11)

Roughly one can write

$\displaystyle\frac{df_{t}(x)}{(\delta
t)^{H}}=\frac{2(dt)^{H}}{f_{t}(x)}-\sqrt{\kappa}\eta(t),$ (12)

where $\eta(t)$ is independent of $H$. Since $H=\frac{1}{2}$ is the critical
value for $H<\frac{1}{2}$ the first term will dominate and so the curve will
not touch the real line and for $H>\frac{1}{2}$ the curve will touch the real
line independent of the value of $\kappa$.

Figure 3: The probability of touching the real line $n/N$ with respect to the
number of realizations $N$ for the curves with 30000 points, in the inset: the
same quantity for the ordinary SLE.

To get more insight on the rule of the fractional differential one can look at
the method of the production of the hull in the numerical experiment. The
trace can be calculated numerically as an iteration process of infinitesimal
conformal mappings as follows

$\displaystyle\gamma(j\tau)=f_{1}\circ f_{2}\circ...\circ f_{j}(\xi_{j}),$
(13)

where $\xi_{j}$ is the FBM (FWM) and

$\displaystyle f_{j}(z)=\sqrt{(z-\xi_{j})^{2}-4\tau^{2H}}+\xi_{j}.$ (14)

The discretized driving force is constant in the interval $[(j-1)\tau,j\tau]$
where $\tau=\frac{t}{N}$, $N$ is the number of points on the curve, is the
mesh of the time. The most simple case is may be the constant force with
$\xi_{j}=0$ then one can get $\gamma_{t}=2\sqrt{t}N^{\frac{1}{2}-H}$. By this
equation one can expect that for $H>\frac{1}{2}$ in the numerical calculation
the curve will grow vertically faster than normal SLE. For $H>\frac{1}{2}$ the
curve will not reach to infinity in finite time. Of course the above curves
are trivial curves in the limit of large $N$, as explained in Kolwankar  we
just expect non-trivial solution for the equation (9) in the continuum limit
when the drift of FSLE has fractal support.

To check numerically the probability of touching the real line we used the
above iterative method and countered the number of curves that are touching
the line $y=\delta t$, where $\delta t$ is the average distant between
successive discrete points on the curve as a measure of minimum length. The
results for the probability of touching the real line, for the case when we
use FBM as a drift of FSLE, were shown in Fig. 3.

###  IV.2 Fractal properties of FSLE curves

Ordinary SLE (1) is a Loewner evolution with $U(t)=\sqrt{\kappa}B_{t}$, where
$B_{t}$ is Brownian motion. The $\kappa$ parameter in the theory, which is the
diffusivity of the Brownian motion, controls the scaling and fractal
properties of the SLE curves. As we mentioned earlier SLEκ is a random fractal
curve with the fractal dimension

$\displaystyle d_{f}=1+\frac{\kappa}{8}\hskip 28.45274pt(0<\kappa<8),$ (15)

where it becomes space-filling for $\kappa\geq 8$ with fractal dimension
$d_{f}=2$ schramm . Although SLE gives a powerful way to classify fractal
(scale invariant) curves in two dimensions but it was shown in Ref.
nezhadgaghighi  that the Weierstrass-Mandelbrot (WM) function as the drift of
the Loewner equation introduces a large class of fractal curves with discrete
scale invariance (DSI). Based on the extensive numerical simulation in Ref.
nezhadgaghighi , it was shown that, taking $\sqrt{\kappa}\Re(W(h,t))$ (see Eq.
(4) with Hurst index $H=\frac{1}{2}$) as the drift in Eq.(1), the solution of
WSLE is always a fractal curve with fractal dimension

$\displaystyle d_{f}=1+\frac{\kappa_{eff}}{8},$ (16)

where
$\kappa_{eff}=\kappa\frac{1}{2\ln\lambda}\int_{0}^{\infty}|\frac{h(0)-h(x)}{x}|^{2}dx$.

Figure 4: Fractal dimension $d_{f}$ of FSLE curves with 30000 points as
function of $H$. The same quantity as function of $\kappa$ is depicted in the
inset. The most interesting point about this result is the linear dependence
of $d_{f}$ versus $\kappa$ for different values of the Hurst index $H$.

In this work, we study the scaling and fractal properties of fractional SLE
curves in two-dimensions. Let us analyze the case in which the drift in Eq.
(9) is FBM or FWM (see Eq. (II) or (4), respectively). Note that, in order to
use the FWM function as a drift of FSLE, we rescale it by the coefficient
$\left[\frac{1}{2\ln\lambda}\int_{0}^{\infty}|\frac{h(0)-h(x)}{x}|^{2}dx\right]^{-1/2}$.
This allows us to generate the model-independent scaling curves (the scaling
exponents will be independent of $\lambda$ and $h(x)$).

The total length of the fractal curve, $S$, measured in units of the lattice
spacing, $a$, obeys a scaling relation as a function of system size, $L$, as

$\displaystyle S\sim\left(\frac{L}{a}\right)^{d_{f}}.$ (17)

To check the relation between the fractal dimension of FSLE curves and Hurst
index $H$ and diffusivity coefficient $\kappa$, we simply measured the average
length of curves $\langle S\rangle$ bounded by a semi-circle with radius $R$.
For fractal curves the relation $\langle S\rangle\sim R^{d_{f}}$ is expected.
The results for FSLE curves with different driving functions FBM are shown in
Fig .(4).

An interesting fact about FSLE curves is that all the results for fractal
properties of fractional stochastic Loewner evolution with FWM function as
driving function were the same as FBM. This the reason that the results were
not depicted in the figures. A second fact is that the fractal dimension
$d_{f}$ for FSLE curves with $H=$const surprisingly is a linear function of
the diffusivity parameter $\kappa$ (see inset of the figure (4)). Note also
that for fixed values of $\kappa$, the fractal dimension $d_{f}(H)$ changes
dramatically near the value $H=0.75$. We should note that FSLE curve with
$H=1.0$ is a line with $d_{f}=1$.

##  V Conclusion

In this work we have studied the fractional stochastic Loewner evolution. We
considered stochastic Loewner evolution with fractional Brownian motion
(fractional Weierstrass-Mandelbrot function) as a driving function. To
generate scale invariant curves we used the local fractional integro-
differential operator (9) instead of the normal differential equation (1).
Based on the theoretical arguments and numerical simulation we showed the FSLE
curves have a transition with the Hurst index $H$. For $H<\frac{1}{2}$ the
FSLE curves will not touch the real line and for $H>\frac{1}{2}$ the curve
will touch the real line independent of the value of $\kappa$. The critical
value $H=\frac{1}{2}$ corresponds to the ordinary SLE. Next, we have
investigated fractal property of the FSLE curves. As a result, we find that
the fractal dimension $d_{f}$, depends on the Hurst index $H$ and the
diffusivity exponent $\kappa$. The results in Ref. hermaan2016  are the best
support to our new approach to scaling curves. The Ref. hermaan2016  suggested
that the perimeters of multi-layered and directed percolation clusters at
criticality are the scaling limits of the Loewner evolution of an anomalous
Brownian motion with exponent $0<\alpha<1$. Investigating statistical models
with a similar properties could be interesting.

##  VI Acknowledgement

The authors would like to thank Mohammad Ali Rajabpour for the helpful
discussions and suggestions. This work would not have been possible without
early discussion with MAR. We also appreciate providing computing facilities
of Shiraz University.

## References

  * (1) M. Bauer and D. Bernard, Phys. Rep. 432, 115 (2006).
  * (2) A. A. Saberi, M. A. Rajabpour, S. Rouhani, Phys. Rev. Lett. 100, 044504 (2008).
  * (3) D. Bernard, et.al, Nature Phys 2, 124 (2006).
  * (4) E. Daryaei, N. A. M. Araújo, K. J. Schrenk, S. Rouhani, and H. J. Herrmann,Phys. Rev. Lett. 109, 218701 (2012).
  * (5) I. Giordanelli, N. Posé, M. Mendoza and H. J. Herrmann, Scientific Reports volume 6, Article number: 22949 (2016)
  * (6) M. N. Najafi, J. Cheraghalizadeh, and H. J. Herrmann, Phys. Rev. E 103, 052106 (2021)
  * (7) A. A. Belavin, A. M. Polyakov, A. B. Zamolodchikov, Nucl. Phys. B 241(1984) 33380
  * (8) O. Schramm, Israel. J. Math. 128, 221 (2000).
  * (9) M. A. Rajabpour and S. M. V. Alaei, Phys. Rev. E 80, 011115 (2009).
  * (10) V. Riva, J. Cardy, Phys. Lett. B 622 (2005) 339-342
  * (11) A. A. Moreira, C. L. N. Oliveira, A. Hansen, N. A. M. Araújo, H. J. Herrmann, and J. S. Andrade, Jr. Phys. Rev. Lett. 109, 255701 (2012).
  * (12) K. J. Schrenk, N. Posé, J. J. Kranz, L. V. M. van Kessenich, N. A. M. Araújo, and H. J. Herrmann Phys. Rev. E 88, 052102 (2013)
  * (13) H. F. Credidio, A. A. Moreira, H. J. Herrmann, and J. S. Andrade, Jr. Phys. Rev. E 93, 042124 (2016)
  * (14) Y. Shibasakia and M. Saitob, Chaos 30, 113130 (2020)
  * (15) V. Beffara, Ann. Probab. 36, 1421 (2008).
  * (16) I. Rushkin,P. Oikonomou, I. A. Gruzberg, L. P. Kadanoff,J. Stat. Mech. (2006) P01001 and J. Stat. Mech. (2008) P01019
  * (17) Q. Guan and M. Winkel, Ann. Probab. 36(4): 1221-1266 (2008);Q. Guan, [arXiv: 0705.2321]; Z-Q Chen and S. Rohde, Communications in Mathematical Physics, 285, 799 (2009).
  * (18) B. B. Mandelbrot, J.W. Van Ness, Fractional Brownian Motions, Fractal Noises and Applications, SIAM Rev (1968) 10:422-37
  * (19) A. H. O. Wada and T. Vojta, Phys. Rev. E 97, 020102(R) (2018)
  * (20) R. Metzler, J. Klafter, Physics Reports, 339(2000)1-77
  * (21) M.V. Berry, Z. V. Lewis, Proc. R. Soc. Lond. A, 370 (1980) 459-484
  * (22) D. Sornette, Physics Reports 297 (1998) 239-270
  * (23) D. Sornette, Critical Phenomena in Natural Sciences. Chaos Fractals, Selforganization and Disorder: Concepts and Tools(2000) Heidelberg, Germany: Spring-Verlag.
  * (24) P. A. Burrough, Nature 294 (1981) 240242 .
  * (25) W. Yan and K. Komvopoulos, J. Appl. Phys. 84 (1998) 3617
  * (26) A. M. Garcia-Garcia, E. Cuevas, Phys. Rev. B 82, 033412 (2010)
  * (27) J. Szulga, F. Molz, Journal of Statistical Physics, 104(2001)1317-1348 and V. Pipiras, M.S. Taqqu, Fractals, 8 (2000) 369-384
  * (28) M. Ghasemi Nezhadhaghighi and M. A. Rajabpour, Phys. Rev. E 82, 061101 (2010)
  * (29) Paul C. Bressloff and Jay M. Newby Rev. Mod. Phys. 85, 135 (2013)
  * (30) S. Burov and E. Barkai, Phys. Rev. E 78, 031112 (2008)
  * (31) Rudolf Hilfer, ed. Applications of fractional calculus in physics. World scientific, (2000).
  * (32) K. M. Kolwankar and A. D. Gangal, Chaos. 1996 6(1996) 505-513, Phys. Rev. Lett. 80, (1998)214-217
  * (33) S. Tizdast, Z. Ebadi, J. Cheraghalizahe, M. N. Najafi, José S. Andrade, Hans J. Herrmann, arXiv:2105.02694
  * (34) D. Marshall, S. Rohde, J. Amer. Math. Soc. 18 (2005), 763-778
  * (35) S. Rohde, O. Schramm, Annals Math. 161 (2005) 879-920