Tight conditional lower bounds for longest common increasing subsequence

DOI10.1007/s00453-018-0485-7zbMath1430.68116arXiv1709.10075OpenAlexW2910214492MaRDI QIDQ2272597

Yanyan Li

Publication date: 10 September 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitycombinatorial pattern matchingsequence alignmentsSETHfine-grained complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance, A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

Cites Work

• Unnamed Item
• Unnamed Item
• LCS\(k\): a refined similarity measure
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• On the generalized constrained longest common subsequence problems
• Faster algorithms for computing longest common increasing subsequences
• A fast algorithm for computing a longest common increasing subsequence
• The longest common subsequence problem for arc-annotated sequences
• Efficient algorithms for finding a longest common increasing subsequence
• The constrained longest common subsequence problem
• The longest common subsequence problem revisited
• An \(O(ND)\) difference algorithm and its variations
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• A faster algorithm computing string edit distances
• On computing the length of longest increasing subsequences
• Which problems have strongly exponential complexity?
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• A linear algorithm for 3-letter longest common weakly increasing subsequence
• Fast computation of a longest increasing subsequence and application
• A simple algorithm for the constrained sequence problems
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• On Problems Equivalent to (min,+)-Convolution
• Consequences of Faster Alignment of Sequences
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Spelling correction in systems programs
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• On the complexity of \(k\)-SAT