How to prove Shortest Common Superstring is NP-Hard 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.
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.