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?
Fixed-parameter tractability of SCS: finding the missing proof(s)
reference request;parameterized complexity