A factor-two approximation for shortest common superstring

The explanation

Take the word SUPERSTRING and cut it into overlapping four-letter pieces. You get eight: SUPE, UPER, PERS, ERST, RSTR, STRI, TRIN and RING. Now forget the word and keep only the pieces. The task is to find the shortest string that contains every piece as an unbroken run of letters. Gluing the pieces end to end works, but it spends 32 letters. Sliding each piece over the one before saves most of that. SUPERSTRING itself has 11 letters and contains all eight. A computer search over all 40,320 orders of the pieces finds nothing shorter.

This puzzle is the shortest common superstring problem. A superstring of a list is a string that contains every item as an unbroken block. The shortest possible length is called the optimum. Here the optimum is 11. With eight pieces, trying every order is easy. With twenty pieces there are about 2.4 billion billion orders to try.

So researchers settle for a guarantee instead of the exact answer. A factor-two approximation is a method whose answer is never more than twice the optimum. Here it would promise at most 22 letters. Plain gluing, at 32 letters, breaks that promise. The method must also be fast. Here that means polynomial time: the running time grows at most like a fixed power of the input's size.

Factor two has been the target since 1988. That year, Jorma Tarhio and Esko Ukkonen conjectured that a simple greedy method reaches it. Greedy repeatedly merges the two pieces with the largest overlap. Proven guarantees came in steps. Avrim Blum, Tao Jiang, Ming Li, John Tromp and Mihalis Yannakakis reached factor 3 in 1994. Z. Sweedyk reached 5/2 in 1999. Marcin Mucha reached 2 + 11/23, about 2.478, in 2013. Matthias Englert, Nicolaos Matsakis and Pavel Veselý got below 2.466 in 2023. An August 2026 preprint by Nikolai Chukhin and three coauthors reports 7/3, about 2.333.

Many earlier methods start from a lower bound [a number that can never exceed the optimum]. It comes from arranging the pieces into separate loops instead of one chain. The loops must then be opened and joined into one string. Each join adds letters, and the difficulty is keeping that extra length under control.

This paper builds its lower bound differently. For each short word, it computes a count. The count never exceeds how often that word must appear in any superstring. Adding up the counts for single letters gives a number W. W can never exceed the optimumSource 1. Words that repeat a pattern, like ABABAB, need a further counting ruleSource 2. From the counts, the paper builds a map of wordsSource 3. Adding a letter costs one, and dropping the first letter costs nothingSource 4. Tracing this map spells out string pieces with total cost W. But the map may fall into separate parts. The paper then joins all the parts for at most W extra lettersSource 5. The hard work is paying for those joins without spending the same budget twiceSource 6.

That gives at most 2W letters, and 2W is at most twice the optimumSource 5. The paper proves this for every finite list of piecesSource 7. For the SUPERSTRING pieces, its method must return 22 letters or fewer. It does not promise 11. It also says nothing about GreedySource 8. A September 2026 preprint by Hiroki Shibata reports a counterexample to the Greedy conjecture, with ratio at least 9/4. The paper shows its running time is polynomialSource 9. It does not show the method is quick in practice.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It states one deterministic polynomial-time method whose output is at most twice the optimum. Time is counted in input bits and length in letters. A tool called Comparator matches the Lean proof to a fixed reference statement. No specialist review has been published.

What it doesn't show. This does not find the shortest superstring itself. Nor does it show that the classic greedy method reaches factor two.