3
$\begingroup$

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.

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$ Jul 13, 2015 at 7:21
  • 2
    $\begingroup$ In the reduction by Blin et al., all of the strings have the same number of 0's and 1's. $\endgroup$
    – JWM
    Jul 13, 2015 at 10:39
-3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ please provide some links to support these claims $\endgroup$
    – user36160
    Jan 9, 2016 at 7:46
  • $\begingroup$ 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. $\endgroup$ Jun 25, 2019 at 20:53
  • 1
    $\begingroup$ 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. $\endgroup$ May 20, 2022 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.