Conditional Lower Bounds for String Matching in Labelled Graphs

The classic problem of string matching consists in finding a match for a shorter pattern string $P$ into a longer text string $T$. This problem has been extensively studied throughout the years, but the core fundamental complexity result was already discovered in the ’70s, when the problem was proven to be solvable in linear time [19]. The problem of String Matching in Labelled Graphs (SMLG) is a generalization of the string matching problem, where we look for matches of $P$ not in a text but in a graph with nodes labelled by single characters. The SMLG problem first received attention in the ’90s [20, 3, 4] due to potential applications in network searches and, later on, applications such as bioinformatics [15], graph databases [5] and heterogeneous networks [24] motivated it anew. Finding quadratic upper bounds of the form $O(|E||P|)$ was possible for different variations of the problem [4, 21, 25], and those results were later proven to be optimal under some complexity hypotheses for other problems [10, 11]. This conditional lower bounds falls into the field of the so-called fine-grained complexity, and in this work we aim to showcase how fine-grained complexity lower bounds are achieved and why they changed the game for polynomial problems, in particular for SMLG.

The journey of fine-grained complexity begins in the early 2000s, when Impagliazzo, Paturi and Zane [17, 18] put forward a hypothesis on the complexity of SAT in conjunctive normal form (CNF-SAT). The hypothesis was named Strong Exponential Time Hypothesis (SETH), and states that no algorithm can solve a CNF-SAT instance over $n$ variables in time $O(2^{\alpha n})$, where . This hypothesis still holds its ground, since no one has been able to disprove it as of the writing of this work. A few years later, Williams [26] showed how SETH can be used to prove conditional lower bounds for polynomial problems. Among others, this work presented a fine-grained reduction from CNF-SAT to the Orthogonal Vectors (OV) problem, that is a reduction that requires subexponential time, which in this case was $O(2^{\frac{n}{2}})$¹¹1We acknowledge that this use of the term “subexponential” is improper, as a real subexponential complexity should be of the form $O(2^{o(n)})$. Nonetheless, we will use this wording for lack of a better term.. In the OV problem, we are given sets $X$ and $Y$ of $n$ binary vectors of dimension $d$, and we are asked to find a pair $(x,y)$ of orthogonal vectors $x\in X$ and $y\in Y$. So far, no algorithm was able to solve OV in $O(n^{2-\epsilon }\text{poly}(d))$ time, and this fact is referred to as the Orthogonal Vectors Conjecture (OVC). Thus, the reduction between CNF-SAT and OV shows that a $O(n^{2-\epsilon }\text{poly}(d))$ time algorithm for OV would disprove SETH, or $\text{SETH}\Rightarrow \text{OVC}$, and this is an important connection between exponential and polynomial complexities. Indeed, this allows to prove SETH-based lower bounds by reducing from OV instead of CNF-SAT, a choice that usually makes reductions cleaner and the lower bounds more reliable as, in principle, OVC might be true even if SETH fails.

After this initial connection, many other lower bounds for polynomial problems conditioned on SETH have been shown. Among these, one of the most celebrated examples is probably the lower bound for the problem of computing edit distance (EDIT) between two strings $A$ and $B$ [6]. The textbook algorithm for EDIT solves the problem in $O(n^2)$ time, where $n=|A|=|B|$, and has been known for decades, but the first lower bound was achieved only thanks to a fine-grained reduction from OV. This brings us back to SMLG, as the conditional lower bound for EDIT has consequences also for matching strings in graphs. Indeed, there are different variations of SMLG, and one thing to specify is whether the matches for pattern $P$ in graph $G$ should be exact or approximate, and whether walks are admitted (same nodes can be matched multiple times) or only paths (every node must be matched ones). To allow for approximate matches, one has to specify what an approximate match is. We could be very permissive, and allowing edit operations to occur both in the pattern and in the graph. This possibility was explored and proven to be an NP-hard problem [4]. If we then ask for a path spelling a string at minimum edit distance from $P$, then we incur in the following problem: if we label every node with character $a$ and we query for pattern of length $|P|=|V|$, then we are solving the Hamiltonian Path problem, known to be NP-hard. Thus, let us look for a walk spelling a path at minimum edit distance from $P$. In this setting, an $O(|E||P|)$ algorithm exists [21, 25], and since a string can be viewed as a chain of nodes, EDIT is a special case of this problem, and thus the conditional quadratic lower bound matches the upper bound.

As previously mentioned, the version of SMLG where we ask for a walk in $G$ spelling an exact match for $P$ has also received a conditional quadratic lower bound [10, 11]. This result however could not be achieved as a simple adaptation of other lower bounds, and needed a custom fine-grained reduction from OV. Moreover, this highlights also a remarkable difference between the text and graph case: while the problem is linear for texts, it is quadratic for graphs, while in the approximate case it is quadratic for both texts and graphs.

