A factor-two approximation for shortest common superstring

Source and verification

This article explains family 128 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Superstrings, overlaps, and the objective

A common superstring of a finite collection $\mathcal{S}$ contains every input string as a contiguous substring. The objective $\mathrm{OPT}(\mathcal{S})$ is the shortest possible symbol length. Containment as a subsequence is insufficient.

For example, ababa contains both aba and bab. But the shorter abab already contains both, so a feasible output need not be optimal. Merging strings by overlaps is natural, yet a theorem for one carefully designed algorithm need not apply to the familiar rule that repeatedly chooses a maximum overlap.

Inputs explicitly encode symbol labels and string boundaries. Let $N$ be their total bit length and $L$ the sum of input lengths in symbols. Then $L\le N$. Runtime charges the encoded length of symbol operations, while the approximation ratio measures symbol length.

Manuscript statement

One deterministic algorithm, polynomial in $N$, returns a common superstring $T$ satisfying

$$|T|\le 2\mathrm{OPT}(\mathcal{S})$$

for every finite collection of explicitly represented ordinary strings. (OpenAI, 2026)

The statement concerns this algorithm, not the maximum-overlap Greedy procedure or a prescribed Collapsing procedure. Empty strings, duplicates, and strings contained in another input can be removed without changing the feasible superstrings. If nothing remains, return the empty string.

🏷️ A graph whose walks spell strings

Let $V$ be all distinct substrings of the remaining inputs, including the empty word $ϵ$. There are $O(L^2)$ such vertices. For nonempty $s$, an up edge goes from its prefix with the last letter deleted to $s$, appending that letter at cost one. A down edge goes from $s$ to its suffix with the first letter deleted, at cost zero.

A balanced directed multigraph has equal incoming and outgoing degrees at every vertex. If its used support is connected, includes $ϵ$, and visits all required input vertices, an Euler tour starts at $ϵ$ and uses every edge once. Write down the appended letter at each up edge.

Inductively, the current vertex word is always a suffix of the output written so far. An up edge appends to both; a down edge only removes the first symbol of the current suffix. Visiting a required vertex therefore certifies that it occurs contiguously in the output. The output length equals the total up-edge cost.

The construction has two tasks: obtain a balanced base graph whose cost is a lower bound on the optimum, then connect it while spending at most that much again.

🏷️ Forced occurrence counts

For a string $T$, let $N_T(s)$ count occurrences of $s$, including overlapping ones. The source computes nonnegative integers $m(s)$ such that

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

for every common superstring $T$. Since one-letter occurrences partition the positions of $T$,

$$W=\sum _{c\in \Sigma }m(c)\le \mathrm{OPT}(\mathcal{S}).$$

Counts are computed in decreasing order of word length. Required strings have count at least one. Every word also satisfies

$$\begin{array}{c}m(s)\ge \sum _{c}m(cs),\\ m(s)\ge \sum _{c}m(sc).\end{array}$$

These follow from disjoint preceding-letter or following-letter classes of occurrences. But they alone can miss repeated symbols badly. For the single input $a^h$, they allow $m(a^j)=1$ at every positive length, yielding only the lower bound $W=1$ instead of $h$.

🏷️ Periodicity and bracketing

A periodic text is a two-sided infinite sequence $A$ repeating with some positive period $p$. An occurrence of $s$ aligned with $A$ is blocked when the nearest mismatching symbols on both sides determine a bracketing word belonging to $V$. Let $b_{A,s}(r)$ count the ways a word $r$ provides such a bracket, and define

$$B_A(s;m)=\sum _{r\ne ϵ}{b}_{A,s}(r)m(r).$$

Only words at least two symbols longer than $s$ contribute. Multiplicity is important: one bracket may surround several occurrences of the same shorter word.

Suppose a word $v$ agrees with $A$, and its nonempty prefix $w$ is shorter by $kp$ for some integer $k\ge 1$. The additional count rule is

$$\begin{array}{c}m(v)>B_A(v;m)\\ ⟹m(w)\ge B_A(w;m)+k+1.\end{array}$$

Intuitively, a long unblocked occurrence contains $k+1$ distinct period-spaced occurrences of the prefix. The implication is computable in descending order because all counts on its right-hand side refer to words longer than $w$.

