Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
Massimo Equi, Veli Mäkinen, Alexandru Ioan Tomescu · Theoretical Computer Science · 2023
The string matching problem on a node-labeled graph G=(V,E) asks whether a given pattern string P equals the concatenation of node labels of some path in G. This is a basic primitive in various problems in bioinformatics, graph databases, or networks, recently proven to have a O(|E||P|)-time lower bound, under the Orthogonal Vectors Hypothesis (OVH) (Equi et al. (2019) [11]). We consider its indexed version, where the graph is indexed to support string queries. We show that, under OVH, no polynomial-time index of the graph performed in time O(|E|α) can support querying P in time O(|P|+|E|δ|P|β), with either δ<1 or β<1. We present our techniques as a general framework, introducing the notion of linear independent-components (lic) reduction, from which we derive our result. This allow us to also translate the quadratic conditional lower bound of Backurs and Indyk (2015) [47] for the problem of matching a query string inside a text, under edit distance, into an analogous tight quadratic lower bound for its indexed version. This improves the recent result of Cohen-Addad, Feuilloley and Starikovskaya (2019) [48], with a slightly different boundary condition. We also apply our technique to obtain the first quadratic indexing lower bounds for Fréchet distance and rooted unlabeled subtree-isomorphism queries.