<p>I am interested in two "super-objects" problems from computational biology.</p>

<p>The first problem, dubbed <em>Shortest Common Supersequence</em> ($SCSy$), takes a family of sequences $s_1,\ldots,s_k$, and seeks a common supersequence of minimum length.
The second problem, dubbed <em>Shortest Common Supertree</em> ($SCSx$, introduced <a href="http://www.mrfellows.net/papers/C36.pdf" rel="nofollow">here</a>), takes a family of p-trees $t_1,\ldots,t_k$, and seeks a common supertree of minimum length.</p>

<p>I have some issues ascertaining the fixed-parameter tractability or $\mathsf{W[1]}$-hardness of the following parameterizations:</p>

<p>(i) $SCSy$ parameterized by the number of sequences $k$: the problem is claimed to be $\mathsf{W[1]}$-hard in M. Hallett's thesis without proof;</p>

<p>(ii) $SCSx$ and $SCSy$ parameterized by the number of duplications of the super-object: in the above mentioned paper, the first problem is claimed to be FPT and the second is claimed to be $\mathsf{W[1]}$-hard, but I couldn't convince myself whether this is correct.</p>

<p>Any people from the FPT scene willing to help?</p>

CC BY-SA 3.0
2014-04-14T16:08:55.107Z
A general comment on your question (not a particular answer). Most people in this community are busy, and those who can answer your questions might be busier than average. So it helps a lot (for both the community and yourself) if you would clearly state what methods you've tried. I believe this is important to attract people to spend time on your problem.
Yixin Cao
CC BY-SA 3.0
2014-04-14T17:27:52.060Z
Here is a quick answer regarding point (ii). I understand that the FPT algorihtm works as follows for a set of sequences $\nabla = \{s_1,\ldots,s_k\}$. We scan the sequences left to right, maintaining a 'cursor' in each $s_i$. At a given step, if there is a letter that is ahead of all the others, we move the corresponding cursors to the right. If there is no such letter, for each possible index $i$ we insert in the target sequence a duplication corresponding to the letter under cursor $i$, and we move this cursor to the right. This gives a $O(k^r)$ algorithm but I'm unsure of the correctness.
NisaiVloot
CC BY-SA 3.0
2014-04-14T17:39:31.843Z
Regarding the second problem, I was wrong: the paper actually claims an FPT algorithm for *complete binary* p-trees (Thm 10 in the paper) while it known to be NP-hard to find a *single-duplication* solution for incomplete binary p-trees (even for three-leaf trees). At this point I don't see a good reason for this complexity gap between sequences and trees, so I'm a bit skeptical about the previous algorithm. But I don't really have a strong point to make as the proofs seem (intentionally?) sloppy.
NisaiVloot
<reference-request><parameterized-complexity>
Fixed-parameter tractability of SCS: finding the missing proof(s)
NisaiVloot
# Fixed-parameter tractability of SCS: finding the missing proof(s)

(Asked by: username_0 on 2014-04-13)

I am interested in two "super-objects" problems from computational biology.

The first problem, dubbed *Shortest Common Supersequence* ($SCSy$), takes a family of sequences $s\_1,\ldots,s\_k$, and seeks a common supersequence of minimum length.
The second problem, dubbed *Shortest Common Supertree* ($SCSx$, introduced [here](http://www.mrfellows.net/papers/C36.pdf)), takes a family of p-trees $t\_1,\ldots,t\_k$, and seeks a common supertree of minimum length.

I have some issues ascertaining the fixed-parameter tractability or $\mathsf{W[1]}$-hardness of the following parameterizations:

(i) $SCSy$ parameterized by the number of sequences $k$: the problem is claimed to be $\mathsf{W[1]}$-hard in M. Hallett's thesis without proof;

(ii) $SCSx$ and $SCSy$ parameterized by the number of duplications of the super-object: in the above mentioned paper, the first problem is claimed to be FPT and the second is claimed to be $\mathsf{W[1]}$-hard, but I couldn't convince myself whether this is correct.

Any people from the FPT scene willing to help?

**Tags:** reference-request, parameterized-complexity

> **Comments:**
> **username_1**: A general comment on your question (not a particular answer). Most people in this community are busy, and those who can answer your questions might be busier than average. So it helps a lot (for both the community and yourself) if you would clearly state what methods you've tried. I believe this is important to attract people to spend time on your problem.  
> **username_0**: Here is a quick answer regarding point (ii). I understand that the FPT algorihtm works as follows for a set of sequences $\nabla = \{s_1,\ldots,s_k\}$. We scan the sequences left to right, maintaining a 'cursor' in each $s_i$. At a given step, if there is a letter that is ahead of all the others, we move the corresponding cursors to the right. If there is no such letter, for each possible index $i$ we insert in the target sequence a duplication corresponding to the letter under cursor $i$, and we move this cursor to the right. This gives a $O(k^r)$ algorithm but I'm unsure of the correctness.  
> **username_0**: Regarding the second problem, I was wrong: the paper actually claims an FPT algorithm for *complete binary* p-trees (Thm 10 in the paper) while it known to be NP-hard to find a *single-duplication* solution for incomplete binary p-trees (even for three-leaf trees). At this point I don't see a good reason for this complexity gap between sequences and trees, so I'm a bit skeptical about the previous algorithm. But I don't really have a strong point to make as the proofs seem (intentionally?) sloppy.  

---

## 0 answers

