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.

References

Primary source

arXiv

Additional references

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

approximation-algorithms combinatorics

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new preprint sharpens the lower-bound examples, but the conjectured guarantee that the greedy method never exceeds twice the optimum remains unproved.

The conjecture, attributed to Tarhio and Ukkonen, says that repeatedly merging the most-overlapping pair produces a superstring of length at most twice the optimum, regardless of tie-breaking. Its unrestricted form remains open after more than thirty years.

Known results

Strings of length at most $3$ , and strings of exactly $4$ , satisfy the conjectured bound (Bulteau et al., 2024).
General upper bounds have improved from $4$ to $3.5$ , $3.425$ , and approximately $3.396$ ; $2$ is unproved.
Explicit families attain ratios approaching $2$ from below, including tie-breaking-independent examples.
Related hierarchical and collapsing variants are settled for strings of length at most $3$ (2019).

August 2026 lower-bound advance

On August 20, 2026, a report on the new arXiv preprint stated that it proves $\rho_k\geq 2$ for every $k\geq 6$ and computes $\rho_3=\frac{9}{5}$ . This strengthens the known lower-bound picture but does not establish the conjectured upper bound for arbitrary inputs; the preprint’s claims remain unverified here.

Current status (as of August 2026): The unrestricted assertion that greedy always achieves a factor- $2$ approximation remains open, while length-restricted lower bounds now include $\rho_k\geq 2$ for $k\geq 6$ and the exact value $\rho_3=\frac{9}{5}$ .

Sources

No solutions have been posted yet.