Shortest common superstring: the factor of two, measured

A couple of weeks ago I wrote about the mathematicians' reaction to the Navier–Stokes announcement, and then about how OpenAI actually ran it. Since then OpenAI has put the rest of that work in the open; the openai/math repository holds 722 manuscripts in 372 families, produced by an internal model that was posed about 4,000 open problems (each result took about three hours of ChatGPT Pro thinking on average, according to its README). Most of it is far from anything I can judge. But result 128 is not. It is about strings, and strings I can test on my laptop.

Result 128 is a polynomial-time 2-approximation for the shortest common superstring, dated 24 September 2026, and it comes with a Lean formalization of the main theorem. So I did what I usually do with a claim like this; I implemented it, put it next to the algorithms it claims to beat, and measured. The code is at bkarak/shortest-superstring-js.

The problem

You get a set of strings and you want the shortest string that contains every one of them as a contiguous substring. For cde, abc and efg the answer is abcdefg; you glue them in the right order and let the overlaps collapse. The textbook motivation is DNA (Deoxyribonucleic Acid) sequencing, where the strings are short reads of a long genome and the superstring is a guess at the genome; data compression is the other one.

The problem is NP-hard (no surprise there), so the interesting question is how close to the optimum a fast algorithm can be guaranteed to stay. And here the story is older than most of the people working on it.

Thirty-eight years of factors

Every course that mentions the problem teaches Greedy; take the two strings with the largest overlap, merge them, repeat. In 1988 Tarhio and Ukkonen conjectured that Greedy is never worse than twice the optimum. Nobody could prove it, and the factors that people could prove came down slowly, one algorithm at a time:

• 3, Blum, Jiang, Li, Tromp and Yannakakis (1994), with TGREEDY; the same paper proved 4 for Greedy itself and for MGREEDY.
• 2.5, Sweedyk (1999).
• 2.478, Mucha (2013).
• 2.465, Englert, Matsakis and Veselý (2023).
• 2.333, Chukhin, Kulikov, Mihajlin and Smal, a preprint from August 2026.
• 2, this paper, a month later.

Two things in that list deserve a second look. The first steps after 1999 were tiny, a hundredth or two at a time, which tells you how hard each one was; then the last two came within a month of each other. And the factor 2 did not come from Greedy. The paper is careful about this (it says so in the abstract), and it cites another September 2026 preprint, by Shibata, that reports a counterexample to the Greedy conjecture with a ratio of at least 9/4. So the conjecture that started the whole thing seems to be false, and the bound it promised was reached by a completely different road. I have not read Shibata's preprint; that part is second-hand, from the paper's introduction.

Taking the lid off

The algorithm does not merge strings at all. It works on a graph whose vertices are all the distinct substrings of the input, the empty one included. An up edge appends a letter and costs one; a down edge deletes the first letter and costs nothing. Walk around such a graph, write down every letter you append, and you get a string that contains every vertex you passed through. So the problem becomes; build a connected, balanced graph through all the inputs with as few up edges as possible. The idea of this graph is not new (the paper credits Golovnev, Kulikov and Mihajlin, and the "Collapsing" framework after them). What is new is the way the edges are counted.

The algorithm proceeds in four steps:

1. Forced counts. For every substring it computes a number that no superstring can go under: at least the counts of its one-letter extensions, at least one for an input, and a rule for periodic words. The one-letter counts add up to a lower bound W on the optimum.
2. Layers. The graph those counts define is split into closed walks, and walks over the same repeating text are rearranged into layers, each going around one period.
3. Budgets. A layer of period p costs p and receives an extra budget of p; all the budgets together are W again.
4. Connections. The layers are connected to the empty word using only those budgets, so the final walk costs at most 2W, which is at most twice the optimum.

The periodic rule is the heart of it, and the paper's own example shows why. Take a single input, aaaaa. The extension rules alone are happy with every aj occurring once, which gives a lower bound of 1 (obviously wrong). The periodic rule notices that aaaaa has period 1, so a prefix shorter by k letters must occur k + 1 times; aaaa twice, aaa three times, and so on, and the bound becomes 5. The repeated letters that a naive count misses are exactly what makes the bound tight. Step 4 is where most of the paper's 19 pages go; requests sent from short periods to longer ones, joins inside a period group, and a rule that breaks cycles of connections at the lexicographically greatest rotation of a periodic text (I would never have guessed that last one).

The implementation is about 1,200 lines of JavaScript with no dependencies. I added two finishing steps that the paper does not have, and both can only make the answer shorter; walks that the connectivity turns out not to need are dropped, and letters at either end are trimmed while every input still occurs. The repository also has Greedy, MGREEDY, TGREEDY, plain concatenation and an exact solver (dynamic programming over subsets, fine up to about 16 strings), so there is something to compare with.

