A factor-two approximation for shortest common superstring
A factor-two approximation for shortest common superstring is the subject of a manuscript dated 24 September 2026 in OpenAI's public mathematics collection (github.com/openai/math). The shortest common superstring problem asks for a shortest string containing each of finitely many given strings as a contiguous substring; it is NP-hard, and the question of a polynomial-time factor-2 approximation has a long history. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
The original result
- Claim. There is a deterministic algorithm, polynomial in the total encoded input size, that on every finite collection of explicitly represented strings outputs a common superstring of length at most twice the optimum.
- Method, as described in the paper's introduction. The proof works in a hierarchical graph whose vertices are all substrings of the inputs. It constructs integer counts no larger than the number of occurrences of each word in any common superstring, so that their one-letter sum W is a lower bound on the optimum; a further rule handles periodic words. These counts give a balanced, possibly disconnected graph of cost W, which is then connected at additional cost at most W.
- Source. A Polynomial-Time 2-Approximation for Shortest Common Superstring in the openai/math repository (commit
adc7f12). - Formalization, as described by the repository. The scope note lean/docs/128.md states that the Lean formalization gives one deterministic polynomial-time algorithm whose output is a common superstring of length at most twice the unrestricted optimum, for every finite list of explicitly encoded strings, with running time measured in input bits and the ratio measured in symbol length. The comparator statement is Superstring.lean.
- Earlier results, as summarized in the paper. Tarhio and Ukkonen conjectured factor 2 for the maximum-overlap Greedy procedure; Blum, Jiang, Li, Tromp and Yannakakis gave a polynomial-time 3-approximation, Sweedyk 5/2, Mucha 2 + 11/23, and Englert, Matsakis and Veselý (14 + √67)/9 < 2.466 (ISAAC 2023). In 2026, Chukhin, Kulikov, Mihajlin and Smal reported a 7/3-approximation (ECCC TR26-157, A Tight Cycle-Cover Inequality for Shortest Common Superstring), and H. Shibata reported a counterexample to the Greedy conjecture with worst-case ratio at least 9/4 (arXiv:2609.01365, Disproving the Greedy Superstring Conjecture).
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 14 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | bkarak/shortest-superstring-js (GitHub) | Implementation | JavaScript implementations of shortest-common-superstring algorithms, centred on the factor-2 algorithm of the manuscript, together with Greedy-type heuristics, an exact solver and a benchmark. | Code repository. |
| 2026-10-07 | buberlo/veriscs (GitHub) | Implementation (formal) | An executable built from a Lean function, with a Lean theorem stating that for every instance it returns a common superstring of length at most twice the optimum; the README calls it "a verified reference and a test oracle" that "is very slow". | The README notes that the text codec is outside the proof and that the native binary is not a verified compiler artifact. |
| 2026-10-07 | rongou/superstring-rs (GitHub) | Partial implementation | A Rust library with preprocessing, an exact solver for small instances, a Greedy baseline and the manuscript's occurrence-count lower bound, as a foundation for the factor-2 algorithm. | The README states: "The approximation algorithm is not implemented yet." |
| 2026-10-11 | spele1100/scs-2approx (GitHub) | Implementation | A C++17 implementation of the factor-2 algorithm. Every run computes a lower bound W ≤ OPT and checks at run time that the output has length at most 2W. | Code repository. |
| 2026-10-13 | K. Dere and Svyatoblood, nurric-ai/lazy-scs (GitHub; manuscript Lazy Periodic Rules: A Scalable Implementation of the Factor-2 Approximation for Shortest Common Superstring) | Extension (implementation) | A scalable Rust implementation: the manuscript's periodic rules are enabled only where needed (every subset of them still gives a valid lower bound), and counts are stored on a suffix automaton, avoiding memory quadratic in the input. The lower-bound argument is formalized in Lean with only the standard axioms; benchmarks on bacterial sequencing reads are reported. | The repository contains the manuscript, code and Lean file; the authors describe themselves as independent researchers. |
Notes
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.