Bounding the Expected Length of Longest Common Subsequences and Forests

On the parameterized complexity of the f

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

✍ Krzysztof Pietrzak 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 205 KB

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W ½1-hard. Unless W ½1 ¼ FPT; this rules out the existence of algorithms with time complexity of Oð f ðkÞn a Þ for those pro