← All problems

Greedy superstring conjecture

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

References

Progress summary

Refreshed
Open · progress reported

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 33, and strings of exactly 44, satisfy the conjectured bound (Bulteau et al., 2024).
  • General upper bounds have improved from 44 to 3.53.5, 3.4253.425, and approximately 3.3963.396; 22 is unproved.
  • Explicit families attain ratios approaching 22 from below, including tie-breaking-independent examples.
  • Related hierarchical and collapsing variants are settled for strings of length at most 33 (2019).

August 2026 lower-bound advance

On August 20, 2026, a report on the new arXiv preprint stated that it proves ρk≥2\rho_k\geq 2 for every k≥6k\geq 6 and computes ρ3=95\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-22 approximation remains open, while length-restricted lower bounds now include ρk≥2\rho_k\geq 2 for k≥6k\geq 6 and the exact value ρ3=95\rho_3=\frac{9}{5}.

Sources

Solutions 1

Claimed by OpenAI. The manuscript claims a deterministic polynomial-time algorithm that constructs a common superstring of length at most twice the optimum for every finite input set of strings. This is related approximation progress for the same optimization problem. Its algorithm is distinct from the page’s maximum-overlap Greedy procedure, and the manuscript does not establish that procedure’s factor-two guarantee for arbitrary tie-breaks.See full solutionHide full solution