Breakthrough Tracker record
A preprint disproves the greedy superstring 2-approximation conjecture
Hiroki Shibata constructs instances for which the standard greedy shortest-common-superstring algorithm has approximation ratio approaching 9/4. This refutes the nearly four-decade conjecture that the ratio is at most 2.
← Back to the filtered Breakthrough Tracker
- Stable ID
cs-greedy-superstring-conjecture-counterexample-2026- Revision
cs-greedy-superstring-conjecture-counterexample-2026.v1- Field
- Computer Science · Algorithms, approximation and string combinatorics
- Evidence
- Tier 1 · Peer reviewed: No
- Record state
- Provisional · Provisional claimed counterexample
- Last checked
AI role
The author reports that GPT-5.6 Sol, used through a custom harness, first discovered the counterexample and proof strategies. The author examined, simplified and verified the proof and takes responsibility for it.
Record details
- Problem or result
- The conjectured factor-2 guarantee for the greedy shortest-common-superstring algorithm
- Authors
- Hiroki Shibata
- Institutions
- Joint Graduate School of Mathematics for Innovation, Kyushu University
- Result date
- First-version preprint submitted September 1, 2026
Why it matters
Shortest common superstring is a foundational approximation problem with applications in sequence assembly and compression. The construction raises the greedy algorithm’s known worst-case lower bound from 2 to 9/4.
Limits
The result is a first-version preprint with no located peer review or independent verification. It establishes a lower bound approaching 9/4; it does not determine the exact worst-case ratio, whose known upper bound remains 3.
Sources
Correction and revision history
- 2026-09-04 — Added after primary-source, scope, status, AI-role and limitation review.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.