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 Θ(s). By the NPhardness of the problem of approximating MaxClique 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 {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 MultiLCS over sublinear 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 polynomialtime reduction from the wellstudied densest ksubgraph problem with perfect completeness to approximating MultiLCS over alphabet of size poly(n/k). As a consequence, from the known hardness result of densest ksubgraph 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.
BibTeX  Entry
@InProceedings{bhangale_et_al:LIPIcs:2020:12641,
author = {Amey Bhangale and Diptarka Chakraborty and Rajendra Kumar},
title = {{Hardness of Approximation of (Multi)LCS over Small Alphabet}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {38:138:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12641},
URN = {urn:nbn:de:0030drops126418},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.38},
annote = {Keywords: Longest common subsequence, Hardness of approximation, ETHhardness, Densest ksubgraph problem}
}
Keywords: 

Longest common subsequence, Hardness of approximation, ETHhardness, Densest ksubgraph problem 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) 
Issue Date: 

2020 
Date of publication: 

11.08.2020 