# How well can shortest common supersequence over small alphabet size be approximated?

Given a list $$L$$ of sequences of the first $$n+1$$ natural numbers, how well can we approximate the shortest common supersequence of all sequences in $$L$$? The paper here shows that if $$n$$ is not restricted there is no constant factor polynomial time approximation. On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

Does this remain true if $$n$$ is bounded or small say sublinear in $$L$$?

• Mar 22 at 0:38
• @NealYoung Mapping doesn't work because we're looking at subseqences not substrings. If we try to map the set of charactersonto $k$ ary strings then choosing a minimum set i(0),i(1),.., i(k) of the first n+1 natural numbers such that b_i(0),b_i(1),.., b_i(k) contains each of 0,1,2,..,k then (b_i(0) b_i(1) .., b_i(k) )^* contains a supersequence of any sequence Mar 22 at 1:24
• @NealYoung I'm not looking for a PTAS there are two "constants" in question the approximation ratio and the alphabet size. My question is there any $b \geq 0$ such that for any constant $c \geq 2$ the SCS problem on an alphabet of size c admits a $b$-approximation? Mar 28 at 19:57
• Actually it's "is there a constant b such that for ANY constant c≥2 , the c -supersequence problem is NP-hard to approximate within b? Mar 28 at 23:13
• Hao, and I assume by "for ANY constant c" you mean "for ALL constants c", not "for SOME constant c." So, you are asking "does there exist a constant b such that, for every fixed c, b-approximating the c-supersequence problem (with running time polynomial in the input size, but depending arbitrarily on c and b) is NP-hard?" Mar 29 at 0:47

## 1 Answer

Does this remain true if $$n$$ is bounded?

No. When $$n=O(1)$$, there is a constant-factor approximation algorithm. See Lemma 1 below.

Does this remain true if $$n$$ is sublinear in $$|L|$$?

Yes. For every constant $$\epsilon>0$$, the problem remains just as hard to approximate even when $$n\le |L|^{\epsilon}$$. See Lemma 2 below.

Lemma 1. There is a constant-factor approximation algorithm for the case when $$n=O(1)$$.

Lemma 2. For any $$\epsilon>0$$, there exists a $$\delta>0$$ such that, if the problem (restricted to $$n\le |L|^{\epsilon}$$) has a polynomial-time approximation algorithm with performance ratio $$n^\delta$$, then P=NP.

Proof of Lemma 1. Just return the sequence $$(1, 2, \ldots, n+1)^\ell$$ where $$\ell=\max\{|\sigma| : \sigma \in L\}$$. This sequence has length $$(n+1)\ell$$, while $$\ell$$ is a lower bound on the optimum, so this is an $$(n+1)$$-approximation algorithm. $$~~\Box$$

Proof of Lemma 2. Fix any $$\epsilon>0$$. We point out that the general problem reduces in polynomial time, preserving approximate solutions, to the restricted problem (requiring $$n \le |L|^\epsilon$$).

Given an instance $$(L, n)$$ of the general problem, the reduction produces the instance $$(L_\epsilon, n)$$ where $$L_\epsilon$$ is obtained from $$L$$ by adding $$n^{1/\epsilon}$$ empty sequences, so that $$|L_\epsilon| \ge n^{1/\epsilon}, \text{ that is } n\le |L_\epsilon|^\epsilon,$$ so that $$(L_\epsilon, n)$$ is indeed an instance of the restricted problem.

We assume WLOG here that every symbol in $$[n+1]$$ occurs in some string in $$L$$, so $$n$$ is at most the input size $$\sum_{\sigma\in L} |\sigma|$$, so the reduction takes polynomial time.

By the result cited by OP, there is a $$\delta>0$$ such that there is no poly-time $$n^{\delta}$$-approximation algorithm for the general problem unless P=NP. By the above reduction (which blows up the input size by at most a polynomial) the same is true for the restricted problem. $$~~~~\Box$$

• I meant a constant independent of n. Mar 25 at 20:55
• Which constant do you mean should be independent of $n$? And what does "independent of $n$" mean if we are restricting $n$ to be $O(1)$? Mar 25 at 21:04
• Is there a constant c such that for any n, given a list $L$ of sequences of the first $n+1$ natural numbers, we can approximate the shortest common supersequence of all sequences in $L$? within factor c in time polynomial in |L|? In other words first fix the the approximation ratio then fix n. Mar 25 at 21:32
• I don't see how $n$ is "fixed" as you describe it. Could you make all the quantifiers you have in mind explicit? Mar 25 at 22:11
• Do you understand the statement before "in other words" Mar 25 at 23:27