Longest common parameterized subsequences with fixed common substring

Abstract

In this paper we consider the problem of the longest common parameterized subsequence with fixed common substring (STR-IC-LCPS). in particular, we show that STR-IC-LCPS is NP-complete. We describe an approach to solve STR-IC-LCPS. This approach is based on an explicit reduction from the problem to the satisfiability problem.