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

DOI10.1007/978-3-030-67731-2_44zbMath1490.68151arXiv2002.00629OpenAlexW3126170517MaRDI QIDQ831852

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

Publication date: 24 March 2022

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

zbMATH Keywords

lower boundsreductionsindexingorthogonal vectorscomplexity theoryedit distancegraph queryexact pattern matching

Mathematics Subject Classification ID

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

Related Items (8)

Linear time construction of indexable elastic founder graphs ⋮ On the Complexity of String Matching for Graphs ⋮ Algorithms and complexity on indexing founder graphs ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Elastic founder graphs improved and enhanced ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Wheeler languages ⋮ Solving string problems on graphs using the labeled direct product

Uses Software

• HISAT
• vg

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster algorithm computing string edit distances
• Wheeler graphs: a framework for BWT-based data structures
• Efficient pattern matching in elastic-degenerate strings
• On the complexity of recognizing Wheeler graphs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Jewels of Stringology
• Pattern matching in hypertext
• On-line pattern matching on similar texts
• 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
• Distance Oracles beyond the Thorup--Zwick Bound
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• On the complexity of \(k\)-SAT

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