Greedy superstring conjecture
Let be a finite set of finite strings. For strings and , let be the maximum length of a string that is simultaneously a suffix of and a prefix of . The greedy superstring algorithm starts with the strings in and repeatedly replaces a pair having maximum overlap by their overlap-merged concatenation, breaking ties arbitrarily, until one string remains. If denotes the minimum length of a string containing every element of as a substring, then the conjecture asserts that for every finite set and every sequence of tie-breaks.
References
Progress summary
A new preprint sharpens the lower-bound examples, but the conjectured guarantee that the greedy method never exceeds twice the optimum remains unproved.
The conjecture, attributed to Tarhio and Ukkonen, says that repeatedly merging the most-overlapping pair produces a superstring of length at most twice the optimum, regardless of tie-breaking. Its unrestricted form remains open after more than thirty years.
Known results
- Strings of length at most , and strings of exactly , satisfy the conjectured bound (Bulteau et al., 2024).
- General upper bounds have improved from to , , and approximately ; is unproved.
- Explicit families attain ratios approaching from below, including tie-breaking-independent examples.
- Related hierarchical and collapsing variants are settled for strings of length at most (2019).
August 2026 lower-bound advance
On August 20, 2026, a report on the new arXiv preprint stated that it proves for every and computes . This strengthens the known lower-bound picture but does not establish the conjectured upper bound for arbitrary inputs; the preprint’s claims remain unverified here.
Current status (as of August 2026): The unrestricted assertion that greedy always achieves a factor- approximation remains open, while length-restricted lower bounds now include for and the exact value .
Solutions 1
Claimed by OpenAI. The manuscript claims a deterministic polynomial-time algorithm that constructs a common superstring of length at most twice the optimum for every finite input set of strings. This is related approximation progress for the same optimization problem. Its algorithm is distinct from the page’s maximum-overlap Greedy procedure, and the manuscript does not establish that procedure’s factor-two guarantee for arbitrary tie-breaks.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-128-01-A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring.pdfOpen