# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Conditional Lower Bounds  
Before diving into compressed indexes for labeled graphs, we spend a paragraph on the complexity of matching strings on labeled graphs. The main results in this direction are due to [PERSON] and [PERSON] [51] and to [PERSON] et al. [52; 53; 54], and we considered the online version of the problem: both pre-processing and query time are counted towards the total running time. The former work [51] proved that, unless the Strong Exponential Time Hypothesis (SETH) [55] is false, _in the worst case_ no algorithm can match a regular expression of size \(e\) against a string of length \(m\) in time \(O((m\cdot e)^{1-\delta})\), for any constant \(\delta>0\). Since regular expressions can be converted into NFAs of the same asymptotic size, this result implies a quadratic conditional lower-bound to the graph pattern matching problem. [PERSON] et al. [54] improved this result to include graphs of maximum node degree equal to two and deterministic directed acyclic graphs. Another recent paper from [PERSON] and [PERSON] [56] established a similar hardness result for the problem of determining whether a NFA accepts a given word: they showed that, provided that the NFA is sparse, a subquadratic algorithm for the problem would falsify SETH. All these results are based on reductions from the orthogonal vectors problem: find two orthogonal vectors in two given sets of binary \(d\)-dimensional vectors (one can easily see the similarity between this problem and string matching). The orthogonal vectors hypothesis (OV) [57] states that the orthogonal vectors problem cannot be solved in strongly subquadratic time. A further improvement has recently been made by [PERSON] [58], who proved that even shaving logarithmic factors from the running time \(O(m\cdot e)\) would yield surprising new results in complexity theory, as well as falsifying an hypothesis recently made by [PERSON] and [PERSON] in Reference [59] on the fine-grained complexity of SAT solvers. As noted above, in the context of our survey, these lower bounds imply that the sum between the construction and query times for a graph index cannot be sub-quadratic unless important conjectures in complexity theory fail. These lower bounds, however, do not rule out the possibility that a graph index could support efficient (say, subquadratic) queries at the cost of an expensive (quadratic or more) index construction algorithm. The more recent works of [PERSON] et al. [52; 53] addressed precisely this issue: they proved that no index that can be built in polynomial time (\(O(e^{\alpha})\) for any constant \(\alpha\geq 1\)) can guarantee strongly sub-quadratic query times, that is, \(O(e^{\beta}m^{\beta})\) query time for any constants \(\delta<1\) or \(\beta<1\). This essentially settles the complexity of the problem: assuming a reasonably fast (polynomial time) index construction algorithm, subpath-query times need to be at least quadratic (\(O(m\cdot e)\)) in the worst case. Since these bounds are matched by existing on-line algorithms [60], one may wonder what is the point of studying graph indexes at all. As we will see, the answer lies in parameterized complexity: even though pattern matching on graphs/regular expressions is hard _in the worst case_, it is indeed possible to solve the problem efficiently in particular cases (for example, trees [35] and particular regular expressions [51]). Ultimately, in Section 3.8 we will introduce a complete hierarchy of labeled graphs capturing the hardness of the problem.