How to prove Shortest Common Superstring is NP-Hard

Question

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.

Answer 1

To show that a problem $X$ is NP-hard, it does not help to reduce $X$ to a known NP-hard problem, since you can also reduce very easy problems to NP-hard problems (for example the trivial problem that is true for all inputs can be reduced to any nontrivial problem in constant time). NP-hardness of $X$ says that all problems in NP can be reduced to $X$, not that $X$ can be reduced to anything.

The easiest way to show that $X$ is NP-hard is to find a different NP-hard problem, then reduce it to $X$. But be careful, some NP-hard problems may be harder than $X$! So your best bet is to pick an NP-complete problem and try to reduce it to $X$, since that's guaranteed to be possible and will complete the proof.

In fact, since the shortest common superstring problem is itself in NP, you actually have no choice but to choose an NP-complete problem to reduce to it, since you can't reduce any harder problems to it.

In this list of NP-complete problems I'm sure a few good candidates will catch your eye. If not, then 3-SAT is always a good default option.