The Complexity of Some Problems on Subsequences and Supersequences

1978/04/01 by David Maier · 622 citations
Computer Science · #Algorithms and Data Compression #Citation #Coding theory and cryptography #Computer science #World Wide Web #semigroups and automata theory

paper · pdf · doi:10.1145/322063.322075

published in Journal of the ACM 25(2), 322-336 (Association for Computing Machinery)

openalex publication_date 1978/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/06

Abstract

The complexity of finding the Longest Common Subsequence (LCS) and the Shortest Common Supersequence (SCS) of an arbRrary number of sequences IS considered We show that the yes/no version of the LCS problem is NP-complete for sequences over an alphabet of size 2, and that the yes/no SCS problem is NPcomplete for sequences over an alphabet of size 5 KEY WORDS AND PHRASES computational complexity, NP-completeness, longest common subsequence, shortest common supersequence CR CATEGORIES 5 23, 5 39

Citations

• The String-to-String Correction Problem
• The complexity of theorem-proving procedures
• A linear space algorithm for computing maximal common subsequences
• On the complexity of the Extended String-to-String Correction Problem
• On computing the length of longest increasing subsequences
• Reducibility among Combinatorial Problems
• Linear pattern matching algorithms

Cited by

• Cache-Oblivious Dynamic Programming for Bioinformatics
• The shortest common supersequence problem over binary alphabet is NP-complete
• On the complexity of approximating the independent set problem
• Linear Time Subsequence and Supersequence Regex Matching
• Preprint: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
• Longest common subsequence [wikipedia]
• Shortest common supersequence [wikipedia]