1
$\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$
7
$\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$
  • $\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$ – TheoryQuest1 Jul 13 '15 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 '15 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$
  • $\begingroup$ please provide some links to support these claims $\endgroup$ – user36160 Jan 9 '16 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$ – Alan Burstein Jun 25 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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