2
$\begingroup$

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), 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?

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Yixin Cao Apr 14 '14 at 16:08
  • $\begingroup$ 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. $\endgroup$ – NisaiVloot Apr 14 '14 at 17:27
  • $\begingroup$ 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. $\endgroup$ – NisaiVloot Apr 14 '14 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.