The Greedy Superstring Conjecture Is False

summary

The gist

The shortest common superstring problem is to find the shortest string that contains every input string as a substring…

In short

The paper disproves the greedy superstring conjecture by showing that its approximation ratio is at least 9/4 for general instances. It constructs a specific counterexample, $S_{k,t}$, where all input strings have length $k$. By comparing the greedy algorithm's output length to the optimal solution length for this instance and taking a limit, it proves the greedy approach is not always optimal.

Key concepts

Greedy Superstring Conjecture
This conjecture suggests that a simple, local decision-making strategy—always merging the two strings with the maximum overlap at each step—will always yield a shortest possible superstring. The paper aims to show this assumption is false by providing a counterexample where this greedy choice leads to a significantly longer final string than necessary.
Approximation Ratio ($ ho_k$)
This measures how much worse the result from the greedy algorithm is compared to the true shortest possible superstring length. The paper proves that for instances of strings of length $k$, this ratio is at least 9/4, meaning the greedy algorithm can produce a string at least 2.25 times longer than the optimal solution in certain cases.
Counterexample ($S_{k,t}$)
The authors create a specific set of input strings designed to defeat the greedy algorithm. These strings are constructed based on recursive definitions and circular substrings of length $k$. This instance is used to demonstrate that no matter how the greedy algorithm proceeds, it cannot achieve the optimal length for this particular set of inputs.
Optimal Value (OPT)
This represents the absolute shortest possible string that contains every input string as a substring. The paper establishes an exact formula for this value, $t(4s + 2) + k - 1$, by using both a lower bound derived from counting distinct strings and an upper bound derived from graph theory (Eulerian circuits). This provides the benchmark against which the greedy algorithm's performance is measured.

Terminology used across episodes

This episode discusses

The paper

The Greedy Superstring Conjecture Is False · Read on arXiv

Hiroki Shibata

Joint Graduate School of Mathematics for Innovation, Kyushu University

In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Since the problem is NP-hard, various approximation algorithms have been proposed for it. The currently best known approximation ratio is 2.466 due to Englert, Matsakis, and Veselý; a better approximation ratio 2 has been announced by OpenAI just recently. In 1988, Tarhio and Ukkonen introduced a simple greedy algorithm that iteratively takes two strings with the longest overlap and merges them together. They showed that the greedy algorithm may produce a superstring that is about two times longer than the optimal one and conjectured that this bound is tight. This has become known as the Greedy Superstring Conjecture and has remained open for almost four decades. The best known upper bound on the approximation ratio of the greedy algorithm is 3.396 due to Englert, Matsakis, and Veselý. In this paper, we present a series of results tightening the bounds of the greedy algorithm, with the main contributions being as follows: 1. We refute the Greedy Conjecture by constructing a family of instances for which a lower bound on the approximation ratio tends to 2.4. 2. We prove that the greedy algorithm is 3-approximate. 3. For input strings of fixed length k, we prove that the approximation guarantee is exactly 9/5 for k=3 and at least 2 for all k at least 6.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "The Greedy Superstring Conjecture Is False".

Jane: Here's the gist of the paper. The shortest common superstring problem is to find the shortest string that contains every input string as a substring, and this paper disproves the greedy superstring conjecture by showing that its approximation ratio is at least 9/4.

Tom: Disproving the Greedy Conjecture The paper demonstrates that for every even integer k ≥ 10, the approximation ratio ρk of the greedy algorithm for SCS instances in which all input strings have length k satisfies ρk ≥ 9k + 2 / 4k + 4.

Jane: This failure is shown by constructing an instance Sk,t where all input strings have length k and showing that the greedy algorithm produces a string of length t(9s + 1) + 1, while the optimal solution OPT(Sk,t) is t(4s + 2) + k − 1.

Tom: By taking the limit as k → ∞, this yields a lower bound of at least 9/4 for unrestricted SCS instances.

Paper summary: Tom: To recap what we just heard, this paper, "The Greedy Superstring Conjecture Is False", is showing that the greedy algorithm for finding the shortest string containing all input strings as substrings isn't a two-approximation algorithm. It lays out a construction called Sk t where all input strings have the same even length k greater than ten. <ref:2609.01365#pg2>

Jane: That specific construction, Sk t, is what lets them prove that for this setup, the greedy approximation ratio rho k is at least nine times k plus two over four times k plus four. <ref:2609.01365#pg2>

Lu: They show that this lower bound holds even for very large input string lengths because they take the limit as k approaches infinity, which means the lower bound on the approximation ratio for unrestricted SCS instances becomes nine over four. <ref:2609.01365#pg2>

Meng: So basically, it’s not just a small error in a specific test case; it't a scaling problem that gets worse as you add more complexity to the input strings. <ref:2609.01365#pg2>

Tom: Right, and they also detail the instance Sk t over an alphabet Σ consisting of x, y, a, b one through t where every string in this set has length k. <ref:2609.01365#pg3>

Jane: That means they’re using a specific set of characters for their strings to build these instances before taking those circular substrings of length k. <ref:2609.01365#pg3>

Lalam: The core idea is that by defining strings Ui, Vi, and Wi based on the recursive definition of X n and then taking circular substrings of length k for these strings, they form the input set Sk t across t instances. <ref:2609.01365#pg3>

Tom: And they establish the optimal value OPT by matching a lower bound derived from the number of distinct input strings with an upper bound obtained via an Eulerian circuit in a de Bruijn graph. <ref:2609.01365#pg3>

Jane: That means they use two different mathematical tools to nail down the true minimum length, which is good for establishing that OPT of Sk t equals t times four times s plus two plus k minus one. <ref:2609.01365#pg3>

Lu: So they’re using both a lower bound approach and an upper bound approach to confirm their optimal value calculation is solid. <ref:2609.01365#pg3>

Meng: From a production standpoint, that double-checking of the optimal value is good because it means the result isn't just based on one side or the other of an inequality. <ref:2609.01365#pg3>

Tom: And they then show their greedy algorithm results in a string length of t times nine times s plus one plus one, which we already discussed is worse than the optimal value by that factor for this specific construction. <ref:2609.01365#pg2>

Jane: So when you put the two lengths side-by-side, the final approximation ratio comes out to be at least nine over four for every even k greater than ten. <ref:2609.01365#pg4>

Lalam: That means the greedy algorithm has a guaranteed performance floor of nine over four for this specific class of problems, and as we let k grow, that floor becomes nine over four for all general cases. <ref:2609.01365#pg2>

Conclusion: Tom: So to wrap up this paper "The Greedy Superstring Conjecture Is False", the main point is that the greedy approach isn't reliable because they proved it can be outperformed by a factor of nine over four in the general case. <ref:2609.01365#pg2>

Jane: It means we should stop assuming that repeated greedy merging is a good enough strategy for finding the shortest common superstring, especially when dealing with large sets of strings where they all share an even length greater than ten. <ref:2609.01365#pg1>

Lu: The authors didn't just prove it for one specific type of instance but showed the failure holds as long as k is even and greater than ten, which is a strong condition to meet. <ref:2609.01365#pg2>

Meng: From an engineering perspective, this means we need to look seriously at alternative approximation algorithms that can guarantee better performance bounds than nine over four for real-world deployment scenarios. <ref:2609.01365#pg2>

Tom: Exactly. So the paper ends with Corollary fifteen which states that the approximation ratio of the greedy algorithm for the general SCS problem is at least nine over four. <ref:2609.01365#pg4>

Jane: It’s a strong statement because it

More episodes

← Home