Publication
A Tight Cycle-Cover Inequality for Shortest Common Superstring
ECCC TR26-157, 2026. PDF ยท Official record
Abstract
In the Shortest Common Superstring problem, one is given a finite set of strings and seeks a shortest string containing every input string as a substring. Before this work, the best known approximation ratio for SCS was (2.466), while the strongest upper bound for the maximum-overlap greedy algorithm was (3.396).
We improve both guarantees: SCS admits a (7/3)-approximation, and the greedy algorithm has approximation ratio at most (3). The main technical ingredient is a strengthened inequality for optimum cycle covers of the overlap graph. For a key coefficient, we prove both a new upper bound and a matching limitation.