==== TABLE OF CONTENTS ====
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//01-introduction.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//02-counts.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//03-layers.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//04-connections.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//05-processing.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//06-cycles.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//07-algorithm.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//collective.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//cycles.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//layers.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//paper.tex
A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//references.tex
===========================
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//01-introduction.tex ====
\section{Introduction}\label{sec:intro}
In the \emph{shortest common superstring problem}, the input is a finite collection $\mathcal S$ of finite strings, and the task is to find a shortest string containing every member of $\mathcal S$ as a contiguous substring. Write $\OPT(\mathcal S)$ for its minimum possible length. The strings are represented explicitly, with encoded symbol labels and string boundaries. Let $N$ be the total bit length of this representation and $L$ the sum of the string lengths measured in symbols. Each symbol and boundary occupies at least one bit, so $L,|\mathcal S|\le N$; operations on symbol labels are charged for their encoded lengths.
\begin{theorem}\label{thm:main}
There is a deterministic algorithm, polynomial in the total encoded input size, that on every finite collection $\mathcal S$ of explicitly represented ordinary strings outputs a common superstring $T$ satisfying
\[
\len{T}\le 2\OPT(\mathcal S).
\]
\end{theorem}
\paragraph{History and significance.}
Tarhio and Ukkonen proposed the factor-$2$ conjecture for the maximum-overlap Greedy procedure~\cite{tarhio1988}. Blum, Jiang, Li, Tromp, and Yannakakis established a polynomial-time $3$-approximation~\cite{blum1994}; Sweedyk later obtained a $5/2$ guarantee~\cite{sweedyk1999}. Subsequent guarantees include $2+11/23$ due to Mucha~\cite{mucha2013} and $(14+\sqrt{67})/9<2.466$ due to Englert, Matsakis, and Vesel\'{y}~\cite{emv2023}. An August 2026 preprint of Chukhin, Kulikov, Mihajlin, and Smal reports a $7/3$-approximation~\cite{cycle2026}. \Cref{thm:main} answers affirmatively the question of whether a polynomial-time factor-$2$ approximation exists.
Many earlier approximation algorithms use the distance graph on the input strings, whose edge costs are the lengths of prefixes left after maximum suffix--prefix overlap. A minimum-weight cycle cover gives a computable lower bound, but its cycles must then be opened and joined while controlling the extra length~\cite{blum1994}. Breslauer, Jiang, and Jiang use rotations of periodic strings to control overlaps~\cite{breslauer1997}; Mucha sharpens this analysis through lexicographically extremal primitive rotations~\cite{mucha2013}. These provide conceptual precedents for the periodic comparisons below; our lower bound and the graph to which we apply them are different.
Our graph representation comes from another formulation. Golovnev, Kulikov, and Mihajlin introduced a hierarchical graph in the bounded-length setting~\cite{golovnev2014}, and the Collapsing framework developed its all-substrings form~\cite{collapsing2020}. In this graph, appending or deleting a letter gives an edge between substring vertices, and a superstring is represented by a closed walk visiting the required strings. The separation between a balanced graph and the operations that connect it also appears in the hierarchical cycle-cover discussion of that framework~\cite[revised version, Section~7.2]{collapsing2020}. We use this representation to turn forced occurrence counts into a balanced graph and then connect it within the same cost bound.
The factor-$2$ question has also motivated conjectures about specific procedures. The classical Greedy conjecture concerns repeatedly merging a pair of maximum overlap, while the Collapsing conjecture concerns a prescribed normalization of doubled hierarchical-graph walks~\cite{collapsing2020}. A September 2026 preprint of Shibata reports a counterexample to the Greedy conjecture, with worst-case ratio at least $9/4$~\cite{greedy2026}. Our theorem concerns the algorithm proved here; neither of those prescribed procedures is assumed to attain factor $2$.
\paragraph{Proof overview.}
The vertices of our hierarchical graph are all substrings of the inputs, including the empty word. An up edge appends a letter and costs one; a down edge deletes the first letter and costs zero. A balanced multiset of edges has equal incoming and outgoing degree at each vertex. If its support is connected and visits the empty word and every required string, an Euler tour spells a common superstring whose length is its up-edge cost.
We first construct integer counts $m(s)$ no larger than the number of occurrences of $s$ in any common superstring. Their one-letter sum $W$ is therefore a lower bound on the optimum. Counts for longer words constrain those of their prefixes and suffixes. A further rule handles periodic words. Relative to a fixed periodic text, a bracketing word consists of a matching interval with a mismatching letter at each end. When the assigned count of a long word exceeds the contribution of its bracketing words, a prefix shorter by $k$ periods must have count at least $k+1$ above its own bracketing contribution. The resulting counts determine a balanced, possibly disconnected graph of cost $W$.
Next decompose that graph into closed walks. The letters appended during a walk, repeated in both directions, form a periodic text; each visited vertex is a finite interval of that text. Walks with the same periodic text can be rearranged, preserving every edge, into ordered walks that each traverse one least period. We call these walks \emph{layers}. A layer of period $p$ has cost $p$ and receives a further budget $p$, so all additional budgets together equal $W$. In the remaining case of the connection procedure, the count rule forces a shorter word to occur on a layer with a different aligned text. A visited interval agreeing with both texts gives an actual graph vertex at which to attach a connection.
The final task is to arrange these connections without spending a budget twice. Some closed walks connect their source layers to a target using only the source budgets. Others require a contribution from the target, but these requests go only to a strictly larger period and are handled together when that period is processed. For each connection paid for only by its source layers, those layers can instead be joined internally while saving one period of budget. The remaining source-funded connections may form directed cycles. On each cycle, a maximal lexicographic rotation yields a contact word no longer than the target's period. Omitting that target's outgoing connection and joining its layers internally therefore pays for a round trip from the contact to the empty word. This connects the base graph at additional cost at most $W$ and completes the factor-$2$ bound.
\paragraph{Organization.}
\Cref{sec:counts} constructs the counts and their balanced graph. \Cref{sec:layers} develops the layer representation and the periodicity facts. \Cref{sec:connections} gives the connection operations, \Cref{sec:processing} processes groups of equal primitive text, and \Cref{sec:cycles} resolves the remaining cycles. \Cref{sec:algorithm} proves polynomial time and extracts the output string.
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//01-introduction.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//02-counts.tex ====
\section{Forced occurrence counts}\label{sec:counts}
Delete the empty string, duplicates, and every input string contained in another input string. This preserves the set of common superstrings and its optimum. If nothing remains, output the empty string. Henceforth the remaining instance is nonempty. Let $\Sigma$ be its alphabet and let $V$ be the set of its distinct substrings, including the empty word $\eps$. Thus $V$ is closed under taking substrings, $\len V=O(L^2)$, and every required string is maximal under extension in $V$.
For a finite string $s$, indices start at zero. Write $s[i:j)$ for its substring on the indicated half-open interval. A \emph{periodic text} is a map $A:\ZZ\to\Sigma$ with $A(i+p)=A(i)$ for some positive integer $p$. The period need not be least unless this is specified.
\subsection{Blocking an occurrence}
Fix a text $A$ and a nonempty $s$ such that $A[0:\len s)=s$. For $r\in V$, let $b_{A,s}(r)$ be the number of integers $j$ with
\[
1\le j,\qquad j+\len s\le\len r-1,
\]
for which $r[j:j+\len s)=s$ and
\begin{align}
r(h)&=A(h-j) &&(1\le h\le\len r-2),\label{eq:block-interior}\\
r(0)&\ne A(-j),\qquad
r(\len r-1)\ne A(\len r-1-j).\label{eq:block-ends}
\end{align}
The word $r$ consists of a matching interval bracketed by one mismatching letter on each side of the specified $s$. Define the linear functional
\begin{equation}\label{eq:block-functional}
B_A(s;m)=\sum_{r\in V\setminus\{\eps\}}b_{A,s}(r)m(r).
\end{equation}
Only words with $\len r\ge\len s+2$ contribute.
If an occurrence of $s$ in a finite word $T$ is aligned with $A$, its nearest mismatch on each side, when both exist, determines a unique bracketing word $r$. Call the occurrence \emph{blocked} if this word belongs to $V$, and \emph{unblocked} otherwise. In particular, an occurrence with no mismatch on one side is unblocked. When $N_T(r)$ denotes the number of occurrences of $r$ in $T$, uniqueness of the nearest mismatches gives
\begin{equation}\label{eq:block-count}
B_A(s;N_T)=\#\{\text{blocked occurrences of }s\text{ in }T\}
\le N_T(s).
\end{equation}
The multiplicity in $b_{A,s}(r)$ is necessary: a single occurrence of $r$ may bracket several distinct occurrences of $s$.
\subsection{The rules}
Construct nonnegative integers $m(s)$ for $s\in V\setminus\{\eps\}$ in decreasing order of length. Missing words have count zero. At each $s$, take the smallest integer satisfying
\begin{equation}\label{eq:extension-rules}
m(s)\ge\sum_{c\in\Sigma}m(cs),\qquad
m(s)\ge\sum_{c\in\Sigma}m(sc),
\end{equation}
and $m(s)\ge1$ if $s$ is required. Impose also the following rules for every period-$p$ text $A$, every $v=A[0:\len v)\in V$, and every nonempty prefix $w$ of $v$ with $\len v=\len w+kp$, $k\ge1$:
\begin{equation}\label{eq:period-rule}
m(v)>B_A(v;m)
\quad\Longrightarrow\quad
m(w)\ge B_A(w;m)+k+1.
\end{equation}
All quantities constraining $m(w)$ have already been determined: $v$ is longer than $w$, and every term of either blocking functional is longer than its inner word. Thus these are explicit lower bounds in a descending recursion.
The apparent range over periodic texts is finite for this purpose. In a rule, $p<\len v$, and $A$ is determined by the first $p$ letters of $v$. One may enumerate $v$, $p$, and $k$, check that repetition of the first $p$ letters agrees with $v$, and retain the admissible rules. This includes nonleast periods.
\begin{lemma}[Occurrence lower bound]\label{lem:counts}
For every common superstring $T$ and every nonempty $s\in V$,
\[
m(s)\le N_T(s).
\]
Consequently, for
\begin{equation}\label{eq:W}
W=\sum_{c\in\Sigma}m(c),
\end{equation}
we have $W\le\OPT(\mathcal S)$ and $m(s)\le L$.
\end{lemma}
\begin{proof}
Fix $T$ and abbreviate $N_T$ to $N$. Induct on decreasing word length. The counts $N$ satisfy \eqref{eq:extension-rules}: occurrences with different preceding letters are disjoint, as are those with different following letters. They also satisfy the requirement for input strings.
Consider a rule \eqref{eq:period-rule} constraining $m(w)$ whose trigger holds. If $N(v)>B_A(v;N)$, choose an unblocked occurrence of $v$. It contains occurrences of $w$ at offsets $0,p,\ldots,kp$. Each is unblocked. Indeed, because $v$ matches $A$ and the offsets are multiples of $p$, a nearest mismatch bracketing one of these shorter occurrences must lie outside $v$. A blocking word in $V$ for it would therefore also block the chosen occurrence of $v$. The $k+1$ shorter occurrences are distinct, so \eqref{eq:block-count} and induction give
\[
N(w)\ge B_A(w;N)+k+1\ge B_A(w;m)+k+1.
\]
In the other case, \eqref{eq:block-count} implies
\[
B_A(v;N)=N(v)\ge m(v)>B_A(v;m).
\]
Every difference $N(r)-m(r)$ in this blocking sum is nonnegative by induction. Some contributing word $r$ therefore has $N(r)-m(r)\ge1$. Choose one of its counted placements of $v$. The $k+1$ period-spaced prefixes $w$ within that placement give distinct counted placements of $w$ in the same $r$. Hence $b_{A,w}(r)\ge k+1$. All other terms in the difference of blocking sums are nonnegative, and therefore
\[
N(w)\ge B_A(w;N)\ge B_A(w;m)+k+1.
\]
Every lower bound used to define $m(w)$ is thus at most $N(w)$, completing the induction.
For an optimal $T$, summing over one-letter words gives $W\le\len T$. For a concatenation of the inputs, $N_T(s)\le\len T\le L$, giving the second assertion.
\end{proof}
\subsection{The balanced base graph}
The \emph{hierarchical graph} on $V$ has, for each nonempty $s$, an up edge $\pref(s)\to s$ and a down edge $s\to\suf(s)$, where $\pref$ deletes the last letter and $\suf$ deletes the first. The up edge has cost one and the down edge cost zero. Golovnev, Kulikov, and Mihajlin introduced a hierarchical graph for bounded-length inputs~\cite{golovnev2014}; the all-substrings form and these edge costs appear in the Collapsing framework~\cite[Section~2.2]{collapsing2020}. We give every graph property needed here directly.
Give the two edges at $s$ multiplicities
\begin{equation}\label{eq:base-multiplicities}
u(s)=m(s)-\sum_c m(cs),\qquad
d(s)=m(s)-\sum_c m(sc),
\end{equation}
respectively. Write $G$ for the resulting directed multigraph, omitting unused edges and vertices.
\begin{lemma}\label{lem:base}
The graph $G$ is balanced, contains every required string as a used vertex, and has $W$ up edges and $W$ down edges, counted with multiplicity.
\end{lemma}
\begin{proof}
The multiplicities are nonnegative by \eqref{eq:extension-rules}. At a nonempty $s$, the incoming and outgoing degrees are, respectively,
\[
u(s)+\sum_c d(cs),\qquad d(s)+\sum_c u(sc),
\]
and both simplify to $m(s)-\sum_{c,d}m(csd)$. Balance at $\eps$ follows by summing degrees over the other vertices. Telescoping \eqref{eq:base-multiplicities} over all nonempty words gives $\sum_s u(s)=\sum_s d(s)=\sum_c m(c)=W$. Finally, a remaining required string has no proper extension in $V$, so both its edge multiplicities equal its positive count.
\end{proof}
For example, suppose the only required word is $a^h$, with $h\ge2$. The extension inequalities alone allow $m(a^j)=1$ for $1\le j\le h$. Their base graph is only the two-edge walk between $a^{h-1}$ and $a^h$, with cost $1$. In the constant text $a$, every blocking functional is zero. Applying the period-one rule to $v=a^h$ and $w=a^j$ forces $m(a^j)\ge h-j+1$ for $1\le jS(j+q)$. Let $U$ repeat the first $q$ letters of $S$. The equalities $S(i)=S(i+q)$ for $iS(j+q),
\]
so $U>S$. If $D$ agreed on the first $q$ letters, its forward word there would be $U$, contrary to the hypothesis on its rotations.
\end{proof}
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//03-layers.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//04-connections.tex ====
\section{Connection operations}\label{sec:connections}
We now construct closed walks that touch existing layers at a cost charged to specified period budgets. We first give joins paid for entirely by the layers being attached, then an operation that also spends the receiving layer's budget. Each cross-text contact uses an actual word common to the two alignments; the band operation below is restricted to layers of one primitive-text group.
A collection of layers and added walks is \emph{rooted} if its graph support is connected to $\eps$. Connectivity is in the underlying undirected graph; every edge multiset we use is balanced. To \emph{touch} a layer means to share at least one of its graph vertices. Since all base edges remain, touching any vertex of a layer connects to every vertex of that layer.
\subsection{Following ordered windows}
\begin{lemma}[Ordered windows]\label{lem:ordered-windows}
Let $[a,b)$ and $[c,d)$ be windows in a common text over $\Sigma$, each spelling a word in $V$. If $a\le c$ and $b\le d$, there is a hierarchical-graph walk from the first word to the second of cost $d-b$. It visits a word of length at most $\max(0,b-c)$.
Consequently an ordered list of windows, with both starts and ends nondecreasing, can be followed at cost equal to the total increase in its ends. If its last window is a translate of the first by $h$ in a text of period dividing $h$, this is a closed walk of cost $h$.
\end{lemma}
\begin{proof}
If $c\le b$, delete the first $c-a$ letters, reaching $[c,b)$, and append through $d$. The words on the down path are suffixes of the first word; those on the up path are prefixes of the second. All belong to $V$, and the up cost is $d-b$.
If $c>b$, delete to the empty word. For each letter in the gap $[b,c)$, take an up step to that letter and a down step back to empty. Then build $[c,d)$. Single-letter words in the gap belong to $V$ because the text uses only $\Sigma$. The cost is $(c-b)+(d-c)=d-b$. Concatenating these constructions proves the assertions about lists and translates.
\end{proof}
In particular, a round trip from a vertex $s$ to $\eps$ and back costs $\len s$. Prescribed windows, rather than all intervals they sweep across, must belong to $V$; \Cref{lem:ordered-windows} supplies the intermediate vertices.
\begin{lemma}[Joining an ordered band]\label{lem:band}
Consider $k$ ordered layers from one primitive-text group of period $p$. At a start $t$, let $H$ be the top layer's first end and $E$ the bottom layer's last end. If $h$ is a nonnegative multiple of $p$ and $H-E\le h$, the layers can be joined together by a closed walk of cost at most $h$.
\end{lemma}
\begin{proof}
If $E\ge H$, every layer contains $[t,E)$: its first end is at most $H$ and its last end is at least $E$. No added walk is needed. Otherwise grow at start $t$ from end $E$ to $H$. Every layer has a vertical range intersecting $[E,H]$, so the growth touches them all. The endpoints are actual bottom and top vertices, and every intermediate word is a prefix of the top vertex. Finish by following to $[t+h,E+h)$, which is a period translate of the starting window. Since $E+h\ge H$, \Cref{lem:ordered-windows} gives a closed walk of cost $h$.
\end{proof}
\subsection{A collective outgoing link}
We call a chosen actual layer window, together with an alignment to a specified periodic text agreeing throughout it, a \emph{record}. A record on a receiving layer provides a vertex at which to attach layers following the other text. An ordinary \emph{link} spends only the attached layers' budgets. The following link attaches $k$ source layers at combined cost $kp$; it can therefore be planned without reserving any budget of the receiving layer. \Cref{fig:collective} illustrates its construction.
\begin{lemma}[Collective link]\label{lem:collective}
Consider $k$ ordered layers with a common period-$p$ text $A$, and put $K=kp$. Let $R=[a,b)$ spell a word in $V$ agreeing with $A$. Let $r_H=f_H(a)$ be the top layer's first end and $r_L=l_L(a)$ the bottom layer's last end. If
\begin{equation}\label{eq:collective-conditions}
r_H\le b+K,\qquad r_H-r_L\le K,
\qquad r_L+K\ge b,
\end{equation}
there is a cost-$K$ closed walk based at the word of $R$ that touches all $k$ layers.
\end{lemma}
\begin{proof}
Put $Y=\max(b,r_H)$. Then $b\le Y\le b+K$. For each constituent layer $i$,
\[
f_i(a)\le Y\le l_i(a)+K=l_i(a+K).
\]
Consequently its path meets height $Y$ at a start in $[a,a+K]$. More explicitly, choose the least such start $x_i$ with $z_i(x_i)\ge Y$. If $x_i=a$, then $z_i(a-1)=f_i(a)\le Y$; otherwise minimality gives $z_i(x_i-1)a_l$, their overlap is an agreement interval between two distinct child texts, so
\begin{equation}\label{eq:child-overlap}
b_i-a_la_j+p_j$, so the final translated window $[T,e_0+q)$ has end greater than $T+p_j$. The whole list is therefore ordered. Its closed excursion costs $q$ by \Cref{lem:ordered-windows}. On its final transition it reaches a vertex of length less than $p_j$. If there are no later records, the same conclusion follows using $b_jt+np,
\qquad l_{\mathrm{base}}(t)1$, reaching $k$ means that at least $k$ layers qualified at the previous threshold $H-(k-1)p$. Pointwise ordering gives \eqref{eq:sharp-band}.
For any $x$, choose its translate $x'$ modulo $p$ in $(t-p,t]$. Then
\[
f_H(x')\le H,
\qquad l_{L_*}(x')\ge l_{L_*}(t)-p.
\]
Their difference is invariant under period translation, proving \eqref{eq:wide-band}.
By \eqref{eq:hard-case}, $H-K>t$, so $w$ is nonempty. Each primitive layer has exactly one position residue whose full-text alignment agrees with $A$: the shifts preserving its text are exactly the multiples of $p$. At that alignment, $w$ is recorded exactly when $l_i(t)\ge H-K$. At most $k$ layers satisfy this inequality when the test stops. Other primitive-text groups have no identical full-text alignment.
\end{proof}
Apply the count rule \eqref{eq:period-rule}, with origin shifted to $t$, to the actual vertex word
\[
v=A[t:H),\qquad w=A[t:H-K).
\]
The top layer records an unblocked occurrence of $v$ in its own text. By \eqref{eq:unblocked-count}, the trigger holds, and the rule gives at least $k+1$ unblocked occurrences of $w$. \Cref{lem:choose-k} leaves at least one on a layer $D$ whose aligned text differs from $A$. A different phase of this same group is allowed.
Choose one such occurrence. \Cref{lem:matching-window} gives an actual window $R=[a,b)$ on $D$, agreeing with $A$ throughout and containing the specified interval $[t,H-K)$. Let $q$ be the least period of $D$. Thus
\begin{equation}\label{eq:chosen-record}
a\le t,
\qquad b\ge H-K,
\qquad b-a2p$; combining this with $b-ap$. The recipient group will therefore be processed later.
\end{enumerate}
This verifies the promised hypotheses for incoming requests. They always go to strictly larger periods, and a child group uses just one record on one recipient layer, even if several of its layers request there. Ordinary planned links consume no recipient budget. When a recipient is processed, its own budget and all reserved requester budgets are available. After \Cref{lem:host} is applied, those layers are rooted and do not enter any outgoing block.
\begin{proposition}\label{prop:partition}
After all groups have been processed, every layer is either marked rooted or belongs to exactly one outgoing block. These two classes are disjoint. Each block consists of layers from one primitive-text group and targets a single actual layer. Its total budget remains reserved for its planned link. A collective block of $k$ layers and period $p$ also satisfies \eqref{eq:sharp-band} at its distinguished position; an individual block consists of one layer.
\end{proposition}
\begin{proof}
Incoming requests use disjoint requester budgets, and each recipient budget is spent only when its group is processed. The baseline step uses only budgets of remaining lower layers. The easy upper-layer branches use at most the combined budgets of the upper layers and finish them. In the remaining branch, the collective case and the individual cases partition those upper layers. Each request is eventually fulfilled, because its recipient is processed later. The layers not marked rooted by a direct operation or a fulfilled request are precisely the outgoing blocks. Their links have only been planned, so their budgets are unspent. The asserted inequality for collective blocks is \eqref{eq:sharp-band}.
\end{proof}
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//05-processing.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//06-cycles.tex ====
\section{Opening cycles of planned links}\label{sec:cycles}
It remains to execute the plans in \Cref{prop:partition}. Regard a block as one node and map its target layer to the block containing that layer, or to a rooted sink if the target is marked rooted. Each nonsink node has exactly one outgoing edge. A component therefore reaches a rooted sink or contains one directed cycle. Additional graph intersections between layers can only help; the following argument does not need them to be recorded by this bookkeeping graph.
\begin{lemma}[One free period]\label{lem:free-period}
A block of $k$ layers and period $p$ can be joined internally, in place of its outgoing link, for cost at most $(k-1)p$. Thus this replacement leaves at least $p$ of its total budget available.
\end{lemma}
\begin{proof}
For an individual block, or any block with $k=1$, no internal addition is needed. For a collective block, \eqref{eq:sharp-band} gives
\[
f_H(t)-l_{L_*}(t)\le(k-1)p.
\]
Apply \Cref{lem:band} with $h=(k-1)p$.
\end{proof}
\begin{lemma}[A short contact on a maximal link]\label{lem:cycle-contact}
On a directed cycle of blocks, choose a block whose group's distinguished forward rotation is lexicographically greatest. If its target layer has period $q$, its planned outgoing link can be realized within its reserved budget so that the resulting connected piece contains a vertex of length at most $q$.
\end{lemma}
\begin{proof}
If the plan is an individual link, \eqref{eq:single-short} already gives the contact. For a collective plan with $k$ source layers of period $p$, put $K=kp$. Recall that $t$ is distinguished, $H=f_H(t)$, and the target record $R=[a,b)$ agrees with the source text and satisfies
\[
a\le tb-x$. These first ends are all at most $H$: they are no greater than the top first end at $x$, which is at most its first end at $t$. Let $F=f_H(x)$. Then $b=latex,
layer/.style={line width=.65pt,draw=black!55},
connection/.style={line width=1.35pt,draw=blue!45!black},
guide/.style={draw=black!25,densely dotted,line width=.45pt}]
\begin{scope}[x=.64cm,y=.25cm]
\node[anchor=west,font=\small\bfseries] at (-.75,24.2)
{A collective link through ordered layers};
\draw[->,black!65] (-.75,3) -- (10.05,3) node[right] {start};
\draw[->,black!65] (-.75,3) -- (-.75,21.7) node[above] {end};
\draw[guide] (0,3) -- (0,12);
\draw[guide] (9,3) -- (9,12);
\draw[guide] (-.75,12) -- (0,12);
\node[left,inner sep=3pt] at (-.75,12) {$Y=b$};
\node[below,inner sep=3pt] at (0,3) {$a$};
\node[below,inner sep=3pt] at (9,3) {$a+K$};
\foreach \c/\shade in {11/75,8/55,5/40} {
\draw[layer,draw=black!\shade] (-.55,\c-1) -- (0,\c-1);
\foreach \j in {0,...,8} {
\draw[layer,draw=black!\shade]
(\j,\j+\c-1) -- (\j,\j+\c) -- (\j+1,\j+\c);
}
\draw[layer,draw=black!\shade]
(9,9+\c-1) -- (9,9+\c) -- (9.55,9+\c);
}
\draw[connection,->] (0,12) -- (9,12);
\draw[connection,->] (9,12) -- (9,21);
\foreach \j/\name in {1/top,4/middle,7/bottom} {
\fill[blue!45!black] (\j,12) circle (2.1pt);
\node[above,inner sep=4pt,font=\scriptsize] at (\j,12) {\name};
}
\filldraw[connection,fill=white,line width=.9pt] (0,12) circle (2.4pt);
\node[above left,inner sep=4pt] at (0,12) {$R$};
\filldraw[connection,fill=white,line width=.9pt] (9,21) circle (2.4pt);
\node[above left,inner sep=4pt] at (9,21) {$R+K$};
\draw[<->,black!65] (10.1,12) -- (10.1,21)
node[midway,right,inner sep=4pt,align=left,font=\scriptsize]
{$K$ up steps};
\draw[<->,black!65] (0,.55) -- (9,.55)
node[midway,above,inner sep=3pt,font=\scriptsize] {$K=kp$};
\end{scope}
\end{tikzpicture}
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//collective.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//cycles.tex ====
\begin{tikzpicture}[font=\small,>=latex,
block/.style={draw=black!60,rounded corners=2pt,fill=black!3,
minimum width=3.05cm,minimum height=1.15cm,align=center,inner sep=5pt},
link/.style={->,draw=black!65,line width=.8pt},
selected/.style={->,draw=blue!45!black,line width=1.4pt}]
\node[block] (source) at (0,2.8)
{Selected source\\$k$ layers, period $p$};
\node[block] (target) at (7.8,2.8)
{Target block\\$\ell$ layers, period $q$};
\node[block] (next) at (7.8,0)
{Next block};
\node[block] (last) at (0,0)
{Another block};
\draw[selected] (source.east) -- (target.west)
node[midway,below=7pt,align=center,font=\scriptsize]
{retain selected link\\cost at most $kp$};
\draw[link] (next.west) -- (last.east);
\draw[link] (last.north) -- (source.south);
\draw[->,draw=black!35,densely dashed,line width=.8pt]
(target.south) -- (next.north);
\draw[black!70,line width=1.1pt] (7.59,1.21) -- (8.01,1.63);
\draw[black!70,line width=1.1pt] (7.59,1.63) -- (8.01,1.21);
\node[anchor=west,align=left,font=\scriptsize] at (8.17,1.42)
{omit target's\\outgoing link};
\coordinate (contact) at (3.9,2.8);
\fill[blue!45!black] (contact) circle (2.4pt);
\node[anchor=south east,inner sep=5pt] at (contact) {$s$, $|s|\le q$};
\node[circle,draw=blue!45!black,fill=white,line width=.9pt,
minimum size=.48cm,inner sep=2pt] (root) at (3.9,4.65) {$\varepsilon$};
\node[above=3pt,font=\scriptsize] at (root.north) {empty word};
\draw[<->,draw=blue!45!black,line width=1.05pt]
(contact) -- (root.south)
node[midway,right=5pt,align=left,font=\scriptsize]
{round trip\\cost at most $q$};
\node[above=6pt,align=center,font=\scriptsize] at (source.north)
{greatest distinguished\\rotation on the cycle};
\node[anchor=north,align=center] at (3.9,-.93)
{Target budget $\ell q$: internal joining costs at most $(\ell-1)q$;\\
at least $q$ remains to root the short contact.};
\end{tikzpicture}
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//cycles.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//layers.tex ====
\begin{tikzpicture}[font=\small,>=latex,
layer/.style={line width=.65pt,draw=black!55},
connection/.style={line width=1.35pt,draw=blue!45!black},
guide/.style={draw=black!25,densely dotted,line width=.45pt}]
\begin{scope}[shift={(0,.75)}]
\node[anchor=west,font=\small\bfseries] at (0,5.3) {A window layer};
\draw[->,black!65] (0,0) -- (3.9,0) node[below] {start $x$};
\draw[->,black!65] (0,0) -- (0,4.5) node[above] {end $e$};
\draw[layer] (.55,1.25) -- (1.6,1.25) -- (1.6,3.05)
-- (3.1,3.05) -- (3.1,4.05) -- (3.75,4.05);
\fill[black!65] (1.6,1.25) circle (1.6pt);
\fill[black!65] (1.6,3.05) circle (1.6pt);
\node[anchor=north east,inner sep=3pt] at (1.6,1.25) {$f_i(x)$};
\node[anchor=south east,inner sep=3pt] at (1.6,3.05) {$l_i(x)$};
\draw[connection,->] (1.25,1.8) -- (1.25,2.55)
node[midway,left,inner sep=3pt] {up};
\draw[connection,->] (1.95,3.4) -- (2.8,3.4)
node[midway,above,inner sep=2pt] {down};
\fill[blue!45!black] (1.6,2.1) circle (2pt);
\node[anchor=west,inner sep=5pt] at (1.6,2.1) {$[x,e)$};
\draw[guide] (1.6,0) -- (1.6,1.17);
\node[below,inner sep=3pt] at (1.6,0) {$x$};
\node[anchor=north,align=center,font=\scriptsize] at (1.8,-.55)
{$f_i(x)=z_i(x-1)$,\quad $l_i(x)=z_i(x)$};
\end{scope}
\end{tikzpicture}
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//layers.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//paper.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{booktabs}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\usepackage[nameinlink,noabbrev,capitalise]{cleveref}
\pdfinfoomitdate=1
\pdftrailerid{}
\pdfsuppressptexinfo=15
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\OPT}{\operatorname{OPT}}
\newcommand{\pref}{\operatorname{pref}}
\newcommand{\suf}{\operatorname{suf}}
\newcommand{\len}[1]{\lvert #1\rvert}
\newcommand{\eps}{\varepsilon}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\NN}{\mathbb Z_{\ge0}}
\newcommand{\cost}{\operatorname{cost}}
\setlist{itemsep=3pt,topsep=5pt}
\emergencystretch=1em
\title{A Polynomial-Time 2-Approximation for\protect\\ Shortest Common Superstring}
\author{OpenAI}
\date{September 24, 2026}
\hypersetup{pdftitle={A Polynomial-Time 2-Approximation for Shortest Common Superstring},pdfauthor={OpenAI}}
\begin{document}
\maketitle
\begin{abstract}
We 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.
\end{abstract}
\input{sections/01-introduction}
\input{sections/02-counts}
\input{sections/03-layers}
\input{sections/04-connections}
\input{sections/05-processing}
\input{sections/06-cycles}
\input{sections/07-algorithm}
\input{references}
\end{document}
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//paper.tex ====
==== BEGIN A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//references.tex ====
\begingroup\small
\begin{thebibliography}{99}
\bibitem{blum1994}
Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis.
\newblock Linear approximation of shortest superstrings.
\newblock \emph{Journal of the ACM}, 41(4):630--647, 1994.
\newblock \href{https://doi.org/10.1145/179812.179818}{doi:10.1145/179812.179818}.
\bibitem{breslauer1997}
Dany Breslauer, Tao Jiang, and Zhigen Jiang.
\newblock Rotations of periodic strings and short superstrings.
\newblock \emph{Journal of Algorithms}, 24(2):340--353, 1997.
\newblock \href{https://doi.org/10.1006/jagm.1997.0861}{doi:10.1006/jagm.1997.0861}.
\bibitem{cycle2026}
Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Alexander Smal.
\newblock A tight cycle-cover inequality for shortest common superstring.
\newblock \emph{Electronic Colloquium on Computational Complexity},
Report TR26-157, August 2026. Preprint.
\newblock \url{https://eccc.weizmann.ac.il/report/2026/157/}.
\bibitem{emv2023}
Matthias Englert, Nicolaos Matsakis, and Pavel Vesel\'{y}.
\newblock Approximation guarantees for shortest superstrings: Simpler and better.
\newblock In \emph{34th International Symposium on Algorithms and
Computation (ISAAC 2023)}, volume 283 of \emph{LIPIcs}, pages 29:1--29:17, 2023.
\newblock \href{https://doi.org/10.4230/LIPIcs.ISAAC.2023.29}{doi:10.4230/LIPIcs.ISAAC.2023.29}.
\bibitem{finewilf}
N. J. Fine and H. S. Wilf.
\newblock Uniqueness theorems for periodic functions.
\newblock \emph{Proceedings of the American Mathematical Society}, 16:109--114, 1965.
\newblock \href{https://doi.org/10.1090/S0002-9939-1965-0174934-9}{doi:10.1090/S0002-9939-1965-0174934-9}.
\bibitem{collapsing2020}
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov,
Ivan Mihajlin, and Maksim Nikolaev.
\newblock Collapsing superstring conjecture.
\newblock In \emph{APPROX/RANDOM 2019}, volume 145 of \emph{LIPIcs},
article 26, 2019.
\newblock \href{https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.26}{doi:10.4230/LIPIcs.APPROX-RANDOM.2019.26};
\href{https://arxiv.org/abs/1809.08669v3}{revised arXiv version, 4 June 2020}.
\bibitem{golovnev2014}
Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin.
\newblock Solving {SCS} for bounded length strings in fewer than $2^n$ steps.
\newblock \emph{Information Processing Letters}, 114(8):421--425, 2014.
\newblock \href{https://doi.org/10.1016/j.ipl.2014.03.004}{doi:10.1016/j.ipl.2014.03.004}.
\bibitem{mucha2013}
Marcin Mucha.
\newblock Lyndon words and short superstrings.
\newblock In \emph{Proceedings of SODA 2013}, pages 958--972, 2013.
\newblock \href{https://doi.org/10.1137/1.9781611973105.69}{doi:10.1137/1.9781611973105.69}.
\bibitem{greedy2026}
Hiroki Shibata.
\newblock Disproving the greedy superstring conjecture.
\newblock \href{https://arxiv.org/abs/2609.01365v1}{arXiv:2609.01365v1},
1 September 2026. Preprint.
\bibitem{sweedyk1999}
Z. Sweedyk.
\newblock A 2.5-approximation algorithm for shortest superstring.
\newblock \emph{SIAM Journal on Computing}, 29(3):954--986, 1999.
\newblock \href{https://doi.org/10.1137/S0097539796324661}{doi:10.1137/S0097539796324661}.
\bibitem{tarhio1988}
Jorma Tarhio and Esko Ukkonen.
\newblock A greedy approximation algorithm for constructing shortest common superstrings.
\newblock \emph{Theoretical Computer Science}, 57(1):131--145, 1988.
\newblock \href{https://doi.org/10.1016/0304-3975(88)90167-3}{doi:10.1016/0304-3975(88)90167-3}.
\end{thebibliography}
\endgroup
==== END A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring//references.tex ====