论文标题
（多）LC在小字母上的近似硬度
Hardness of Approximation of (Multi-)LCS over Small Alphabet
论文作者
论文摘要
找到最长常见子序列（LCS）的问题是计算机科学中的基本问题之一，该问题在计算生物学，文本处理，信息检索，数据压缩等领域中找到了应用。众所周知，（决策版本）的问题是找到一个任意数量的输入序列的LCS长度（我们指的是多级lc-lcs问题）。 Jiang和Li [Sicomp'95]表明，如果难以在$ s $的一倍之内进行Max-Clique，那么多LCS也很难在$θ（s）$的一倍之内近似。通过Zuckerman [TOC'07]近似最大值的问题的NP硬度，对于任何常数$δ> 0 $，除非在$ n^{1-δ} $ fivers polynomial time y yount of polynomial time y nimal n^$ n of ty polynomial fivers lc} $ n $ n $ n $的任意数量输入序列的长度均无法近似但是，江和李的减少假定字母大小为$ω（n）$。到目前为止，尚无硬度结果因在亚线性大小的字母上近似多LC的问题而闻名。另一方面，对于字母$σ$的字符串而言，可以轻松获得$ 1/|σ| $ -Factor近似。 在本文中，我们通过显示{\ em Perfectentys}的多项式\ emph {emph {emph $ k $ -subgraph}问题，通过{\ em perfect perfectity}的问题来证明多项式时间的缩减，以证明在小字母上的近似硬度的硬度取得重大进展。结果，从最致密的$ k $ -subgraph问题的已知硬度（例如[manurangsi，stoc'17]）中，我们知道，没有多项式时间算法可以给出$ n^{ - o（1）} $ - ; nife y lapphabet yive y liffers y limsity $ n^^$ n^of n^^$ n^^o（1）} $（1）} $（1）。
The problem of finding longest common subsequence (LCS) is one of the fundamental problems in computer science, which finds application in fields such as computational biology, text processing, information retrieval, data compression etc. It is well known that (decision version of) the problem of finding the length of a LCS of an arbitrary number of input sequences (which we refer to as Multi-LCS problem) is NP-complete. Jiang and Li [SICOMP'95] showed that if Max-Clique is hard to approximate within a factor of $s$ then Multi-LCS is also hard to approximate within a factor of $Θ(s)$. By the NP-hardness of the problem of approximating Max-Clique by Zuckerman [ToC'07], for any constant $δ>0$, the length of a LCS of arbitrary number of input sequences of length $n$ each, cannot be approximated within an $n^{1-δ}$-factor in polynomial time unless {\tt{P}}$=${\NP}. However, the reduction of Jiang and Li assumes the alphabet size to be $Ω(n)$. So far no hardness result is known for the problem of approximating Multi-LCS over sub-linear sized alphabet. On the other hand, it is easy to get $1/|Σ|$-factor approximation for strings of alphabet $Σ$. In this paper, we make a significant progress towards proving hardness of approximation over small alphabet by showing a polynomial-time reduction from the well-studied \emph{densest $k$-subgraph} problem with {\em perfect completeness} to approximating Multi-LCS over alphabet of size $poly(n/k)$. As a consequence, from the known hardness result of densest $k$-subgraph problem (e.g. [Manurangsi, STOC'17]) we get that no polynomial-time algorithm can give an $n^{-o(1)}$-factor approximation of Multi-LCS over an alphabet of size $n^{o(1)}$, unless the Exponential Time Hypothesis is false.