Its validity for actual occurrence counts needs two cases. If $T$ has an unblocked occurrence of $v$, its $k+1$ period-spaced prefixes are also unblocked, giving the bound. Otherwise all occurrences of $v$ are blocked. Since the computed trigger still holds, some longer bracketing word must have more actual occurrences than its computed count. Each such surplus bracket contributes at least $k+1$ placements of $w$, giving the same inequality. Thus the proof does not assume that a strict inequality for computed counts automatically remains strict for actual counts. (OpenAI, 2026)

For $a^h$, the constant periodic text has no blocking words. The rule forces $m(a^j)\ge h-j+1$, and comparison with the input itself gives equality. Hence $W=h$, recovering the missing repeated letters.

🏷️ Building the balanced graph

Give the up and down edges associated with $s$ multiplicities

$$\begin{array}{rl}u(s)& =m(s)-\sum _{c}m(cs),\\ d(s)& =m(s)-\sum _{c}m(sc).\end{array}$$

They are nonnegative by the extension rules. The incoming degree at $s$ is $u(s)+{\sum }_{c}d(cs)$; the outgoing degree is $d(s)+{\sum }_{c}u(sc)$. Both simplify to

$$m(s)-\sum _{c,d}m(csd).$$

Thus the graph is balanced. Summing the multiplicities telescopes, leaving exactly $W$ up edges and $W$ down edges. Every required string, having no longer extension among the remaining substring vertices, receives positive multiplicity and is visited.

For the single input aaaa, the top panel shows the inadequate extension-only counts; the lower panel includes the periodic rule. Arrow labels are up costs one and down costs zero. Gray vertices are available substring labels unused by the top graph. The exact example illustrates the base construction, not the general connection theorem.

Balance does not imply connectivity. A union of disjoint directed cycles has equal in- and out-degrees but no single Euler tour visiting them all. Connecting the base graph within an additional budget $W$ is the main remaining theorem.

🏷️ Periodic layers and connection budgets

Decompose the base graph into closed walks. Repeating the letters appended by one walk produces a periodic text, and its visited vertices are intervals in that text. Walks sharing the same text can be rearranged without changing edges into ordered layers, each traversing one least period.

A layer with period $p$ has up cost $p$ and receives another budget $p$. All additional budgets sum to $W$. Agreement of intervals in two differently aligned texts gives an actual substring vertex at which a connection can attach; agreement merely as abstract positions would not suffice.

The count rule guarantees such a contact in the difficult case. If enough repeated material cannot be charged to brackets of the current text, a shorter word must occur on a layer carrying a different aligned text. The construction searches actual visited windows for that contact.

Some connections are paid entirely by their source layers. Others require a target contribution, but these requests go only toward strictly larger periods and are processed collectively. The ordering prevents circular dependence among target-funded requests.

Source-funded connections can still form directed cycles. The source proves that the relevant layers can instead be joined internally while saving one period of budget. On a cycle, a maximal lexicographic rotation supplies a contact word no longer than the target period. Omit that target’s outgoing connection and use the saved budget for a round trip between the contact and $ϵ$. This attaches the cycle to the root without charging a layer twice. (OpenAI, 2026)

These periodic contact and budget lemmas are essential. Arbitrarily connecting each component separately to the empty word can exceed $W$ even though the base graph itself costs only $W$.

🏷️ The factor two and explicit polynomial work

Every added walk is closed, so balance is preserved. After the connection theorem, all required vertices lie in one used component containing $ϵ$, and

$$\begin{array}{rl}\text{total up cost}& \le W+W\\ & \le 2\mathrm{OPT}(\mathcal{S}).\end{array}$$

The Euler construction therefore proves the approximation ratio and gives the actual output string.

The apparent search over periodic texts is finite. A relevant period $p<|v|$ is determined by the first $p$ letters of an input substring $v$. Enumerating $v,p,k$ gives a polynomial list of rules. Bracketing counts are found by checking substrings and their placements.

The count upper bound against the concatenation of all inputs gives $m(s)\le L$, so counts have bounded binary length. The base graph has exactly $2W\le 2L$ edges with multiplicity, and the final graph at most $4W\le 4L$. Layers are stored by one primitive period and finite phase data; the algorithm never constructs an infinite periodic text.

All tie breaking uses deterministic orders on explicit labels and stable edge identifiers. Symbol comparisons and output writing are charged in bits. These details turn the existence of suitable counts, contacts, and Euler tours into the stated uniform polynomial-time algorithm.

🏷️ Key steps and proof outlines

A period constraint that survives lower-bound substitution

