标题： 最短公共超串变种的近似难度 显示英文标题

标题： Approximation hardness of Shortest Common Superstring variants

摘要： 最短公共超串（SCS）问题因其与计算基因组学中的从头组装问题的联系而被广泛研究。 基本问题属于APX-难，但该问题的几个推广形式也已被研究。 特别是，以前的结果包括带有负字符串的SCS（SCSN）属于Log-APX（尽管没有已知的难解性结果），而带有通配符的SCS（SCSW）是Poly-APX-难的。 在这里，我们证明了两个新的难解性结果：（1）通过从最小集合覆盖问题约化，证明SCSN是Log-APX-难的（因此是Log-APX-完全的），（2）带有负字符串和通配符的SCS（SCSNW）通过从最小一的3SAT问题约化，证明是NPOPB-难的。 显示英文摘要

摘要： The shortest common superstring (SCS) problem has been studied at great length because of its connections to the de novo assembly problem in computational genomics. The base problem is APX-complete, but several generalizations of the problem have also been studied. In particular, previous results include that SCS with Negative strings (SCSN) is in Log-APX (though there is no known hardness result) and SCS with Wildcards (SCSW) is Poly-APX-hard. Here, we prove two new hardness results: (1) SCSN is Log-APX-hard (and therefore Log-APX-complete) by a reduction from Minimum Set Cover and (2) SCS with Negative strings and Wildcards (SCSNW) is NPOPB-hard by a reduction from Minimum Ones 3SAT.