The Greedy Superstring Conjecture Is False
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 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.Where the paper says it
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 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). 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.Where the paper says it
Where the paper says it
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 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. 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). 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. By combining the lower and upper bounds in Lemma 6 and Lemma 9, we obtain the exact optimal value. Theorem 10.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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 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.Where the paper says it
References
[1] Chris Armen and Clifford Stein. A 2 2/3 superstring approximation algorithm. p. 0 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.Where the paper says it
[2] Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications, Second Edition. Springer Monographs in Mathematics. p. 0 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.Where the paper says it
[3] Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear approximation of shortest superstrings. p. 0 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.Where the paper says it
[4] Bastien Cazaux and Eric Rivals. Relationship between superstring and compression measures: New insights on the greedy conjecture. p. 0 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.Where the paper says it
[5] Nikolai Chukhin, Alexander Kulikov, Ivan Mihajlin, and Alexander Smal. A tight cycle-cover inequality for shortest common superstring. p. 0 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.Where the paper says it
[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 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.Where the paper says it
[8] Matthias Englert, Nicolaos Matsakis, and Pavel Vesel´y. Approximation guarantees for shortest superstrings: Simpler and better. p. 0 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.Where the paper says it
[9] John Gallant, David Maier, and James A. Storer. On finding minimal length superstrings. p. 0 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.Where the paper says it
[10] John K. Gallant. String Compression Algorithms. p. 0 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].Where the paper says it
[11] Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, and Maksim Nikolaev. Collapsing superstring conjecture. p. 0 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. 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.Where the paper says it
Where the paper says it
[12] Dan Gusfield. Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. p. 0 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.Where the paper says it
[13] Haim Kaplan and Nira Shafrir. The greedy algorithm for shortest superstrings. p. 0 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.Where the paper says it
[14] Alexander S. Kulikov, Sergey Savinov, and Evgeniy Sluzhaev. Greedy conjecture for strings of length 4. p. 0 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].Where the paper says it
[15] Bin Ma. Why greed works for shortest common superstring problem. p. 0 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.Where the paper says it
[16] Eduardo Moreno. De bruijn sequences and de bruijn graphs for a general language. p. 4 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).Where the paper says it
[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 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].Where the paper says it
[19] Maksim S. Nikolaev. All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent. p. 0 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.Where the paper says it
[20] Maksim S. Nikolaev. Greedy conjecture for the shortest common superstring problem and its strengthenings. p. 0 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.Where the paper says it
[21] Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman. A new approach to fragment assembly in DNA sequencing. p. 0 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].Where the paper says it
[22] Heidi J. Romero, Carlos A. Brizuela, and Andrei Tchernykh. An experimental comparison of approximation algorithms for the shortest common superstring problem. p. 0 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.Where the paper says it
[23] Z. Sweedyk. A 2½-approximation algorithm for shortest superstring. p. 0 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.Where the paper says it
[24] Jorma Tarhio and Esko Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings. p. 0 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.Where the paper says it
[25] Esko Ukkonen. A linear-time algorithm for finding approximate shortest common superstrings. p. 0 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.Where the paper says it
[26] Virginia Vassilevska. Explicit inapproximability bounds for the shortest superstring problem. p. 0 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.Where the paper says it
[27] Vijay V. Vazirani. Approximation algorithms. p. 0 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.Where the paper says it
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
-
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. -
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. -
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
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time