The problem of computing the longest common subsequence of two sequences ( LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS : the Repetition-Bounded Longest Common Subsequence problem ( RBLCS ), the Multiset-Restricted Common Subsequence problem ( MRCS ), the Two-Side-Filled Longest Common Subsequence problem ( 2FLCS ), and the One-Side-Filled Longest Common Subsequence problem ( 1FLCS ). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O ( 1 . 4422 5 n ) -time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and p o l y ( n ) . Here, we first establish that each of MRCS , 1FLCS , and 2FLCS is polynomially equivalent to RBLCS . Then, we design a refined DP-based algorithm for RBLCS that runs in O ( 1 . 4142 2 n ) time, which implies that MRCS , 1FLCS , and 2FLCS can also be solved in O ( 1 . 4142 2 n ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS .

In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the Repetition-Bounded Longest Common Subsequence problem (or RBLCS , for short): Let an alphabet S be a finite set of symbols and an occurrence constraint C o c c be a function C o c c : S → N , assigning an upper bound on the number of occurrences of each symbol in S . Given two sequences X and Y over the alphabet S and an occurrence constraint C o c c , the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s ∈ S appears at most C o c c ( s ) times in the obtained subsequence. The special case where C o c c ( s ) = 1 for every symbol s ∈ S is known as the Repetition-Free Longest Common Subsequence problem ( RFLCS ) and has been studied previously; e.g., in [1] , Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS . However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that | X | ≤ | Y | and | X | = n . In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O ( 1.44225 n ) . Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O ( 1.44225 n ) for any occurrence constraint C o c c , and even less in certain special cases. In particular, for RFLCS , our DP-based algorithm runs in O ( 1.41422 n ) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.