3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Related: cstheory.stackexchange.com/q/54062/8237 $\endgroup$
    – Neal Young
    Mar 22 at 0:38
  • 1
    $\begingroup$ @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 $\endgroup$
    – Hao S
    Mar 22 at 1:24
  • $\begingroup$ @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? $\endgroup$
    – Hao S
    Mar 28 at 19:57
  • $\begingroup$ 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? $\endgroup$
    – Hao S
    Mar 28 at 23:13
  • 1
    $\begingroup$ 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?" $\endgroup$
    – Neal Young
    Mar 29 at 0:47

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
6
  • $\begingroup$ I meant a constant independent of n. $\endgroup$
    – Hao S
    Mar 25 at 20:55
  • $\begingroup$ 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)$? $\endgroup$
    – Neal Young
    Mar 25 at 21:04
  • $\begingroup$ 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. $\endgroup$
    – Hao S
    Mar 25 at 21:32
  • $\begingroup$ I don't see how $n$ is "fixed" as you describe it. Could you make all the quantifiers you have in mind explicit? $\endgroup$
    – Neal Young
    Mar 25 at 22:11
  • $\begingroup$ Do you understand the statement before "in other words" $\endgroup$
    – Hao S
    Mar 25 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.