A new mathematical preprint reports that a greedy algorithm for combining strings can be driven toward an output twice the length of the best possible common string in the worst case when every input string has a fixed length k of at least 6. In the paper’s notation, the worst-case ratio ρₖ is at least 2 for every k ≥ 6. The result comes from specially constructed finite instances and a permitted sequence of tie decisions inside the algorithm, so it describes an extreme case rather than typical behavior.
At the shorter end, the paper gives a more precise answer. For inputs made of length-3 strings, it reports the exact worst-case ratio ρ₃ = 9/5. A construction provides the lower bound, while Theorem 5.1 provides the matching upper bound.
The work is an arXiv v1 preprint dated 20 Aug 2026. It studies mathematical string instances rather than people, animals, laboratory samples or measured real-world outcomes, and no journal peer-review status is reported in the supplied material.
A simple rule, measured in the worst case
The study asks how the greedy algorithm’s worst-case approximation ratio behaves when all input strings have the same fixed length. Its inputs are finite, nonempty sets S of distinct strings over finite alphabets. In a k-SCS instance, every input string has exactly k characters.
The underlying task is the shortest common superstring problem: find one string that contains every member of S, while keeping the result as short as possible. The paper calls the minimum possible length OPT(S), then compares it with the length of a particular greedy output, written as |g|.
GREEDY repeatedly chooses an ordered pair of distinct strings with the maximum available overlap, merges the pair, returns the merged string to the set and continues until one string remains. When several pairs have the same maximum overlap, the algorithm resolves the tie arbitrarily. That tie rule is central to the paper’s worst-case constructions.
For each fixed k, ρₖ is the supremum of |g|/OPT(S) across finite alphabets, possible greedy outputs and nonempty k-SCS instances. In plain terms, it records how bad the ratio can become under the most damaging permitted configuration, not an average score across a benchmark.
The construction that approaches the twofold bound
The k = 6 construction begins with cyclic spectra of two strings. They form an instance containing 9 distinct strings, each of length 6. The same set is also a linear 6-spectrum of a string of length 14, giving the authors a structured comparison for the greedy output.
The authors then iterate the construction. With t repetitions, the comparison superstring has length 9t + 5, while a possible GREEDY execution produces a superstring of length 18t. The resulting ratio is 18t/(9t + 5), which approaches 2 as t increases. Because ρ₆ is defined as a supremum over instances and greedy outputs, this family establishes ρ₆ ≥ 2.
For k ≥ 7, the paper generalizes the pattern by setting d = k − 6 and using the strings p = ABAABXy and q = ABXy. Their cyclic k-spectra are distinct, and the resulting set S has size 2k − 3. The construction keeps the inputs at one exact length while extending the same kind of adverse overlap pattern.
In the iterated version for these longer strings, the possible greedy output has length (4k − 6)t, and the displayed ratio lower bound has denominator (2k − 3)t + k − 1. Allowing t to vary gives ρₖ ≥ 2 for every k ≥ 7. Together with the k = 6 case, this yields the theorem for all k ≥ 6.
That conclusion needs to be read as a lower bound. It shows that the worst-case ratio reaches at least 2 in the supremum sense; it does not establish a universal upper bound of 2 for GREEDY. Nor does it say that every possible tie-breaking sequence follows the long route exhibited by the constructions.
Three-character inputs can be solved exactly
For k = 3, the paper uses a different construction to show how badly the rule can behave. After the selected merges, no nontrivial overlap remains, so GREEDY concatenates the remaining pieces and produces the lower bound ρ₃ ≥ 9/5.
The upper-bound argument turns the two relevant overlap phases into a directed-graph and trail-cover analysis. It links the overlap-two and overlap-one phases through trail covers of graphs G and M and introduces a budget σ. The proof overview derives the inequalities 2κ₂ ≤ n + τ(G) − σ and τ(M) ≤ 2σ + 2τ(G), connecting the accounting in the two phases.
Those bounds support Theorem 5.1, which gives ρ₃ ≤ 9/5. The lower and upper bounds therefore meet exactly: the paper reports ρ₃ = 9/5 rather than a range of possible values. The supplied analysis describes this as an exact value in the computationally hard range of the problem.
A theorem about constructed worst cases
The paper’s evidence is entirely combinatorial. It analyzes finite sets of strings, graph representations, cyclic-spectrum constructions and proof inequalities; it uses no empirical sample, statistical test or inferential model. The results are theorems about the defined instances, not estimates with statistical uncertainty.
The analysis also does not evaluate GREEDY in genome assembly, compression, scheduling or any other real-world application. It gives no evidence about human outcomes or about how often the adverse tie-breaking executions occur in practice.
The main open issue is the broader upper-bound question: the supplied text does not show that 2 is a global ceiling for the greedy algorithm. It also does not establish exact worst-case ratios for every shorter fixed length, including k = 4 and k = 5. The practical frequency and impact of the constructed bad executions remain unevaluated.
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