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

Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu

We consider the following string matching problem on a node-labeled graph $G=(V,E)$: given a pattern string $P$, decide whether there exists a path in $G$ whose concatenation of no…