On the greedy algorithm for the Shortest Common Superstring problem with reversals

• We study a variation of the Shortest Common Superstring (SCS) problem in which reversals of strings are allowed, called SCS-R.
• We show that a natural adaptation of the classical greedy algorithm for SCS can be used for the SCS-R problem.
• We prove that our algorithm has (optimal) compression ratio 1/2.
• We also provide a linear-time implementation of our algorithm.

We study a variation of the classical Shortest Common Superstring (SCS) problem in which a shortest superstring of a finite set of strings S is sought containing as a factor every string of S or its reversal. We call this problem Shortest Common Superstring with Reversals (SCS-R). This problem has been introduced by Jiang et al. [9], who designed a greedy-like algorithm with length approximation ratio 4. In this paper, we show that a natural adaptation of the classical greedy algorithm for SCS has (optimal) compression ratio  12, i.e., the sum of the overlaps in the output string is at least half the sum of the overlaps in an optimal solution. We also provide a linear-time implementation of our algorithm.