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

DOI10.1007/978-3-030-67731-2_44MaRDI QIDQ831852zbMATH OpenOpenAlexFDO

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

Publication date 24 March 2022

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

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)

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.

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

Cites work

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

Cited in

(11)

• \(k\) one-way heads cannot do string-matching
• Fine-Grained Complexity of Regular Path Queries
• Wheeler languages
• On the Complexity of String Matching for Graphs
• 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

Describes a project that uses

Uses Software

• vg
• HISAT

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)