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.