A greedy algorithm for stitching short strings into one common string can be forced to produce an answer at least twice as long as the best possible answer once the input strings are six characters long or longer, according to a new mathematical analysis. The result is a worst-case guarantee: it identifies formal examples where the method can go badly wrong, rather than measuring how it behaves on typical data.
The same work settles the three-character case exactly. For sets of strings of length three, the algorithm’s worst-case approximation ratio is 9/5. In other words, the longest bad outcome allowed by the paper’s model is nine units of output for every five units in an optimal solution.
A rule built around the biggest overlap
The problem is the shortest common superstring problem. The input is a finite, nonempty set of distinct strings over a finite alphabet, and the task is to arrange them inside one string as compactly as possible. The analysis focuses on the case in which every input string has the same length, written as k.
GREEDY repeatedly looks for an ordered pair with the largest overlap—the number of characters that can be shared when one string is placed after another—merges that pair, and repeats until one string remains. If several pairs have the same overlap, the algorithm allows arbitrary tie-breaking. That detail matters because the lower-bound examples use permissible choices among ties to obtain a particularly long final string.
This is a proof-driven study, not a statistical experiment. The authors analyze constructed string sets and their overlap graphs, which represent how strings can be joined. The upper-bound argument for length three follows the merging process through trail covers and budget inequalities, linking the stages with overlap two and overlap one through a shared accounting quantity.
The factor-two example begins with nine strings
For strings of length six, the authors construct a set containing nine distinct strings. Those strings can all be found inside a common superstring of length 14, showing the compact arrangement available for comparison with GREEDY.
A possible sequence of maximum-overlap choices leaves two merged strings with lengths 11 and 8. Their remaining overlap is only one character, so the final greedy superstring has length 18. Repeating the construction gives a comparison length of 9t + 5 against a possible greedy length of 18t, which yields the lower bound ρ6 ≥ 2.
The conclusion is about the ratio’s worst case, not about every run of the algorithm. A different way of resolving equal-overlap choices can produce a different output, while the lower-bound result only needs one allowed sequence to establish the bound.
The construction extends beyond length six
The authors extend the idea to every string length k at least seven. In the base construction, the optimum common superstring has length 3k − 4, while a possible greedy outcome ends with a one-character overlap and length 4k − 6.
An iterated version reports a common-superstring length of (2k − 3)t + k − 1 and a possible greedy length of (4k − 6)t. From these families, the analysis concludes ρk ≥ 2 for every k ≥ 6, covering the length-six construction and all the longer lengths treated by the theorem.
The result is therefore a lower bound for the longer cases. It does not establish that the exact ratio is two for every k at least six, because a matching upper bound is not supplied for those lengths.
Length three is fully characterized
The length-three result has both halves. A constructed instance can make GREEDY produce a superstring of length nine when an optimum has length seven, proving a lower bound of 9/5. A repeated version uses an underlying string of length 5t + 2 with 5t distinct three-character strings; GREEDY can form 2t strings and produce an output of length 9t.
The paper then proves the matching upper bound. Its overlap-graph analysis connects local trail covers through a budget σ, deriving inequalities that control both the overlap-two phase and the overlap-one phase. Combining those local covers gives a final greedy-to-optimum ratio below the paper’s 9/5 threshold, completing the equality ρ3 = 9/5.
That exact statement applies to the formal three-character model defined in the analysis. It is not an average performance estimate, and the work reports no empirical benchmark, implementation evaluation, or real-world validation.
Several questions remain open
The findings do not show that the unrestricted greedy superstring ratio is at most two or exactly two. They also do not give exact values for strings of length four or five. Those cases, along with the exact ratios for other lengths not characterized here, remain unresolved in the supplied analysis.
The practical meaning of the constructions is also left open. Because GREEDY permits arbitrary tie resolution, future work would need to examine how specific implementations behave and how these worst-case examples relate to practical performance. The analysis itself makes no claim about average-case or real-world behavior.
The work is a preprint on arXiv, identified in its front matter as version 2 dated 24 Aug 2026; no journal venue is reported. The authors also disclose using GPT-5.6 Sol Ultra and GPT-5.6 Sol Pro for construction, proof, proofreading, and literature-review work, while stating that they independently verified all arguments.
Paper data and sources
Original title: The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already
Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text