1
$\begingroup$

After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting Problem, Satisfiability Problem or Traveling Salesman Problem. Now my problem is Shortest Common Superstring

  • Input: A finite set R = {r1, r2, ..., rm} of binary strings (sequences of 0 and 1); positive integer k.
  • Question: Is there a binary string w of length at most k such that every string in R is a substring of w, i.e. for each r in R, w can be decomposed as w = w0rw1 where w0, w1 are (possibly empty) binary strings?

In this link it states that the problem is NP-Hard(https://www.geeksforgeeks.org/shortest-superstring-problem/), besides I am using the greedy algorithm stated there to solve the problem.

So I need help with choosing which NP-Hard Algorithm to reduce to and a way to reduce it. I do not expect a full solution(even though it would be welcome), just guidance would be enough. I honestly do not have much clue on how to go about it.

$\endgroup$
  • $\begingroup$ The reduction actually goes in the other direction: You pick a problem that you already know to be NP-hard, and reduce it to the problem you want to prove NP-hard. This is a common mistake. $\endgroup$ – j_random_hacker Dec 15 '19 at 2:31
  • 1
    $\begingroup$ (This is a common mistake - getting the reduction direction wrong, that is.) $\endgroup$ – greybeard Dec 15 '19 at 3:39
1
$\begingroup$

This article may help you.

Theorem 1 states that Hamilton path problem can be reduced to SCS even if all strings have fixed length $H \ge 3$.

For your case with strings of any length but fixed alphabet, this is also true, but the proof is more technical.

$\endgroup$

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.