# Is longest common subsequence with bounded occurrences NP-complete?

The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are constants?

I asked this question on cs.stackexchange and was told, "The problem probably remains NP-complete." However, I was unsuccessful in showing a reduction from the original LCS problem.

• Of course I guess $n$ and $m$ are "constants" in the sense that these values are the same for all input strings, not that they are fixed to be constants in the problem setting. (Otherwise of course the problem is no longer NP-complete given that the maximal length of the resulting longest common subsequence would also be bounded by a constant.)
– a3nm
Commented May 14 at 18:08

## 2 Answers

This paper by Blin et al. (Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths, CPM'12) provides a reduction from independent set to LCS where the Hamming weights of all strings are the same (it is $n-1$ where $n$ is the number of vertices in the independent set instance). Thus, the problem remains NP-complete under this assumption.

• Thanks for the answer. In this case the Hamming Weight (no. of 1's) are fixed to a constant M in each string. Assuming, both the number of 1's and 0's are fixed (i.e. the string sizes are same along with the Hamming Weight) does the LCS problem reduce to P ? Commented Jul 13, 2015 at 7:21
• In the reduction by Blin et al., all of the strings have the same number of 0's and 1's.
– JWM
Commented Jul 13, 2015 at 10:39

I believe the problem was shown to be NP-Hard, as opposed to NP-Complete. I am not personally familiar with any proof of reducibility of SAT to LCS. Such a proof is required for a problem to be regarded as NP-Complete. NP-Complete essentially means that a given problem is at least as hard as SAT. The reduction of a problem to SAT in P-time and P-space merely shows the problem is itself no harder the SAT. The LCS problem has a P-time and P-space solution as an answer set problem.

• please provide some links to support these claims
– user36160
Commented Jan 9, 2016 at 7:46
• To the 4 down voters: How dare you! This answer is excellent. User36160 says (very original name btw) "[got links]?" - use Google is my reply. Commented Jun 25, 2019 at 20:53
• It’s important to note that the LCSq between 2 strings is NP-Hard, when comparing 3 strings the problem is NP-Complete according to Wikipedia’s list of NP-Complete problems. Commented May 20, 2022 at 13:27