In the Shortest Common Superstring (SCS) problem, a finite set of strings is given and the task is to find the shortest string that contains every input string as a substring. The problem is NP‑hard and many approximation algorithms have been proposed. The best known approximation ratio so far is $2.466$ (Englert, Matsakis & Vesel\'y), and OpenAI has recently announced a ratio of $2$. In 1988 Tarhio and Ukkonen introduced a simple greedy algorithm that repeatedly merges the two strings with the longest overlap. They showed that the greedy solution can be about twice as long as optimal and conjectured that this bound is tight, a statement that has been known as the Greedy Superstring Conjecture for almost four decades. The best known upper bound on the greedy ratio is $3.396$ (same authors). This paper presents three main contributions:
- By constructing a family of instances, we show that the greedy algorithm’s approximation ratio can approach $2.4$, thereby refuting the conjecture.
- We prove that the greedy algorithm is a $3$‑approximation.
- For inputs where each string has fixed length $k$, we prove the guarantee is exactly $9/5$ for $k=3$ and at least $2$ for all $k \ge 6$.
These results tighten both lower and upper bounds for the greedy approach and give a clearer theoretical benchmark for designing practical SCS algorithms.\n\nReview: The work disproves a long‑standing conjecture and provides sharper bounds, offering valuable guidance for future approximation strategies.