CS Paper Radar

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

Ryosuke Yamano, Tetsuo Shibuya

cs.DS ·submitted 2026-11-12 10:00 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

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

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

cs.DS ·2026-09-21 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
similarity 0.62
Abstract

Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every string produced during the computation remains available for reuse. Given an initial set of strings $A$ and a target set $B$, the objective is to produce all strings in $B$ using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length $n$, we obtain an $O(\log n)$-approximation, and we extend the result to arbitrary finite target sets with an $O(\log N)$-approximation, where $N$ is the total length of the targets not already present in the initial set. This resolves the approximability question for the non-uniform non-contiguous case left open by Constantin and Popa (TCS 2025).

0.08

Pangenome Optimization via Elastic Degenerate Strings

cs.DS ·2026-09-22 ·Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen
code/data similarity 0.61
Abstract

An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.

0.39

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

MacCorles: Minimum Alignment Cost Computation on Run-Length Encoded Strings

cs.DS ·2026-08-14 ·Wing-Kai Hon, Dominik Köppl, Jun-Hong Wang
similarity 0.56
Abstract

We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligned character pairs, as in the classical longest common subsequence problem, and then, among all such alignments, to minimize the alignment length. Equivalently, after maximizing the number of equal pairs, we minimize the number of insertions and deletions. We show that this problem admits a simple block-boundary dynamic program. If the input strings have lengths $N$ and $M$, and their run-length encodings have $n$ and $m$ runs, respectively, the algorithm runs in $O(mN+nM)$ time using $O(nm)$ space. The algorithm treats every pair of runs as a homogeneous block with an explicit transfer function and stores dynamic-programming values only on run boundaries.

0.04

NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance

cs.DS ·2026-09-16 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
theory similarity 0.56
Abstract

In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the \emph{translocation operation} is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as \emph{contiguous} if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as \emph{non-contiguous}. If the exchanged prefixes are of equal length, the translocation is called \emph{uniform}. Otherwise, the translocation is termed \emph{non-uniform}. The \emph{translocation distance} between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.

0.42

Reportable Shortcuts with RLBWTs

cs.DS ·2026-09-06 ·Travis Gagie
similarity 0.55
Abstract

Backward search over a run-length compressed Burrows-Wheeler transform (RLBWT) takes one step per pattern character, even when long stretches of the pattern match material that recurs throughout a highly repetitive collection. We describe shortcuts: for a precomputed set of pairs $(α,β)$ of strings, a backward search that has just matched $β$ and finds $α$ immediately to its left in the pattern can cross $α$ in one step. Since a shortcut is taken only after its pair has been recognized in the pattern, the search returns a report of the shortcuts it took along with the usual BWT interval. Our motivation is pangenome graphs, where such pairs mark the places where a pattern passes through a vertex, so the report gives the path a match takes through the graph. We work out the case of a single linear reference $R$, with $β$ ranging over the length-$\ell$ windows of $R$ starting at multiples of $\ell$, and $α$ over the $2^t \ell$ characters preceding such a window. We show that the search counts correctly, that under stated conditions it crosses a stretch of the pattern matching $m$ consecutive windows of $R$ with $O(\log m + m / 2^τ)$ shortcuts, where $2^τ\ell$ is the longest shortcut, and that the shortcuts can be built efficiently from the RLBWT. On the Pizza&Chili cere collection of 37 genomes, shortcuts make backward search 2.3 to 4.2 times faster on exact patterns of length 200 to 1000, and 1.7 to 2.0 times faster with 1% of the characters substituted, for 86% more space. On 11 gigabases of genomes of seven bacterial species, they make it 1.6 to 1.9 times faster on exact patterns for 32% more space. On whole chromosome 19 haplotypes against 16 to 64 others from the Human Pangenome Reference Consortium, shortcuts in both directions make Boyer-Moore-Li search for maximal exact matches of length at least 1000 about 8 times faster.

0.26