Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

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, and it was recently proven that solving it in time O(|E|1−ϵ|P|) or O(|E||P|1−ϵ) is hard under OVH, the Orthogonal Vectors Hypothesis, and thus under SETH, the Strong Exponential Time Hypothesis (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 δPeer reviewe