The numbers

The harness generates four families: random strings over 4 and over 26 letters, reads cut from a random genome, and strings cut from repetitions of a few short seeds (the periodic case, where the paper's rule does its work). For small instances, 3 to 10 strings, there are 300 per family and each is compared with the exact optimum. All of it ran on my M4 Max with Node 26, in about 30 seconds.

Ouch. On average Greedy wins, and on genome reads it is optimal 98% of the time while the new algorithm manages 74%. On random strings over 26 letters (not in the table) every algorithm except concatenation is optimal almost always, which says more about the instances than about the algorithms. The 2-approximation is also slower on small inputs, about 0.15 ms against 0.015 ms, ten times. MGREEDY, which I left out of the table, is the worst of the lot on periodic strings, 1.201 on average.

But a guarantee is not about the average. It is about the instance you did not think of, and for Greedy that instance has been known for decades: c(ab)k, (ba)k and (ab)kc. Greedy sees the huge overlap between the first and the third, merges them, and leaves the middle one stranded.

Greedy writes 4k + 2 letters against an optimum of 2k + 4, so its ratio climbs towards 2 as k grows. The new algorithm stays two letters above the optimum, whatever k is. That is the whole point of the paper in one table.

For large inputs the optimum is out of reach, but the algorithm brings its own yardstick; the lower bound W. On the small instances W averaged between 0.970 and 1.000 of the optimum, depending on the family (the loosest single case was 0.667, on genome reads). On a thousand 40-letter reads of a 2,000-letter genome, every algorithm wrote strings within half a percent of W on average (2% in the worst case), which means at least that close to the optimum, and now we can actually say so.

And is it faster?

No, and the one number that says otherwise is my fault. On the small instances the new algorithm takes about 0.15 ms against Greedy's 0.015 ms. On sixty periodic strings it takes 16 ms against 0.13 ms, more than a hundred times slower, and on two hundred random strings 22 ms against 11 ms. Only on the thousand genome reads does it win, 86 ms against 271 ms.

That last win belongs to my Greedy, not to the paper. My Greedy computes the overlap of every pair of strings before it merges anything; a thousand strings means a million pairs, and that quadratic step is what the 271 ms pays for. The textbook way to implement Greedy (Gusfield's book has it) finds all the overlaps with a suffix tree, in time close to linear in the total length of the input, and a Greedy written that way would win here too. The new algorithm has no such way out. Its graph has a vertex for every distinct substring of the input, so time and memory grow with the square of the total length by construction; ten thousand letters of input can already mean tens of millions of vertices.

To be fair to the authors, speed was never the claim. The theorem says "polynomial time", and in complexity theory that is the whole requirement; nobody proving a factor of two is trying to beat a suffix tree. But if you were thinking of assembling a genome with it, with millions of reads, forget it.

So, who is better?

It depends on what "better" means, and there are three answers to it.

• Shorter answers on the inputs you will actually meet: mostly Greedy. Its average was better in seven of the eight families. The exception was two hundred random strings over four letters, where the new algorithm wrote exactly W letters every time (so its answers were provably optimal) and Greedy was 0.02% longer. On the small four-letter instances the new algorithm also found the optimum more often, 91% against 85%, even though its average was a little worse.
• Speed: Greedy, by a wide margin once it is implemented properly.
• A promise about the worst case: the new algorithm, and only the new algorithm. Whatever the input, it never writes more than twice the optimum, and it tells you its lower bound, so you know how far from the best you can be. Greedy has neither; there are inputs where it approaches twice the optimum (Table 2) and, if Shibata is right, inputs where it goes past it.

So the new algorithm is not the better algorithm; it is the better guarantee. Of course, a guarantee is worth something only when the bad case can happen to you, and in a pipeline nobody controls the input for, it can. My advice is boring; run both and keep the shorter. You get Greedy's answers almost every time, and the factor of two on the day Greedy is fooled.

Epilogue

What stays with me is something else. A bound that people chipped at for thirty-eight years was closed by a model, with a proof that a machine has checked. The paper is readable, and turning it into working code took a careful reading and no guessing; I did not find a single step that failed on the 1,200 instances the tests run. But 1,200 lines of an algorithm whose correctness argument lives in a PDF (and in Lean) is a new kind of dependency. Who maintains it, when the person who reads the proof is not the person who wrote it?

The code, the benchmark and the full results are at bkarak/shortest-superstring-js, MIT licensed. Run npm run bench and you will get your own numbers :)