Shortest common superstring: assembling fragments within a factor of two

← All digests

Family 128 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Given several text fragments, construct the shortest string containing every fragment as a consecutive block. Overlaps can save space: the strings abc and bcd both fit inside abcd, shorter than their direct concatenation.

This is the shortest common superstring problem. It is easy to produce some answer by concatenating the inputs, but difficult to find the shortest answer in general. Approximation algorithms aim for a provable ratio between the output length and the unknown optimum.

The natural greedy idea repeatedly merges a pair with maximum suffix–prefix overlap. That procedure inspired a famous factor-two conjecture, but the question of whether some polynomial-time algorithm achieves factor two is broader than the question about that particular greedy rule.

This manuscript claims a deterministic factor-two algorithm for every finite family of explicitly represented ordinary strings. Its construction uses a graph of substrings, lower bounds on required occurrence counts, and periodicity arguments to join graph components. The claim concerns this new algorithm; it does not assert a factor-two guarantee for classical maximum-overlap Greedy.

2. Background and essential definitions

A string is a finite sequence of symbols from an alphabet. A substring must occupy consecutive positions. A subsequence may skip positions, so shortest common superstring is different from shortest common supersequence.

For an input family $S$, let $\operatorname{OPT}(S)$ be the minimum number of symbols in any string containing all members of $S$ as substrings. A factor-two algorithm outputs $T$ with

$$|T|\le2\operatorname{OPT}(S).$$

Repeated input strings do not require repeated occurrences: one occurrence can satisfy several identical requests. An input contained inside another input can also be removed without changing the problem. Empty strings impose no constraint.

The suffix–prefix overlap of two strings is the longest ending of the first that equals a beginning of the second. Merging along an overlap saves its length. But locally large overlaps can interact badly with later choices, which is why an approximation proof needs a global comparison with the optimum.

A periodic text repeats a finite pattern indefinitely in both directions. Its least period is the length of the shortest repeating pattern. Finite strings can agree with portions of several periodic texts; long enough agreement constrains how those periods relate.

The input encoding matters as well. Let $L$ be the sum of input lengths in symbols and $N$ the total encoded bit length, including symbol labels and boundaries. The manuscript charges for comparing and writing labels, rather than assuming that an arbitrarily large symbol identifier is a unit-cost object.

3. Development history and previous partial results

Tarhio and Ukkonen proposed the factor-two conjecture for maximum-overlap Greedy in their 1988 paper. The algorithm is simple and appealing, but its behavior is not settled merely by observing that each merge makes a locally optimal saving.

Blum, Jiang, Li, Tromp, and Yannakakis gave a polynomial-time factor-three approximation. Their work helped establish cycle covers as a central lower-bound tool: arranging strings in cycles is easier than joining everything into one final string, but opening those cycles incurs additional cost.

Sweedyk improved the factor to $5/2$. Mucha subsequently used lexicographically distinguished rotations of periodic strings to obtain $2+11/23$. Englert, Matsakis, and Veselý gave a further improvement below 2.466 in ISAAC 2023. The source also cites an August 2026 preprint claiming a $7/3$ approximation.

Another line of work represents strings in a hierarchical graph of their substrings. Golovnev, Kulikov, and Mihajlin introduced a related bounded-length formulation; the Collapsing framework developed the all-substrings version. This representation is the new manuscript’s direct starting point.

The manuscript also acknowledges a September 2026 preprint by Shibata reporting a counterexample to the classical Greedy conjecture, with ratio at least $9/4$. These contemporaneous claims make the distinction between an existence theorem for a factor-two algorithm and a theorem about Greedy especially important. The present family claims the former through a different construction.

4. What the new manuscripts claim

For every finite family $S$ of explicitly represented ordinary strings, the manuscript states that a deterministic algorithm outputs a common superstring $T$ satisfying

$$|T|\le2\operatorname{OPT}(S)$$

in time polynomial in $N$, the full encoded input size. The output string itself is constructed, not merely its estimated length.

The guarantee allows arbitrary finite symbol labels whose encodings are included in the cost. It does not assume a fixed-size alphabet or constant-cost operations on unbounded labels. All tie-breaking choices can be made deterministically from the explicit encodings.

A useful intermediate object is a collection of integer lower bounds $m(s)$ for the number of occurrences of each relevant substring $s$. For every common superstring $T$, the paper claims

$$m(s)\le N_T(s),$$

where $N_T(s)$ counts occurrences, including overlapping ones. In particular,

$$W=\sum_{c\in\Sigma}m(c)\le\operatorname{OPT}(S),$$

with $\Sigma$ the set of symbols appearing in the input.

The algorithm constructs a balanced graph of cost $W$, then connects its components with additional cost at most $W$. A traversal of the connected graph produces the final string. Thus the advertised factor is supported by the concrete chain $|T|\le2W\le2\operatorname{OPT}(S)$.