The occurrence counts $m(v)$ are lower bounds, whereas the unknown optimum has actual counts $N(v)$. A conditional inequality for $N$ does not automatically remain valid after replacing every occurrence of $N$ by $m$. The manuscript’s period argument explicitly resolves this issue. Fix a periodic alignment $A$, a word $v$, and a prefix $w$ obtained by shortening $v$ by $kp$, where $p$ is the period. Let $B_A(v;m)$ count the copies of $v$ accounted for by longer words whose nearest mismatch brackets obstruct that alignment, with the source’s prescribed multiplicities. The update is triggered by $m(v)>B_A(v;m)$ and requests $m(w)\ge B_A(w;m)+k+1$.

The trigger is justified by a two-case induction.

Either an actual copy of $v$ is not accounted for by a mismatch bracket, or a longer bracket word has an actual count strictly larger than its current lower bound. Each case supplies the required $k+1$ copies at the shorter scale.

Indeed, if $N(v)>B_A(v;N)$, an unblocked occurrence extends through the relevant periodic interval. Its $k+1$ period-spaced prefixes give the desired unblocked copies of $w$. Otherwise all actual copies are blocked, and

$$B_A(v;N)=N(v)\ge m(v)>B_A(v;m).$$

Some longer bracket word must therefore have $N(r)>m(r)$. One placement of $v$ within this extra copy of $r$ supplies $k+1$ placements of $w$. Their multiplicities give $B_A(w;N)-B_A(w;m)\ge k+1$. Induction on decreasing word length has already validated the bounds for these longer words. Thus the algorithm does not assume that the trigger itself transfers unchanged to the optimum. This is the key justification in “Forced occurrence counts.” (OpenAI, 2026)

The two budgets behind the approximation factor

For a word $s$, put $u(s)=m(s)-{\sum }_{c}m(cs)$ and $d(s)=m(s)-{\sum }_{c}m(sc)$, with the sums over alphabet letters. These nonnegative integers specify the upward and downward edge multiplicities of the base substring graph. The extension inequalities ensure nonnegativity; subtracting the two extension sums in either order gives the same degree balance. The upward cost is $W={\sum }_{c}m(c)$, which is at most the optimum superstring length because each letter occurrence must be counted.

Balance alone gives closed components, not a single superstring. The layer decomposition assigns each periodic layer of least period $p$ a connection budget $p$. These budgets sum to $W$. Every connecting operation is itself a closed walk, so adding it preserves balance. Once all components meet the empty word, an Euler tour spells a common superstring of length at most $W+W\le 2\mathrm{OPT}$. Consequently the difficult connection theorem is an amortized statement about the same initial budget; it cannot charge a fresh period every time two layers interact.

Opening dependency cycles without paying twice

After the group procedure, each unresolved block of $k$ layers of period $p$ has one planned outgoing link and total budget $kp$. A functional graph of these plans can contain directed cycles. The “one free period” lemma joins a block internally for at most $(k-1)p$, leaving $p$ unused if its outgoing link is omitted.

A second lemma chooses, on a cycle, a source block whose distinguished forward rotation is lexicographically maximal. If its target has period $q$, the planned link can be realized with a contact word of length at most $q$. The proof compares the two periodic alignments: agreement for $q$ consecutive positions would contradict maximality of the distinguished rotation. It therefore finds a short suffix of a genuine overlap record. Descending to this suffix and then growing along an actual top-layer word touches every required layer. All intermediate words remain vertices of the substring graph; arbitrary invented periodic words would not suffice.

For a cycle containing at least two blocks, retain this selected link and omit the target block’s outgoing link. Internal joining of the target frees its budget $q$, exactly enough to connect the short contact to the empty word. The retained links now join the whole cycle into one rooted component. A one-block cycle is handled separately: its different alignment already gives a contact shorter than its own period. Distinct cycles use disjoint block budgets, and the incoming trees can then attach toward their rooted cycles. “Opening cycles of planned links” supplies this precise source-target bookkeeping. (OpenAI, 2026)

See Also

• Edit distance also studies explicitly represented strings, but permits insertions, deletions, and substitutions between a supplied pair.
• Deletion-trace reconstruction asks for an unknown source string from subsequences, unlike the contiguous containment requirement here.

🏷️ Manuscripts and verification scope

• A Polynomial-Time 2-Approximation for Shortest Common Superstring — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope concerns a deterministic polynomial-time construction for all explicitly encoded finite string lists. Its approximation ratio uses symbol length, while runtime is measured in input bits. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A Polynomial-Time 2-Approximation for Shortest Common Superstring.