The shortest common nonsubsequence problem is NP-complete

DOI10.1016/0304-3975(93)90200-DMaRDI QIDQ1208726zbMATH OpenOpenAlexFDO

Authors S. Singh, Manuel Middendorf

Publication date 16 May 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90200-d

zbMATH Keywords

combinatorial optimizationNP-completenessstrings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

The shortest common nonsubsequence (SCNS) problem is: Given a finite set \(L\) of strings over an alphabet \(\Sigma\) and an integer \(k\in\mathbb{N}\), is there a string of length \(\leq k\) over \(\Sigma\) that is not a subsequence of any string in \(L\)? The SNCS problem is shown to be NP-complete for strings over an alphabet of size \(\geq 2\).

Recommendations

• The constrained shortest common supersequence problem
• The STO problem is NP-complete
• Solving the shortest common supersequence problem.
• scientific article; zbMATH DE number 6161102
• scientific article; zbMATH DE number 827942
• The set closest common subsequence problem
• On the approximation of longest common nonsupersequences and shortest common nonsubsequences
• The longest common subsequence problem revisited
• The longest filled common subsequence problem

Cites work

• An algorithm for distinguishing efficiently bit-strings by their subsequences
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common supersequence problem over binary alphabet is NP- complete

Cited in

(6)

• On trace inclusion optimization problems
• Restricted common superstring and restricted common supersequence
• NP-completeness of special string editing problems
• Combined super-/substring and super-/subsequence problems
• Consistent subsequences and supersequences
• On the approximation of longest common nonsupersequences and shortest common nonsubsequences

This page was built for publication: The shortest common nonsubsequence problem is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208726)