This theorem does not claim exact optimization, a factor below two, or optimality of the factor-two boundary. Nor does it assume the Greedy or Collapsing conjecture as an input to its argument.

5. Why the advance matters

Provisional importance: 3/5. Reaching factor two would settle a prominent approximation target for a classical string problem. It also gives a structural account of how local fragment requirements can be assembled globally without paying more than one extra copy of a suitable lower bound.

The model appears naturally in text compression and idealized sequence assembly. Those motivations explain the interest, but real assembly tasks can involve errors, missing coverage, reverse complements, or statistical uncertainty. The theorem concerns exact containment of the supplied ordinary strings.

The method is interesting because its lower bound already incorporates periodic constraints. Periodicity is often the source of troublesome overlaps: a short repeated pattern can create many locally attractive merges whose global relationship is ambiguous. Accounting for this structure before joining components aims to prevent the final connection cost from exceeding the allowed budget.

The score reflects a substantial advance in approximation and string algorithms. It is narrower than a general solution to sequence assembly, and the manuscript does not supply benchmark evidence establishing a practical advantage over existing heuristics.

6. The main idea

Make a graph whose walks spell strings

Create one vertex for every distinct substring of the inputs, including the empty string. There are at most $O(L^2)$ such vertices. An upward edge appends one symbol and costs one; a downward edge deletes the first symbol and costs zero, whenever both endpoint strings belong to the graph.

Starting at the empty string, record each symbol appended by an upward edge. At every stage, the current vertex is a suffix of the text already written. Therefore visiting an input-string vertex guarantees that the output contains that string as a substring.

A directed multigraph is balanced when every vertex has equal incoming and outgoing degree. If its used edges form a connected support, it has an Euler tour: a closed walk traversing every edge copy exactly once. A balanced, connected graph visiting all required strings therefore provides a superstring whose length is its number of upward edges.

Build a lower bound strong enough to pay for connections

The occurrence counts are computed from longer strings toward shorter ones. If a string must occur, so must its prefixes and suffixes. Counts of extensions also constrain the shorter string because occurrences with distinct preceding or following symbols are distinct.

Periodicity adds another rule. Relative to a repeated text, an occurrence can be bracketed by mismatching symbols on both sides. Such brackets account for certain occurrences that stop following the periodic pattern. If a long periodic fragment has more required occurrences than its brackets explain, shorter prefixes must occur repeatedly along the unbroken periodic stretch.

The manuscript turns this observation into explicit integer inequalities. Although the description mentions infinite periodic texts, the algorithm only needs finitely many candidates derived from the input substrings and their possible periods. The resulting counts yield a balanced graph with cost $W$, but it may have several disconnected components.

Use each periodic component’s budget once

Decompose that graph into closed walks. Repeating the symbols appended by a walk gives a periodic text. Walks with the same text can be reorganized into layers that each traverse one least period. A layer of period $p$ costs $p$ and receives another $p$ units to pay for connections.

The challenge is not merely to find connections. It is to arrange them so that two different connections do not spend the same budget. Some can be funded entirely by their source layers. Others need help from a target, but these requests are arranged to go toward strictly larger periods and are handled collectively.

Residual source-funded connections can form cycles. The manuscript uses a lexicographically maximal rotation on each such cycle to locate a short contact. By omitting one outgoing connection and joining the relevant layers internally, it saves enough to connect that component to the empty-string vertex.

The claimed accounting keeps the total added cost at most $W$. Once connectivity is obtained, an Euler tour writes the answer directly. The final graph has polynomially many explicit edge copies, so the construction does not conceal an exponentially long output or an implicit search over infinite words.

7. Scope, limitations, and open questions

The strings are explicit. A very long string represented by a small grammar, a repetition count in binary, or another compressed format is a different input model. The polynomial-time statement should not be transferred to such encodings without further work.

The guarantee is exact containment of ordinary strings. It does not allow mismatches or gaps, and it does not choose between a fragment and its reversal or reverse complement. Such variants can change both the graph representation and the approximation analysis.

Factor two is the stated guarantee for this algorithm. The digest does not attribute it to maximum-overlap Greedy, and the source’s discussion of the reported Greedy counterexample remains relevant even if the new algorithm succeeds.

Further questions include obtaining a factor strictly below two, simplifying the construction, and understanding its practical cost. The theorem establishes polynomial encoded complexity, but a polynomial-time existence result alone does not determine whether the procedure is preferable on real datasets.

8. Sources and further reading

The historical links cover the original Greedy proposal, cycle-cover approximations, and the hierarchical graph formulation. The two 2026 preprints are included because the source explicitly uses them to frame the current approximation landscape. The manuscript below supplies the forced-count construction, periodic connection argument, and deterministic encoding analysis.

Source manuscripts

• M1. OpenAI, A Polynomial-Time 2-Approximation for Shortest Common Superstring (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.