The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

DOI10.4230/LIPIcs.ESA.2020.61OpenAlexW3081524518MaRDI QIDQ5874533

Daniel Gibney, Gary Hoppenworth, Jason Bentley, Sharma V. Thankachan

Publication date: 7 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12927/pdf/LIPIcs-ESA-2020-61.pdf/

zbMATH Keywords

edit distanceSETHMedian stringcenter string

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (3)

Co-linear chaining with overlaps and gap costs ⋮ The complexity of approximate pattern matching on de Bruijn graphs ⋮ Matching patterns with variables under edit distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The consensus string problem for a metric is NP-complete
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distinguishing string selection problems.
• Hardness of RNA folding problem with four symbols
• Topology of strings: median string is NP-complete
• Tight conditional lower bounds for longest common increasing subsequence
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Clustered Integer 3SUM via Additive Combinatorics
• On the closest string and substring problems
• Upper and Lower Bounds for Dynamic Data Structures on Strings
• More Efficient Algorithms for Closest String and Substring Problems
• Minimal Mutation Trees of Sequences
• Improved Approximation Algorithms for Tree Alignment
• Subtree Isomorphism Revisited
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Higher Lower Bounds from the 3SUM Conjecture
• Conditional Lower Bounds for All-Pairs Max-Flow
• Consequences of Faster Alignment of Sequences
• An Equivalence Class for Orthogonal Vectors
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Listing Center Strings Under the Edit Distance Metric

This page was built for publication: The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance