CS Paper Radar

The Greedy Superstring Conjecture Is False

Nikolai Chukhin, Rishikesh Gajjala, Juha Harviainen, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Shibata, Alexander V. Smal

cs.DS ·submitted 2026-09-01 15:03 UTC · v2
theory

Abstract

In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Since the problem is NP-hard, various approximation algorithms have been proposed for it. The currently best known approximation ratio is $2.466$ due to Englert, Matsakis, and Veselý; a better approximation ratio $2$ has been announced by OpenAI just recently. In 1988, Tarhio and Ukkonen introduced a simple greedy algorithm that iteratively takes two strings with the longest overlap and merges them together. They showed that the greedy algorithm may produce a superstring that is about two times longer than the optimal one and conjectured that this bound is tight. This has become known as the Greedy Superstring Conjecture and has remained open for almost four decades. The best known upper bound on the approximation ratio of the greedy algorithm is $3.396$ due to Englert, Matsakis, and Veselý. In this paper, we present a series of results tightening the bounds of the greedy algorithm, with the main contributions being as follows: 1. We refute the Greedy Conjecture by constructing a family of instances for which a lower bound on the approximation ratio tends to $2.4$. 2. We prove that the greedy algorithm is $3$-approximate. 3. For input strings of fixed length $k$, we prove that the approximation guarantee is exactly $9/5$ for $k=3$ and at least $2$ for all $k \ge 6$.

Comment
Preliminary versions of the results of this paper are contained in arXiv:2608.20018v2, arXiv:2609.27921v2, and arXiv:2609.01365v1

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-08-20 ·Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal
theory similarity 0.92
Abstract · Fix typos (mostly in section 3)

In the Shortest Common Superstring (SCS) problem, one is given a set of strings and is asked to find a string of minimum length containing each of the input strings as a substring. The greedy superstring conjecture states that the following natural greedy algorithm has approximation ratio $2$: while there is more than one string, select the pair of strings with the maximum overlap, merge them, and add the merged string back to the set. The greedy algorithm works in linear time and is probably the simplest possible approximation algorithm for SCS. If the conjecture holds, then the greedy algorithm also surpasses the approximation guarantees of the best known approximation algorithms. The conjecture is open for $40$ years already and even the approximation ratio $ρ_k$ in the special case in which input strings have length $k$ has not yet been found: for all $k \ge 3$, $2-1/k \le ρ_k \le \min\{(k+1)/2, 3.396\}$. We prove that already for strings of length $6$, the approximation ratio of the greedy algorithm is at least $2$: $ρ_k \ge 2$ for all $k \ge 6$. We also show that $ρ_3=9/5$, thus completely characterizing the worst-case behavior of the greedy algorithm for strings of length $3$.

0.45

A Tight Cycle-Cover Inequality for Shortest Common Superstring

cs.DS ·2026-08-21 ·Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal
publishedtheory similarity 0.86
Abstract · updated the proof's exposition

In the Shortest Common Superstring problem (SCS), one is given a finite set of strings and is asked to find a shortest string containing every input string as a substring. Its best known approximation ratio is $2.466$, whereas the currently strongest upper bound on the approximation guarantee of the maximum-overlap greedy algorithm is $3.396$ (Englert, Matsakis, and Vesel{ý}, 2023), though it is conjectured to be $2$. We improve both approximation guarantees: SCS admits a $\frac{7}{3}$ approximation and the approximation guarantee of the greedy algorithm is at most $3$. The main technical ingredient of our proof is a certain inequality for optimum cycle covers of an overlap graph associated with the input strings. Every previous improvement of greedy's worst-case guarantee and the two recent record guarantees for general SCS are driven by it. We improve this inequality by pushing it to its limit: for a particular coefficient of this inequality, we show a new upper bound and prove that it cannot be improved further.

0.47

Tight Cycle-Cover Inequalities and Improved Approximation for Shortest Common Superstring with Reverse Complements

cs.DS ·2026-11-12 ·Ryosuke Yamano, Tetsuo Shibuya
similarity 0.62
Abstract

The Shortest Common Superstring (SCS) problem is a classical idealized model of genome assembly. However, SCS does not account for the double-stranded nature of DNA: sequencing reads may originate from either strand without a known orientation. This motivates a natural variant, Shortest Common Superstring with Reverse Complements (SCS-RC), which asks for a shortest string containing each input string or its reverse complement as a substring. For SCS, the MGREEDY algorithm constructs an optimal cycle cover of the overlap graph and concatenates the strings obtained by breaking each cycle at its minimum-overlap edge. This algorithm was recently shown to achieve a tight $3$-approximation. Its reverse-complement extension, MGREEDY-RC, also constructs an optimal cycle cover of the overlap graph augmented with reverse complements, but its best known approximation guarantee was $3.75$ (CPM 2026). We extend this cycle-cover inequality to SCS-RC and show that MGREEDY-RC achieves a $3$-approximation, which is tight even over the DNA alphabet. The $3$-approximation guarantee for MGREEDY-RC yields a $2.5$-approximation for TGREEDY-RC, which greedily merges the strings derived from the cycle cover. By replacing this greedy merging step with an algorithm based on a reduction to a maximum-weight Hamiltonian path problem constrained to contain a given perfect matching, we obtain a $(22/9+\varepsilon)$-approximation for every fixed $\varepsilon>0$. This improves upon the previous best ratio of $8/3$ (WABI 2026), establishing the best known polynomial-time approximation guarantee for SCS-RC.

0.14

Longest Unbordered Factors in Linear Time

cs.DS ·2026-11-09 ·Takuya Mieno
similarity 0.60
Abstract

A border of a string is a nonempty proper prefix that is also a suffix. A string is unbordered if it has no border. The length of a longest unbordered factor is closely related to the smallest period of the string. While the smallest period can be computed in linear time, the best previously known algorithm for computing a longest unbordered factor takes $O(n \log n)$ worst-case time for a string of length $n$. Whether this computational problem can be solved in worst-case linear time has remained open. In this paper, we resolve this open problem for integer alphabets of size $n^{O(1)}$ by presenting an algorithm that computes all occurrences of longest unbordered factors in $O(n)$ worst-case time. Our algorithm uses a combinatorial property of longest unbordered factors and scans the input string in both directions to capture all occurrences achieving the global maximum without computing the local maximum at every starting position.

0.28

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.59
Abstract

We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

0.53

Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation

cs.DS ·2026-11-03 ·Nick Fischer, Yael Kirkpatrick, Vasileios Nakos
similarity 0.59
Abstract

\emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute the Hamming distance between~$P$ and every length-$|P|$ substring of~$T$. As exact algorithms have been stuck at time~$\tilde O(n^{3/2})$ for decades, a long line of work has turned to the $(1+ε)$-approximate version of the problem. Milestones include Karloff's $\tilde O(ε^{-2} n)$-time algorithm [IPL '93], followed by randomized improvements to $\tilde O(ε^{-1} n)$ by Kopelowitz and Porat [FOCS '15] and recently to $\tilde O(ε^{-0.915} n)$ by Chan, Jin, Vassilevska W., and Xu [FOCS '23]. In this work, we significantly improve this bound to $\tilde O(ε^{-2/3} n)$, using a considerably simpler algorithm. Our algorithm follows the framework of Chan, Jin, Vassilevska W., and Xu, which reduces the problem to a variant of 3SUM that we call \emph{Sumset Estimation}. We solve Sumset Estimation optimally (up to logarithmic factors) by replacing their matrix multiplication techniques with ideas from sparse recovery. Specifically, we adapt the classic Count Sketch by replacing its random signs with random complex roots of unity---a simple idea that may find further applications for other additive problems. Finally, we give evidence that our running time might in fact be optimal: we show that the $ε^{-2/3}$ dependence is \emph{best possible} for a certain natural class of algorithms, including ours and all previous algorithms.

0.50

An $n^{8/5+o(1)}$-Time $Ω(λ^3)$-Approximation for Longest Common Subsequence

cs.DS ·2026-09-25 ·Zhao Song
similarity 0.59
Abstract

Let $λ$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω(λ^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω(λ^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.

0.15

Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses

cs.DS cs.CL ·2026-11-05 ·Kundan Baliga, Aiden Xie, Aditya Byju
theory similarity 0.58
Abstract · 40 pages, 7 figures. Restructured: the results on the re-typing inequality for short tokens moved to a companion paper; the compressed-lengt…

Byte-Pair Encoding (BPE) builds most language-model tokenisers by repeatedly merging a most frequent adjacent pair of symbols. How much shortening can this greedy rule lose against the best $k$ merges? Kozma and Voderholzer proved that greedy achieves at least one third of the optimal shortening; the best known upper bound is $(1-e^{-2})/2\approx 0.432$. We show that one third is a barrier for packing-based analyses, which see the optimum only through a pair packing, and we prove that greedy achieves at least $0.391$ of the optimum on every input, with any tie-breaking. The key idea is rule determinism: all copies of a rule of the optimum spell the same letters, so when one greedy replacement destroys three of the optimum's merge points, half a unit can be refunded on each side. A weaker bound, $0.374$, has a short proof that needs no computer; $0.391$ adds a certificate in exact arithmetic. We also show that the worst-case ratio is exactly $3/4$ for two merges and at most $7/12$ for three.

0.53