1 · The essentials
Suppose you have a finite collection of written strings and want one string that contains every one of them as an uninterrupted piece. The goal is to make that combined string as short as possible. The manuscript gives an algorithm whose output is never more than twice as long as the shortest possible answer. It works for every finite collection of ordinary strings supplied explicitly, rather than in a compressed or implicit form. Its running time is bounded by a polynomial in the full size of the encoded input, including the labels used for symbols. The main result has a Lean formalization, and its guarantee belongs to this particular algorithm—not to the classical method that repeatedly chooses the largest overlap.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine joining printed strips into one long strip, letting matching ends overlap while keeping each original strip readable without interruption. The algorithm promises a finished strip no more than twice the shortest achievable length; the image does not explain how it chooses the joins.
Why it matters
The result combines a bound on the answer’s length with a bound on the computation needed to produce it. Both guarantees apply to every explicitly represented finite input family, rather than only selected examples. The distinction from the classical maximum-overlap Greedy procedure matters: this result does not give that procedure the same guarantee.
2 · Going further
The shortest common superstring problem asks, for a finite family of strings, for a string containing every input string as a contiguous substring and having minimum length. Writing for that minimum, the manuscript’s algorithm returns a common superstring satisfying . The algorithm is deterministic, and its running time is polynomial in the total encoded input size, including symbol labels.
The supplied abstract states the construction’s guarantee but does not describe the algorithm’s steps or the main idea of its argument, so those cannot be explained from this source alone. It explicitly distinguishes the constructed algorithm from classical maximum-overlap Greedy. The main manuscript is marked as Lean-formalized; the supplied material does not give a finer breakdown of the formalization’s scope. Only one manuscript is supplied, so no relationship to companion manuscripts is specified.
Useful notions
- Strings as sequences of symbols
- Contiguous substrings
- Minimum-length optimization
- Polynomial running time
- Encoded input size
What was known before / what is new
Before
The source identifies classical maximum-overlap Greedy as a separate procedure. It gives no historical account or earlier approximation bounds, and it does not state whether any particular prior question remains open.
New
The manuscript presents a deterministic polynomial-time algorithm with a factor-two length guarantee for every finite family of explicitly represented ordinary strings. Its time bound includes the encoding of symbol labels. The main result has a Lean formalization.
Limits and assumptions
The stated hypotheses are a finite family of explicitly represented ordinary strings; compressed or implicit representations are outside the stated scope. The guarantee is an approximation bound, not a promise to return a shortest answer, and it applies only to the constructed algorithm, not classical maximum-overlap Greedy. The main result is Lean-formalized, but the source provides no detailed inventory of formally verified components. No remaining open problems or details of the algorithm and its argument are supplied.
Mini glossary
- Common superstring —
- A string that contains every input string as a contiguous substring.
- Contiguous substring —
- An uninterrupted sequence of symbols occurring within a string.
- Factor-two approximation —
- Here, an algorithm that returns a valid common superstring of length at most twice the minimum possible length.
- Deterministic algorithm —
- An algorithm whose prescribed choices do not depend on randomness.
- Polynomial running time —
- A running-time bound given by a polynomial in the size of the encoded input.
- Lean formalization —
- An encoding of a mathematical result and its justification for checking in the Lean proof assistant.
Keywords : Shortest common superstring · Approximation algorithms · Lean formalization
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Gives a deterministic polynomial-time algorithm constructing a common superstring of length at most twice the optimum for every finite family of explicitly represented strings. The running time is polynomial in the full encoded input length, including symbol labels.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
A Polynomial-Time 2-Approximation for Shortest Common Superstring
24/09/2026We give a deterministic algorithm that, for every finite family of explicitly represented ordinary strings, outputs a common superstring of length at most twice the optimum in time polynomial in the total encoded input size, including symbol labels. The guarantee applies to the algorithm constructed here, not the classical maximum-overlap Greedy procedure.