2013/09/02 by Aurélie Lagoutte, Lagoutte, Aurélie, Sébastien Tavenas +1
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1309.0422
openalex publication_date 2013/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Shortest Common Supersequence problem (SCS for short) consists in finding a shortest common supersequence of a finite set of words on a fixed alphabet Sigma. It is well-known that its decision version denoted [SR8] in [Garey and Johnson] is NP-complete. Many variants have been studied in the literature. In this paper we settle the complexity of two such variants of SCS where inputs do not contain identical consecutive letters. We prove that those variants denoted φSCS and MSCS both have a decision version which remains NP-complete when |Σ| is at least 3. Note that it was known for MSCS when |Σ| is at least 4 [Fleisher and Woeginger] and we discuss how [Darte] states a similar result for |Σ| at least 3.