CS Paper Radar

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

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander Smal

cs.DS ·submitted 2026-08-20 13:29 UTC · v2
theory

Abstract

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$.

Comment
Fix typos (mostly in section 3)

Closest papers

Nearest neighbours by meaning across the whole index.

The Greedy Superstring Conjecture Is False

cs.DS ·2026-09-01 ·Nikolai Chukhin, Rishikesh Gajjala, Juha Harviainen, Alexander S. Kulikov, Ivan Mihajlin +2 more
theory similarity 0.92
Abstract · Preliminary versions of the results of this paper are contained in arXiv:2608.20018v2, arXiv:2609.27921v2, and arXiv:2609.01365v1

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$.

0.09

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.84
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.44

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

cs.DS ·2026-09-25 ·Zhao Song
similarity 0.62
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

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.60
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

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.60
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

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.59
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

Internal Queries for Maximal Closed Substrings

cs.DS ·2026-11-08 ·Simone Faro, Francesco Pio Marino, Arianna Pavone
theory similarity 0.57
Abstract

Searching for repetitions inside a selected part of a text raises a subtle boundary problem: removing neighbouring characters can create new maximal answers. We study this effect for maximal closed substrings (MCSs). A string is closed if it is a single letter or has a nonempty proper prefix occurring exactly twice, as its prefix and suffix; a closed occurrence is maximal if neither available one-character extension is closed. Previous work established $O(n\log n)$ bounds on the global MCS families of a length-$n$ text and developed enumeration algorithms. Internal queries instead ask for the MCSs of a chosen substring, with maximality evaluated inside that substring. Separating boundary occurrences from interior ones gives an $O(n\log n)$-word index that reports the $c$ answers in $O(\log n+c)$ time and supports counting and longest queries in $O(\log n)$ time. Our main result reduces reporting space to $O(n)$ words, with $O((c+1)\log^{1+\varepsilon} n)$ query time and $O(n\log^{1+\varepsilon} n)$ construction time for any fixed $\varepsilon>0$. Thus, after preprocessing, reporting requires no additive scan of the queried substring, which is particularly useful for long queries with few answers. Independently, we prove that at most $3(s-1)$ MCS occurrences of any length-$s$ substring cross a fixed gap between consecutive characters, with maximality evaluated inside that substring. The same bound holds for global MCSs contained in a length-$s$ block. A family over two letters attains $\lfloor(s-1)/2\rfloor$ crossings for every $s\ge3$, showing that the linear order of this local density bound is optimal.

0.10

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.56
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