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 \varphi SCS and MSCS both have a decision version which remains NP-complete when |\Sigma| is at least 3. Note that it was known for MSCS when |\Sigma| is at least 4 [Fleisher and Woeginger] and we discuss how [Darte] states a similar result for |\Sigma| at least 3.
翻译：最短常见超级序列问题(简称SCS)在于找到固定字母Sigma上一套有限词的最短共同的超级序列。众所周知,其决定文本在[Garey和Johnson]中注明[SR8]为[SR8],是NP的完整。文献中已经研究了许多变式。在本文件中,我们解决了SCS两种变式的复杂性,其中投入不包含相同的连续字母。我们证明这些变式在注解的\varphi SCS和MSCS都有一个决定版本,当“Sigma ⁇ ”至少为3时,该变式仍然为NP-完成。请注意,当“Sigma ⁇ ”至少为4[Flesher和Woonginger]时,MSCS已知,我们讨论“Darte”如何对“Sigma”至少3表示类似的结果。
相关内容
微信扫码咨询专知VIP会员