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

DOI10.1007/978-3-030-67731-2_44zbMATH Open1490.68151arXiv2002.00629OpenAlexW3126170517MaRDI QIDQ831852FDOQ831852

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

Publication date: 24 March 2022

Abstract: 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 node labels equals $P$. This is a basic primitive in various problems in bioinformatics, graph databases, or networks. The hardness results of Backurs and Indyk (FOCS 2016) imply that this problem cannot be solved in better than $O(|E||P|)$ time, under the Orthogonal Vectors Hypothesis (OVH), and this holds even under various restrictions on the graph (Equi et al., ICALP 2019). In this paper we consider its offline version, namely the one in which we are allowed to index the graph in order to support time-efficient string matching queries. Indeed, it was tantalizing in the string matching community to believe that sub-quadratic time queries can be achieved, e.g. at the cost of a high-degree polynomial-time indexing. We disprove this belief, showing that, under OVH, no polynomial-time index can support querying $P$ in time $$, with either $delta<1$ or $$. We prove this tight bound employing a known self-reducibility technique, e.g. from the field of dynamic algorithms, which translates conditional lower bounds for an online problem to its offline version. As a side-contribution, we formalize this technique with the notion of linear independent-components reduction, allowing for a simple proof of our result. As another illustration of our technique, we also translate the quadratic conditional lower bound of Backurs and Indyk (STOC 2015) for the problem of matching a query string inside a text, under edit distance. We obtain an analogous tight quadratic lower bound for its offline version, improving the recent result of Cohen-Addad, Feuilloley and Starikovskaya (SODA 2019), but with a slightly different boundary condition.

Full work available at URL: https://arxiv.org/abs/2002.00629

Recommendations

• On Hardness of Several String Indexing Problems
• Lower bounds for text indexing with mismatches and differences
• Complexity issues of string to graph approximate matching
• On the complexity of approximately matching a string to a directed graph

zbMATH Keywords

lower boundscomplexity theoryedit distancereductionsindexinggraph queryexact pattern matchingorthogonal vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15) Algorithms on strings (68W32)

Cites Work

• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• On the complexity of \(k\)-SAT
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Jewels of Stringology
• A faster algorithm computing string edit distances
• Distance oracles beyond the Thorup-Zwick bound
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Wheeler graphs: a framework for BWT-based data structures
• On the complexity of recognizing Wheeler graphs
• Degenerate string comparison and applications
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Title not available (Why is that?)
• Pattern matching in hypertext
• On-line pattern matching on similar texts
• Orthogonal vectors indexing
• Faster Online Elastic Degenerate String Matching
• Regular Languages meet Prefix Sorting
• Indexing variation graphs
• Lower bounds for text indexing with mismatches and differences
• More applications of the polynomial method to algorithm design
• Title not available (Why is that?)
• An Efficient Elastic-Degenerate Text Index? Not Likely
• Linear time construction of indexable founder block graphs

Cited In (11)

• Fine-Grained Complexity of Regular Path Queries
• \(k\) one-way heads cannot do string-matching
• On the Complexity of String Matching for Graphs
• Wheeler languages
• Algorithms and complexity on indexing founder graphs
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Elastic founder graphs improved and enhanced
• Linear time construction of indexable elastic founder graphs
• Solving string problems on graphs using the labeled direct product
• Chaining of maximal exact matches in graphs
• Wheeler maps

Uses Software

• HISAT
• vg

This page was built for publication: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831852)