 Main
Hardness of Approximation of (Multi)LCS over Small Alphabet
Abstract
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 MultiLCS problem) is NPcomplete. Jiang and Li [SICOMP'95] showed that if MaxClique is hard to approximate within a factor of $s$ then MultiLCS is also hard to approximate within a factor of $\Theta(s)$. By the NPhardness of the problem of approximating MaxClique by Zuckerman [ToC'07], for any constant $\delta>0$, the length of a LCS of arbitrary number of input sequences of length $n$ each, cannot be approximated within an $n^{1\delta}$factor in polynomial time unless {\tt{P}}$=${\NP}. However, the reduction of Jiang and Li assumes the alphabet size to be $\Omega(n)$. So far no hardness result is known for the problem of approximating MultiLCS over sublinear sized alphabet. On the other hand, it is easy to get $1/\Sigma$factor approximation for strings of alphabet $\Sigma$. In this paper, we make a significant progress towards proving hardness of approximation over small alphabet by showing a polynomialtime reduction from the wellstudied \emph{densest $k$subgraph} problem with {\em perfect completeness} to approximating MultiLCS 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 polynomialtime algorithm can give an $n^{o(1)}$factor approximation of MultiLCS over an alphabet of size $n^{o(1)}$, unless the Exponential Time Hypothesis is false.
Many UCauthored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.
Main Content
Enter the password to open this PDF file:













