The Greedy Superstring Conjecture Is False

arXiv:2609.01365 · cs.DS · Submitted 2026-09-01 · Read on arXiv

Listen

Radio episode about this paper

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

Hiroki Shibata

Joint Graduate School of Mathematics for Innovation, Kyushu University

cs.DS

Submitted: 2026-09-01

Updated: 2026-11-06

Comments: Preliminary versions of the results of this paper are contained in arXiv:2608.20018v2, arXiv:2609.27921v2, and arXiv:2609.01365v1

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

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

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

Summary

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. p. 0

Where the paper says it

In this paper, we disprove this conjecture and show that the approximation ratio of this algorithm is at least 9/4. 1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring.

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. 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. p. 4

Where the paper says it

We can construct an optimal solution to the SCS instance Sk,t using such an Eulerian circuit (Theorem 10). In the lower-bound construction, we first merge the length-k circular substrings generated from each Ui , Vi , and Wi and obtain 3t strings corresponding to Ui , Vi , and Wi (1 ≤ i ≤ t).

By taking the limit as k → ∞, this yields a lower bound of at least 9/4 for unrestricted SCS instances. p. 1
Where the paper says it

Thus, the conjecture fails even when all input strings have the same even length k ≥ 10. By taking the limit as k → ∞, the lower bound on the approximation ratio of the greedy algorithm for unrestricted SCS instances becomes 9/4.

Construction of the Counterexample

The authors construct an instance Sk,t over an alphabet Σ = Σ = x, y, a, b1,..., bt where every input string has length k. p. 0

Where the paper says it

In this paper, we disprove this conjecture and show that the approximation ratio of this algorithm is at least 9/4. 1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring.

The construction involves defining strings Ui, Vi and Wi based on the recursive definition of Xn and then taking circular substrings of length k for these strings. p. 4
Where the paper says it

We can construct an optimal solution to the SCS instance Sk,t using such an Eulerian circuit (Theorem 10). In the lower-bound construction, we first merge the length-k circular substrings generated from each Ui , Vi , and Wi and obtain 3t strings corresponding to Ui , Vi , and Wi (1 ≤ i ≤ t).

The input set Sk,t is formed by collecting all these circular substrings across t instances. p. 1
Where the paper says it

For a set of strings S, let maxov(S) = max{ov(X, Y ) | X, Y ∈ S, X ̸= Y }. The following two lemmas show basic properties of merging multiple strings and consecutive circular substrings.

Optimal Value Determination

The optimal value OPT(Sk,t) is determined 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. The lower bound is established by showing that OPT(Sk,t) ≥ t(4s + 2) + k − 1. p. 4

Where the paper says it

4 Optimal Value of the Instance In this section, we determine OPT(Sk,t) by proving matching lower and upper bounds. We first derive a lower bound from the number of distinct input strings.

The upper bound is shown to be OPT(Sk,t) ≤ t(4s + 2) + k − 1. p. 4
Where the paper says it

4 Optimal Value of the Instance In this section, we determine OPT(Sk,t) by proving matching lower and upper bounds. We first derive a lower bound from the number of distinct input strings.

This leads to the exact optimal value Theorem 10: OPT(Sk,t) = t(4s + 2) + k − 1. p. 7
Where the paper says it

By combining the lower and upper bounds in Lemma 6 and Lemma 9, we obtain the exact optimal value. Theorem 10.

Lower Bound Procedure

The lower bound is proven by providing a concrete procedure for selecting and merging strings when the initial input is Sk,t. This procedure involves defining specific merged strings Uˆi, Vˆi, and Wˆi using sequences of merges with overlap length k − 1. p. 7

Where the paper says it

Our procedure first obtains Uˆ i , Vˆ i , and Wˆ i for every 1 ≤ i ≤ t by merging the elements Ui,j , Vi,j , and Wi,j as specified by the equalities involving ⊙. The two strings merged at each step have an overlap of length k − 1, and we perform the merge operations from left to right.

The total length of the resulting string T′ is calculated by subtracting the sum of all merge overlaps from the total initial length kt(4s + 2). p. 4
Where the paper says it

Hence, |Sk,t| = t k + s + (s + 2) = t(4s + 2). Every string in Sk,t has length exactly k, so the total length of all strings in Sk,t is kt(4s + 2).

This calculation results in T′ = t(9s + 1) + 1.

Final Approximation Ratio

By combining the lower bound and upper bound for an arbitrary even k, the approximation ratio ρk is shown to be at least (t(9s + 1) + 1) / (t(4s + 2) + k − 1). Taking the limit as t → ∞ yields the final result Corollary 15: The approximation ratio of the greedy algorithm for the general SCS problem is at least 9/4. p. 1

Where the paper says it

Thus, the conjecture fails even when all input strings have the same even length k ≥ 10. By taking the limit as k → ∞, the lower bound on the approximation ratio of the greedy algorithm for unrestricted SCS instances becomes 9/4.

References

[1] Chris Armen and Clifford Stein. A 2 2/3 superstring approximation algorithm. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Discret. Appl. Math., 88(1-3):29–57, 1998

[2] Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications, Second Edition. Springer Monographs in Mathematics. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Springer, 2009

[3] Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear approximation of shortest superstrings. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

J. ACM, 41(4):630–647, 1994

[4] Bastien Cazaux and Eric Rivals. Relationship between superstring and compression measures: New insights on the greedy conjecture. p. 0

Where the paper says it

Also, several other works have studied various formulations and variants related to the greedy superstring conjecture [11, 19, 20]. Very recently, new progress has been made on both sides of the approximation-ratio gap.

Discret. Appl. Math., 245:59–64, 2018

[5] Nikolai Chukhin, Alexander Kulikov, Ivan Mihajlin, and Alexander Smal. A tight cycle-cover inequality for shortest common superstring. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Technical Report TR26-157, Electronic Colloquium on Computational Complexity (ECCC), 2026

[6] Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Alexander Smal. The greedy superstring algorithm achieves ratio 2 for strings of length 6 already, 2026

[7] N. G. de Bruijn. A combinatorial problem. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 49(7):758–764, 1946

[8] Matthias Englert, Nicolaos Matsakis, and Pavel Vesel´y. Approximation guarantees for shortest superstrings: Simpler and better. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation, ISAAC 2023, Kyoto, Japan, December 3-6, 2023

[9] John Gallant, David Maier, and James A. Storer. On finding minimal length superstrings. p. 0

Where the paper says it

In this paper, we disprove this conjecture and show that the approximation ratio of this algorithm is at least 9/4. 1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring.

J. Comput. Syst. Sci., 20(1):50–58, 1980

[10] John K. Gallant. String Compression Algorithms. p. 0

Where the paper says it

1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring. It arises in applications such as genome assembly [18, 21] and data compression [4, 9], and is also discussed in several textbooks [12, 27].

PhD thesis, Princeton University, 1982

[11] Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, and Maksim Nikolaev. Collapsing superstring conjecture. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

In Dimitris Achlioptas and L´aszl´o A. V´egh, editors, Approximation, Randomization, and Combinatorial Optimization. p. 0
Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Algorithms and Techniques, APPROX/RANDOM 2019

[12] Dan Gusfield. Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. p. 0

Where the paper says it

This problem is NP-hard [9] and APX-hard even over a binary alphabet [26]. Consequently, much of the research on SCS has focused on approximation algorithms and heuristics.

Cambridge University Press, 1997

[13] Haim Kaplan and Nira Shafrir. The greedy algorithm for shortest superstrings. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Inf. Process. Lett., 93(1):13–17, 2005

[14] Alexander S. Kulikov, Sergey Savinov, and Evgeniy Sluzhaev. Greedy conjecture for strings of length 4. p. 0

Where the paper says it

Since its formulation, the greedy superstring conjecture has been studied extensively [4, 5, 14, 19, 20]. In particular, the conjecture is known to hold when all input strings have length 4 [14].

In Ferdinando Cicalese, Ely Porat, and Ugo Vaccaro, editors, Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015

[15] Bin Ma. Why greed works for shortest common superstring problem. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Theor. Comput. Sci., 410(51):5374–5381, 2009