At this point, one natural approach to find upper bounds could be to change the setting to try to play around the lower bound. For example, one could ask if queries to the pattern could be solved efficiently, that is in subquadratic time, after spending quadratic or even polynomial time indexing the graph. Unfortunately, also this question was answered negatively, as Equi, Mäkinen and Tomescu [11] proved that superpolynomial indexing time is needed in order to achieve subquaratic time queries. This result was given as a special case of a more general technique, which allows to claim that the same type of indexing lower bound holds for any problem with a fine-grained reduction from OV respecting a certain structure.

All these fine-grained results where further strengthened after the introduction of new hardness hypotheses [1] believed to be more reliable than SETH. Using this framework, Gibney, Hoppenworth, and Thankachan [16] showed that the hardness of SMLG can be based on these hypotheses, and this improved the lower bound proving that even shaving logarithmic factors from the quadratic time complexity is hard. This enhanced lower bound is given by reducing from a problem called Formula-SAT, a generalisation of CNF-SAT, and due to the nature of the problem the design of the reduction had to be modified into a structure of recursively-defined gadgets.

As a final note, although this work is centred around the quadratic lower bounds for SMLG, it is important to remember that there are graphs for which the problem is easier to solve, and even linear time complexity can be achieved. This is the case for instance for Wheeler graphs [14], certain (Elastic) Founder graphs [23, 13], trees [22] and Funnels [7]. More in general, it is also possible to parametrize the complexity in a parameter expressing the “sortability” of the graph [9, 8].

In the sections that follow, we will introduce SMLG more formally as well as the fine-grained complexity hypotheses. As a warm up, we show how to reduce CNF-SAT to OV in subexponential time, as the reduction is very central to the field and very concise at the same time. Then, we give an overview of the main ideas behind different fine-grained reductions for SMLG that were given throughout the years, with the goal of showcasing the different features among them.

A pattern string $P$ is a string of characters drawn from an alphabet $\mathrm{\Sigma }$, has length $|P|$, and $P[i]$ is its $i$-th character. We say that $G=(V,E,\mathrm{\ell })$ is a labeled graph if $V$ is a set of nodes, $E$ a set of edges over $V$, and $\mathrm{\ell }:V\to \mathrm{\Sigma }$ is a labeling function that associate a character of alphabet $\mathrm{\Sigma }$ to every node in $V$. Moreover, we say that $P$ has a match in $G$ if there is a walk of nodes $v_1,\mathrm{\dots },v_m$ in $G$ such that $P=\mathrm{\ell }(v_1)\mathrm{\cdots }\mathrm{\ell }(v_m)$. Then, SMLG is formally defined as follows.

Note that in this definition of SMLG we ask for a walk to exist and not a simple path. This is because, if we are not allowed to repeat nodes, there is a straightforward reduction from the Hamiltonian path problem, making the problem NP-Complete. To see this, simply define $\mathrm{\Sigma }=\{\text{A}\}$, $P=\text{A A}\mathrm{\cdots }\text{A}$, $|P|=|V|$ and $\mathrm{\ell }(v)=\text{A}$ for every $v\in V$. In other words, we are asking to find a match for a path as long as the number of nodes, and if we can match every node only once, we are finding an Hamiltonian path.

Quadratic algorithms have been the best we could achieve for general formulations of SMLG, and the reason is because better solutions are unlikely to exist. In order to show that we have reached the optimum, we of course need lower bound techniques, and here is where fine-grained complexity comes into play, has it provides us the means of proving such lower bounds via reductions. Thus, before presenting the conditional lower bounds for SMLG, we first introduce fine-grained complexity tools and basic notions needed to understand the later reductions. The central hypothesis in fine-grained complexity is the Strong Exponential Time Hypothesis (SETH).

This hypothesis is called strong to remark that it is a stronger statement when compared to the more forgiving Exponential Time Hypothesis (ETH), which forbids the existence of algorithms solving CNF-SAT in $O(2^{o(n)})$ time. To give an example, if an algorithm solves CNF-SAT in $O(2^{\frac{n}{2}})$, SETH is violated but ETH is not.

There are polynomial problems for which hardness conjectures are independently believed, and for which there also exist efficient reductions from CNF-SAT. When possible, it is preferred finding a reduction from these problems instead of reducing directly from CNF-SAT. This way, multiple hypotheses have to fail to invalidate the conditional lower bound, and moreover we have to deal only with polynomial complexities in the analysis, instead of having both exponential and polynomial complexities.

The polynomial problems most commonly used as a base for reductions to other polynomial problems are Orthogonal Vectors, All Pairs Shortest Paths, and $3$-SUM [27]. In this work, we focus solely on Orthogonal Vectors (OV) which, intuitively, asks the following: given two sets of binary vectors, answer whether it is possible to find a vector in the first set and a vector in the second set so that they are orthogonal.

The notation $x[i]\cdot y[i]$ indicates the scalar product when used for two single entries of vectors $x$ and $y$, while it refers to the dot product $x\cdot y$ when applied on the vectors themselves. Currently, it is conjectured that no algorithm can solve OV in truly subquadratic time.

