<blockquote>
<p>Does this remain true if <span class="math-container">$n$</span> is bounded?</p>
</blockquote>
<p>No.  When <span class="math-container">$n=O(1)$</span>, there is a constant-factor approximation algorithm.  See Lemma 1 below.</p>
<blockquote>
<p>Does this remain true if <span class="math-container">$n$</span> is sublinear in <span class="math-container">$|L|$</span>?</p>
</blockquote>
<p>Yes. For every constant <span class="math-container">$\epsilon&gt;0$</span>,
the problem remains just as hard to approximate
even when <span class="math-container">$n\le |L|^{\epsilon}$</span>.
See Lemma 2 below.</p>
<hr />
<p><strong>Lemma 1.</strong> <em>There is a constant-factor approximation algorithm for the case when <span class="math-container">$n=O(1)$</span>.</em></p>
<p><strong>Lemma 2.</strong> <em>For any <span class="math-container">$\epsilon&gt;0$</span>, there exists a <span class="math-container">$\delta&gt;0$</span>
such that, if the problem (restricted to <span class="math-container">$n\le |L|^{\epsilon}$</span>)
has a polynomial-time approximation algorithm with performance ratio <span class="math-container">$n^\delta$</span>, then P=NP.</em></p>
<p><em>Proof of Lemma 1.</em> Just return the sequence <span class="math-container">$$(1, 2, \ldots, n+1)^\ell$$</span> where <span class="math-container">$\ell=\max\{|\sigma| : \sigma \in L\}$</span>.
This sequence has length <span class="math-container">$(n+1)\ell$</span>,
while <span class="math-container">$\ell$</span> is a lower bound on the optimum,
so this is an <span class="math-container">$(n+1)$</span>-approximation algorithm.
<span class="math-container">$~~\Box$</span></p>
<p><em>Proof of Lemma 2.</em>
Fix any <span class="math-container">$\epsilon&gt;0$</span>.
We point out that the general problem reduces
in polynomial time, preserving approximate solutions,
to the restricted problem (requiring <span class="math-container">$n \le |L|^\epsilon$</span>).</p>
<p>Given an instance <span class="math-container">$(L, n)$</span> of the general problem,
the reduction produces the instance <span class="math-container">$(L_\epsilon, n)$</span>
where <span class="math-container">$L_\epsilon$</span> is obtained from <span class="math-container">$L$</span>
by adding <span class="math-container">$n^{1/\epsilon}$</span> empty sequences, so that
<span class="math-container">$$|L_\epsilon| \ge n^{1/\epsilon}, \text{ that is } n\le |L_\epsilon|^\epsilon,$$</span>
so that <span class="math-container">$(L_\epsilon, n)$</span> is indeed an instance of the restricted problem.</p>
<p>We assume WLOG here that every symbol in <span class="math-container">$[n+1]$</span> occurs in some string in <span class="math-container">$L$</span>, so <span class="math-container">$n$</span> is at most the input size <span class="math-container">$\sum_{\sigma\in L} |\sigma|$</span>, so the reduction takes polynomial time.</p>
<p>By the result cited by OP,
there is a <span class="math-container">$\delta&gt;0$</span>
such that there is no poly-time <span class="math-container">$n^{\delta}$</span>-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.
<span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2024-03-25T20:55:47.047Z
I meant a constant independent of n.
Hao S
CC BY-SA 4.0
2024-03-25T21:04:18.833Z
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)$?
Neal Young
CC BY-SA 4.0
2024-03-25T21:32:32.903Z
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.
Hao S
CC BY-SA 4.0
2024-03-25T22:11:28.593Z
I don't see how $n$ is "fixed" as you describe it.  Could you make all the quantifiers you have in mind explicit?
Neal Young
CC BY-SA 4.0
2024-03-25T23:27:28.480Z
Do you understand the statement before "in other words"
Hao S
CC BY-SA 4.0
2024-03-26T00:01:39.453Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/152242/discussion-between-neal-young-and-hao-s).
Neal Young
CC BY-SA 4.0
2024-03-25T20:33:58.410Z
2024-03-25T23:59:02.663Z
2024-03-25T23:59:02.663Z
Neal Young
<p>Given a list <span class="math-container">$L$</span> of sequences of the first <span class="math-container">$n+1$</span> natural numbers, how well can we approximate the shortest common supersequence of all sequences in <span class="math-container">$L$</span>?  The paper here shows that if <span class="math-container">$n$</span> is not restricted there is no constant factor polynomial time approximation.
<a href="https://epubs.siam.org/doi/abs/10.1137/S009753979223842X?journalCode=smjcat" rel="nofollow noreferrer">On the Approximation of Shortest Common Supersequences and Longest Common Subsequences</a></p>
<p>Does this remain true if <span class="math-container">$n$</span> is bounded or small say sublinear in <span class="math-container">$L$</span>?</p>

CC BY-SA 4.0
2024-03-22T00:38:57.853Z
Related: https://cstheory.stackexchange.com/q/54062/8237
Neal Young
CC BY-SA 4.0
2024-03-22T01:24:22.123Z
@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
Hao S
CC BY-SA 4.0
2024-03-28T19:57:16.623Z
@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?
Hao S
CC BY-SA 4.0
2024-03-28T23:13:45.230Z
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?
Hao S
CC BY-SA 4.0
2024-03-29T00:47:44.817Z
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?"
Neal Young
CC BY-SA 4.0
2024-03-29T06:14:32.160Z
@NealYoung  Yes that's what I mean.
Hao S
CC BY-SA 4.0
2024-03-29T12:25:07.187Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/152322/discussion-between-neal-young-and-hao-s).
Neal Young
<ds.algorithms><co.combinatorics><approximation-algorithms><permutations><string-matching>
How well can shortest common supersequence over small alphabet size be approximated?
Hao S
# How well can shortest common supersequence over small alphabet size be approximated?

(Asked by: username_0 on 2024-03-20)

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](https://epubs.siam.org/doi/abs/10.1137/S009753979223842X?journalCode=smjcat)

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

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms, permutations, string-matching
> **Comments:**
> **username_1**: Related: https://cstheory.stackexchange.com/q/54062/8237  
> **username_0**: @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  
> **username_0**: @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?  
> **username_0**: 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?  
> **username_1**: 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?"  
> **username_0**: @NealYoung  Yes that's what I mean.  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/152322/discussion-between-neal-young-and-hao-s).  

---

## 1 answers

### Answer by username_1 on 2024-03-25. Score: 1

> 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$

> **Comments:**
> **username_0**: I meant a constant independent of n.  
> **username_1**: 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)$?  
> **username_0**: 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.  
> **username_1**: I don't see how $n$ is "fixed" as you describe it.  Could you make all the quantifiers you have in mind explicit?  
> **username_0**: Do you understand the statement before "in other words"  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/152242/discussion-between-neal-young-and-hao-s).  

---

