On the Hardness and Inapproximability of Recognizing Wheeler Graphs

DOI10.4230/LIPIcs.ESA.2019.51OpenAlexW2977558816MaRDI QIDQ5075794

Daniel Gibney, Sharma V. Thankachan

Publication date: 11 May 2022

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

zbMATH Keywords

NP-completenessstring algorithmsBurrows-Wheeler transformsuffix trees

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (10)

The complexity of approximate pattern matching on de Bruijn graphs ⋮ On the Complexity of String Matching for Graphs ⋮ Algorithms and complexity on indexing founder graphs ⋮ Quantum time complexity and algorithms for pattern matching on labeled graphs ⋮ Ordering regular languages and automata: complexity ⋮ Unnamed Item ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Solving string problems on graphs using the labeled direct product ⋮ Space efficient merging of de Bruijn graphs and Wheeler graphs ⋮ On the complexity of recognizing Wheeler graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Graph isomorphism, general remarks
• Wheeler graphs: a framework for BWT-based data structures
• Superbubbles, ultrabubbles and cacti
• Faster compressed dictionary matching
• On the complexity of recognizing Wheeler graphs
• An extension of the Burrows-Wheeler transform
• The compressed permuterm index
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Succinct Dictionary Matching with No Slowdown
• Laying Out Graphs Using Queues
• Efficient string matching
• Total Ordering Problem
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• Stack and Queue Layouts of Directed Acyclic Graphs: Part II
• pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
• Succinct de Bruijn Graphs
• Regular Languages meet Prefix Sorting

This page was built for publication: On the Hardness and Inapproximability of Recognizing Wheeler Graphs