One central result in fine-grained complexity is that SETH and OVC are connected via a subexponential reduction. We give a proof of this result, as we find it easy to follow and very instructive at the same time.

Using fine-grained reductions, we can provide a quadratic lower bound for exact SMLG conditioned on SETH and OVC. In this section, we state this lower bound in its simplest form, focusing on giving the intuition behind the structure of the reduction. In Section 5, we explain a few different ways of strengthening this result.

The conditional lower bound for exact SMLG is formally stated as follows.

We now sketch the idea of the reduction from OV used to show the lower bound [12, 10]. Starting from sets of vectors $X$ and $Y$, the reduction builds pattern $P$ and graph $G$ in $O(nd)$ time, such that $P$ matches in $G$ if and only if there is a pair of orthogonal vectors between $X$ and $Y$. We first describe how to construct the pattern, and then the graph.

Patter $P$ is defined over alphabet $\mathrm{\Sigma }=\{\text{b},\text{e},\text{0},\text{1}\}$, has length $|P|=O(nd)$, and can be built in $O(nd)$ time from the first set of vectors $X=\{x_1,\mathrm{\dots },x_n\}$. Namely, we define

where $P_{x_i}$ is a string of length $d$ that is just a copy of $x_i\in X$, that is $x_i[h]=0\Rightarrow P_{x_i}[h]=\text{0}$ and $x_i[h]=1\Rightarrow P_{x_i}[h]=\text{1}$, for $1\le i\le n$ and $1\le h\le d$. Here we are using characters b and e to mark the beginning and the end of each subpattern $P_{x_i}$, respectively. Substrings bb and ee instead respectively mark the beginning and the end of the entire pattern, forcing it to start and end the match at specific locations in the graph.

Graph $G$ is built on top of the second set of vectors $Y=\{y_1,\mathrm{\dots },y_n\}$, and consists of different substructures hierarchically organized: gadgets encoding single entries of the vectors are combined into gadgets encoding entire vectors, which are further combined to form the whole graph. At a macroscopic level, we want to structure the graph in three conceptual rows stacked on top of each other, as exemplified in Figure 2. In the graph, characters b and e force the subpatterns to correctly align to the gadgets encoding entire vectors, and thus forcing the entire match to synchronize at the subpattern level. Then, the idea is to make the top and bottom rows able to match any properly-synchronizing prefix and suffix of the pattern, respectively, while the middle row shall match only those subpatterns encoding vectors that are orthogonal to some vector in $Y$. Thus, if we force a match to start from the top or middle row, and end in the middle or bottom row, at least one subpattern must match in the middle row, which will be possible only if the pair of vectors encoded by that subpattern and the graph gadget it matches in are orthogonal. As shown in Figure 2, we can force this behaviour by introducing paths of two nodes spelling the string bb in the top and middle row. In pattern $P$, this string is present only as a prefix, marking the beginning of the pattern. The same logic applies to paths of two nodes spelling the string ee in the middle and bottom row, since that string is present in $P$ only as a suffix.

As already mentioned, the single graph gadgets in the middle row $G_W$ must provide the following property.

Let us see how to construct such gadgets. Since ${\sum }_{h=1}^{d}x[h]\cdot y[h]=0$ when every term of the sum is $0$, the idea is to make the graph force the pattern to have character $S[h]=0$ when $y[h]=1$, while letting $S[h]$ be either 0 or 1 when $y[h]=0$. To achieve this, first we place a path of $h$ nodes all with label 0, then we add a node with label 1 for those positions such that $y[h]=0$, and finally we fully connect nodes encoding the entry at position $h$ to those for position $h+1$, for $1\le h\le d$. Figure 3 shows an example of the entire middle row $G_W$, where gadget $G_W^{(j)}$ encodes vector $y_j$, for $1\le j\le n$, using nodes with labels b and e to mark the beginning and the end of the gadgets. It then holds the following.

In order to complete the reduction, it remains only to build the universal gadgets for the top and bottom rows of $G$. This is easily achieved by following the same construction scheme as for gadgets $G_W^{(j)}$, and just placing both a 0-node and a 1-node at every position. Finally, we remark that in order to make all possible “shifts” of the pattern possible, the top and bottom rows of $G$ must have $2(n-1)$ universal gadgets. We can now claim the following.

Notice that every gadget $G_W^{(j)}$ or universal gadget consists of $O(d)$ nodes and edges, and there are $O(2(n-1)+n+2(n-1))=O(n)$ such gadgets, for a total size of $O(nd)$. This consideration together with Lemma 7, 8 and 9 let us claim Theorem 6.

After having established a first quadratic conditional lower bound for SMLG, we now want to see how far we can push it. What if there are constraints on the graph, or on the alphabet? Can we make up for the quadratic complexity if we first build an index? Can we condition the lower bound on other hypotheses to make it even stronger? Let us explore these questions.