[16] Eduardo Moreno. De bruijn sequences and de bruijn graphs for a general language. p. 4

Where the paper says it

On the other hand, each string has some length-(k−1) circular substrings in common with the other strings (Lemma 7). Because of this structure, the de Bruijn graph [7, 16] of order k − 1 constructed from all length-k circular substrings has an Eulerian circuit (Lemma 8).

Inf. Process. Lett., 96(6):214–219, 2005

[17] Marcin Mucha. Lyndon words and short superstrings. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA

[18] Eugene W. Myers. A history of DNA sequence assembly. p. 0

Where the paper says it

1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring. It arises in applications such as genome assembly [18, 21] and data compression [4, 9], and is also discussed in several textbooks [12, 27].

it Inf. Technol., 58(3):126–132, 2016

[19] Maksim S. Nikolaev. All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

In Thierry Lecroq and H´el̀ene Touzet, editors, String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021

[20] Maksim S. Nikolaev. Greedy conjecture for the shortest common superstring problem and its strengthenings. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

In Zsuzsanna Lipt´ak, Edleno Silva de Moura, Karina Figueroa, and Ricardo Baeza-Yates, editors, String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024

[21] Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman. A new approach to fragment assembly in DNA sequencing. p. 0

Where the paper says it

1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring. It arises in applications such as genome assembly [18, 21] and data compression [4, 9], and is also discussed in several textbooks [12, 27].

In Thomas Lengauer, editor, Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001

[22] Heidi J. Romero, Carlos A. Brizuela, and Andrei Tchernykh. An experimental comparison of approximation algorithms for the shortest common superstring problem. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

In 5th Mexican International Conference on Computer Science (ENC 2004), 20-24 September 2004

[23] Z. Sweedyk. A 2½-approximation algorithm for shortest superstring. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

SIAM J. Comput., 29(3):954–986, 1999

[24] Jorma Tarhio and Esko Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

Theor. Comput. Sci., 57:131–145, 1988

[25] Esko Ukkonen. A linear-time algorithm for finding approximate shortest common superstrings. p. 0

Where the paper says it

In this paper, we disprove this conjecture and show that the approximation ratio of this algorithm is at least 9/4. 1 Introduction The shortest common superstring problem (SCS, or the shortest superstring problem) is the problem of finding a string of minimum length that contains every input string as a substring.

Algorithmica, 5(3):313–323, 1990

[26] Virginia Vassilevska. Explicit inapproximability bounds for the shortest superstring problem. p. 0

Where the paper says it

Disproving the Greedy Superstring Conjecture Hiroki Shibata∗1 1Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan September 2, 2026 Abstract The shortest common superstring problem is to find the shortest string that contains every string in a given set as a substring. It is conjectured that the greedy algorithm that repeatedly selects a pair of strings with maximum overlap and merges them is a 2-approximation algorithm, and this conjecture had remained open for nearly four decades.

In Joanna Jedrzejowicz and Andrzej Szepietowski, editors, Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005

[27] Vijay V. Vazirani. Approximation algorithms. p. 0

Where the paper says it

This problem is NP-hard [9] and APX-hard even over a binary alphabet [26]. Consequently, much of the research on SCS has focused on approximation algorithms and heuristics.

Springer, 2001

Corollary

The approximation ratio of the greedy algorithm for the general SCS problem is at least 9/4.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Disproving the greedy superstring conjecture allows AI systems to guarantee a lower bound on solution quality for shortest common superstring problems, specifically proving that the approximation ratio of this algorithm is at least 9/4. This provides a rigorous performance guarantee for heuristic-based SCS solvers.

  2. The construction of instances Sk,t enables the creation of complex test cases where every input string has length k, allowing researchers to rigorously evaluate greedy algorithms under specific constraints and determine their true worst-case performance bounds.

  3. The derivation of the exact optimal value OPT(Sk,t) = t(4s + 2) + k - 1 gives a precise benchmark for SCS solvers, enabling the development of more accurate approximation algorithms that aim to approach this proven limit rather than just relying on existing heuristics.

Abstract

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.

Related papers