Greedy superstring conjecture

Let $S$ be a finite set of finite strings. For strings $x$ and $y$ , let $\operatorname{ov}(x,y)$ be the maximum length of a string that is simultaneously a suffix of $x$ and a prefix of $y$ . The greedy superstring algorithm starts with the strings in $S$ and repeatedly replaces a pair $x,y$ having maximum overlap $\operatorname{ov}(x,y)$ by their overlap-merged concatenation, breaking ties arbitrarily, until one string $G(S)$ remains. If $\operatorname{OPT}(S)$ denotes the minimum length of a string containing every element of $S$ as a substring, then the conjecture asserts that $|G(S)|\leq 2\,\operatorname{OPT}(S)$ for every finite set $S$ and every sequence of tie-breaks.

Progress summary

Partially solved

A new preprint settles the lower-bound side at two for strings of length six or more and computes the three-letter case, but the conjectured upper bound for arbitrary inputs remains open.

The conjecture asserts that the greedy algorithm for the Shortest Common Superstring problem always achieves approximation ratio $2$ . The conjecture is attributed to Tarhio and Ukkonen and remains unresolved in its unrestricted form.

Known results

The conjecture holds for input strings of length at most $3$ and for strings of length exactly $4$ (Bulteau et al., 2024).
The known general upper bounds for the greedy ratio have been successively improved to $4$ , $3.5$ , $3.425$ , and approximately $3.396$ ; the conjectured upper bound $2$ is unproved.
Explicit constructions give ratios approaching $2$ from below, including examples not depending on tie-breaking.
The related Greedy Hierarchical and Collapsing Superstring conjectures are proved for strings of length at most $3$ (2019).

August 2026 lower-bound advance

A new arXiv preprint proves $\rho_k\ge 2$ for every $k\ge 6$ and exactly computes $\rho_3$ . This establishes ratio two in these length-restricted settings, but does not prove the upper bound for all instances.

Current status (as of August 2026): The length-restricted ratios now satisfy $\rho_k\ge 2$ for $k\ge 6$ and $\rho_3$ is known exactly, while the unrestricted claim that greedy is a $2$ -approximation remains open.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

The Greedy Superstring Algorithm Achieves Ratio 2 for Strings of Length 6 Already — arXiv

approximation-algorithms combinatorics

7 hours ago