On the Greedy Algorithm for the Shortest Common Superstring
Problem with Reversals
Gabriele Fici
Dipartimento di Matematica e Informatica, Università di Palermo, Italy
gabriele.fici@unipa.it

arXiv:1511.08431v2 [] 7 Dec 2015

Tomasz Kociumaka
Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
kociumaka@mimuw.edu.pl
Jakub Radoszewski
Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland and
Newton International Fellow at Department of Informatics, King’s College London, UK
jrad@mimuw.edu.pl
Wojciech Rytter
Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
rytter@mimuw.edu.pl
Tomasz Waleń
Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
walen@mimuw.edu.pl

Abstract
We study a variation of the classical Shortest Common Superstring (SCS) problem in
which a shortest superstring of a ﬁnite 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
1
2 , 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.

Keywords: Shortest Common Superstring, reversal, greedy algorithm.

1

Introduction

The Shortest Common Superstring (SCS) problem is a classical combinatorial problem on strings
with applications in many domains, e.g. DNA fragment assembly, data compression, etc. (see
[6] for a recent survey). It consists, given a ﬁnite set of strings S over an alphabet Σ, in ﬁnding a
shortest string containing as factors (substrings) all the strings in S. The decision version of the
problem is known to be NP-complete [13, 5, 4], even under several restrictions on the structure
of S (see again [6]). However, a particularly simple greedy algorithm introduced by Gallant in
his Ph.D. thesis [5] is widely used in applications since it has very good performance in practice
1

(see for instance [12] and references therein). It consists in repetitively replacing a pair of strings
with maximum overlap with the string obtained by overlapping the two strings, until one string
remains. The greedy algorithm can be implemented using Aho-Corasick automaton in O(n)
randomized time (with hashing on the symbols of the alphabet) or O(n min(log m, log |Σ|))
deterministic time (see [17]), where n is the sum of the lengths of the strings in S and m its
cardinality.
The approximation of the greedy algorithm is usually measured in two diﬀerent ways: one
consists in taking into account the approximation ratio (also known as the length ratio) kg /kmin ,
where kg is the length of the output string of greedy and kmin the length of a shortest superstring,
the other consists in taking into account the compression ratio (n − kg )/(n − kmin ).
For the approximation ratio, Turner [16] proved that there is no constant c < 2 such that
kg /kmin ≤ c. The greedy conjecture states that this approximation ratio is in fact 2 [1]. The
best bound currently known is 3.5 due to Kaplan and Shafrir [10]. Algorithms with better
approximation ratio are known; the best one is due to Mucha, with an approximation ratio of
11
[14].
2 23
For the compression ratio, Tarhio and Ukkonen [15] proved that (n − kg )/(n − kmin ) ≥ 21
and this bound is tight, since it is achieved for the set S = {abh , bh a, bh+1 } when greedy makes
the ﬁrst choice merging the ﬁrst two strings together.
Let us formally state the SCS problem:
Shortest Common Superstring (SCS)
Input: strings S = {s1 , . . . , sm } of total length n.
Output: a shortest string u that contains si for each i = 1, . . . , m as a factor.
Several variations of SCS have been considered in literature. For example, shortest common
superstring problem with reverse complements was considered in [11]. In this setting the alphabet is Σ = {a, t, g, c} and the complement of a string s is s̄R , where ¯ is deﬁned by ā = t, t̄ = a,
ḡ = c, c̄ = g, and tR denotes the reversal of t, that is the string obtained reading t backwards.
In particular, this problem was shown to be NP-complete.
Other variations of the SCS problem can be found in [8, 3, 7, 2].
In this paper, we address the problem of searching for a string u of minimal length such
that for every si ∈ S, u contains as a factor si or its reversal sR
i .
Shortest Common Superstring with Reversals (SCS-R)
Input: strings S = {s1 , . . . , sm } of total length n.
Output: a shortest string u that contains for each i = 1, . . . , m at least one of the strings
si or sR
i as a factor.
For example, if S = {aabb, aaac, abbb}, then a solution of SCS-R for S is caaabbb. Notice that
a shortest superstring with reversals can be much shorter than a classical shortest superstring.
An extremal example is given by an input set of the form S = {abh , cbh }.
The SCS-R problem was already considered by Jiang et al. [9], who observed (not giving
any proof) that the problem is still NP-hard. We provide a proof at the end of the paper.
In [9], the authors proposed a greedy 4-approximation algorithm. Here, we show that an
adaptation of the classical greedy algorithm can be used for solving the SCS-R problem with
an (optimal) compression ratio 12 , and that this algorithm can be implemented in linear time
with respect to the total size of the input set.

2

2

Basics and Notation

Let Σ be a ﬁnite alphabet. We assume that Σ is linearly sortable, e.g., Σ = {0, . . . , nO(1) }. The
length of a string s over Σ is denoted by |s|. The empty string, denoted by ε, is the unique
string of length zero. A string t occurs in a string s if s = vtz for some strings v, z. In this case
we say that t is a factor of s. In particular, we say that t is a prefix of s when v = ε and a
suffix of s when z = ε. We say that a factor t is proper if s 6= t.
The string sR obtained by reading s from right to left is called the reversal (or mirror image)
R
of s. Given a set of strings S = {s1 , . . . , sm }, we deﬁne the set S R = {sR
1 , . . . , sm } and the set
R
e
S =S∪S .
Given two strings u, v, we deﬁne the (maximum) overlap between u and v, denoted by
ov(u, v), as the length of the longest suﬃx of u that is also a preﬁx of v. Sometimes we abuse
the notation and also say that the suﬃx of u of length ov(u, v) is the overlap of u and v. In
general ov(u, v) is not equal to ov(v, u), but it is readily veriﬁed that ov(u, v) = ov(v R , uR ).
Additionally, we deﬁne pr (u, v) as the preﬁx of u obtained by removing the suﬃx of length
ov(u, v) and denote u⊗v = pr(u, v)v. Note that the ⊗ operation is in general neither symmetric
nor associative.
A set of strings S is called factor-free if no string in S is a factor of another string in S. We
say that S is reverse-factor-free if there are no distinct strings u, v ∈ S such that u is a factor
of v or v R .
Given a factor-free set of strings S = {s1 , . . . , sm }, the SCS problem for S is known to
be equivalent to that of ﬁnding a maximum-weight Hamiltonian path π in the overlap graph
GS , which is a directed weighted graph (S, E, w) with arcs E = {(si , sj ) | i 6= j} of weights
w(si , sj ) = ov(si , sj ) (cf. Theorem 2.3 in [15]). In this setting, a path π = si1 , . . . , sik corresponds
to a string str(π) := pr (si1 , si2 ) · · · pr(sik−1 , sik )sik . By ov(π) we denote the total weight of arcs
in the path π.
e S = (V, E, w).
To accommodate reversals we extend the notion of an overlap graph to G
R
Here V = {vs : s ∈ S} ∪ {vs : s ∈ S} so every s ∈ S corresponds to exactly two vertices, vs
e S we deﬁne αR as v R
and vsR . We deﬁne str(vs ) = s and str (vsR ) = sR . For a vertex α ∈ G
s
if α = vs for some s or as vs if α = vsR for some s. Note that str(αR ) = str(α)R . For every
α, β ∈ V , α 6= β, we introduce an arc from α to β with weight ov(str(α), str (β)). For an arc
e = (α, β) we deﬁne eR = (β R , αR ). Note that the weight of eR is the same as the weight of e.
e S we also use the notions of str(π) and ov(π). We say that a path π in G
eS
For paths π in G
e S , exactly one of the two vertices α,
is semi-Hamiltonian if π contains, for every vertex α ∈ G
R
α . Observe that a solution to SCS-R problem for a reverse-factor-free set S corresponds to a
eS .
maximum-weight semi-Hamiltonian path π in the overlap graph G

3

Greedy Algorithm and its Linear-Time Implementation

We deﬁne an auxiliary procedure Make-Reverse-Factor-Free(S) that removes from S all
strings u which are contained as a factor in v or v R for some v ∈ S, v 6= u. Note that the
resulting set S ′ is reverse-factor-free and, moreover, a string is a common superstring with
reversals for S ′ if and only if it is a common superstring with reversals for S.
Example 1. Let S = {ab, aaa, aab, baa}. Then Make-Reverse-Factor-Free(S) produces
S ′ = {aaa, aab} or S ′ = {aaa, baa}.
The Greedy-R algorithm works as follows: while |S| > 1, choose u, v ∈ Se (excluding u = v
and u = v R ) with largest overlap, insert into S the string u ⊗ v, and remove from S all strings
among u, v, uR , v R that belong to S; see the pseudocode.
3

Algorithm Greedy-R(S)
Input: a non-empty set of strings S
Output: a superstring of S that approximates a solution of SCS-R problem for S
begin
S := Make-Reverse-Factor-Free(S)
while |S| > 1 do
e u∈
P := {(u, v) : u, v ∈ S,
/ {v, v R }}
{ S is reverse-factor-free and |S| > 1, so |P | ≥ 1 }
take (u, v) ∈ P with the maximal value of ov(u, v)
S := S ∪ {u ⊗ v}
S := S \ {u, v, uR , v R }
return the only element of S
end
Let us state two properties of this algorithm useful for its eﬃcient implementation.
Lemma 1. The set S stays reverse-factor-free after each iteration of the while loop.
Proof. Suppose that at some point S ceases to be reverse-factor-free. This might only be due
to the fact that, when w = u ⊗ v is introduced to S, Se contains a string w′ ∈
/ {u, uR , v, v R } such
′
that w is a factor of w but not of u or v. The latter, however, implies ov(u, w′ ) > ov(u, v) and
ov(w′ , v) > ov(u, v). That contradicts the choice of (u, v) ∈ P maximizing ov(u, v).
Lemma 2. Before u ⊗ v is inserted to S, we have ov(w, u ⊗ v) = ov(w, u) and ov(u ⊗ v, w) =
e
ov(v, w) for every w ∈ S.

Proof. Clearly, ov(w, u ⊗ v) ≥ ov(w, u) and ov(u ⊗ v, w) ≥ ov(v, w). Moreover, one of these
inequalities might be strict only if ov(w, u ⊗ v) > |u| or ov(u ⊗ v, w) > |v|, in particular, only if
w contains respectively u or v as a proper factor. This, however, contradicts Lemma 1.

3.1

Interpretation on the Overlap Graph

Tarhio and Ukkonen [15] work with the following interpretation of the greedy algorithm on the
overlap graph GS : They maintain a set of arcs F ⊆ E(GS ) forming a collection of disjoint
paths and at each step they add to F an arc e ∈ E(GS ) \ F of maximum weight so that the
resulting set still forms a collection of disjoint paths. Here, paths correspond to strings in the
collection S maintained by the original implementation. Insertion of an arc (si , sj ) to F results
in merging two paths into one and this corresponds to replacing strings u, v ∈ S with u ⊗ v. It
turns out that ov(u, v) = ov(si , sj ) and thus both implementations of the greedy algorithm are
equivalent.
e S and, for
Here, we provide an analogous interpretation of Greedy-R on the overlap graph G
completeness, explicitly prove its equivalence to the original implementation. We also maintain
e S ) forming a collection of disjoint paths. In each step we extend F
a set of arcs F ⊆ E(G
with a pair of arcs {e, eR } of maximum (common) weight so that the resulting set still forms
a collection of disjoint paths; see the pseudocode of algorithm Greedy-R2. Observe that this
R
way paths formed by F come in pairs π, π R such that π = α1 , . . . , αp and π R = αR
p , . . . , α1 (in
particular, str(π R ) = str (π)R ). We claim that these pairs of paths correspond to strings s ∈ S
of the original implementation (with s = str (π) or s = str (π R )). In particular, each string s ∈ Se
corresponds to a single path formed by F unless s = sR when it corresponds to two reverse
paths. The claim is certainly true at the beginning of the algorithm, so let us argue that single
iterations of the main loops in both algorithms perform analogous operations.
4

Algorithm Greedy-R2(S)
Input: a non-empty set of strings S
Output: a superstring of S that approximates a solution of SCS-R problem for S
begin
S := Make-Reverse-Factor-Free(S)
eS
Construct G
F := ∅
for i := 1 to |S| − 1 do
e S ) \ F : F ∪ {e, eR } forms a collection of disjoint paths in G
eS }
P := {e ∈ E(G
take e ∈ P with the maximal weight w(e)
F := F ∪ {e, eR }
eS
return str (π) for one of the maximal paths π formed by F in G
end
First, consider an arc e = (α, β) such that there exists a path π that ends at α and a path π ′
that starts at β. (Otherwise, F ∪ {e, eR } does not form a collection of disjoint paths). Observe
that strings u = str(π) and v = str(π ′ ) belong to Se in Greedy-R and that u ∈ {v, v R } if and
only if F ∪ {e, eR } yields a cycle. Thus, both algorithms consider essentially the same set of
possibilities (the only caveat is that if u or v is a palindrome, then several arcs e correspond to
e By Lemma 2 the weight of an arc (α, β) is ov(str(α), str (β)) =
the same pair of strings from S).
ov(u, v). Thus, the maximum-weight arcs correspond to pairs (u, v) ∈ P with largest overlap.
Clearly, setting F := F ∪ {e, eR } results in merging π ′ with π and π R with π ′R . These
paths represent u ⊗ v and v R ⊗ uR . Since the set S in Greedy-R stays reverse-factor-free due
to Lemma 1 and, in particular, S does not contain any pair of strings v, v R such that v is not
a palindrome, the “S := S \ {u, uR , v, v R }” instruction always removes exactly two elements of
S. This means that the bijection between S and pairs of paths formed by F is preserved.
Finally, observe that after exactly |S| − 1 steps F forms two semi-Hamiltonian paths. Either
of them can be returned as a solution.

3.2

Linear-Time Implementation

Ukkonen [17] showed that the Greedy algorithm for the original SCS problem can be implemented in linear time based on the overlap-graph interpretation. Our linear-time implementation of the Greedy-R2 algorithm is quite similar.
First, let us show how to eﬃciently implement the Make-Reverse-Factor-Free operation. It is actually slightly easier to compute it for Se instead of S. However, this is not an issue:
if we substitute S with Se in the very beginning of the greedy algorithm, then the overlap graph
will stay the same.
e can be computed in time linear
Lemma 3. The result of Make-Reverse-Factor-Free(S)
in the total length of strings in S.

Proof. Let us introduce an auxiliary procedure Make-Factor-Free(X) that removes from X
all strings u for which there exists a string v in X such that u is a proper factor of v.
Ukkonen [17] applied the following result for the preprocessing phase of the greedy algorithm
for the ordinary SCS problem.
Claim 1 ([17]). Make-Factor-Free(X) can be implemented in time linear in the total length
of the strings in X.

5

e it suﬃces to determine
Observe that in order to compute Make-Reverse-Factor-Free(S)
e and then for every pair of strings u, uR ∈ S ′ leave exactly one of
S ′ = Make-Factor-Free(S)
these strings, e.g., the lexicographically smaller one. Note that u ∈ S ′ if and only if uR ∈ S ′ , so
for the latter it suﬃces to iterate through S ′ and report a string u if and only if u ≤ uR .
e which is at
The whole procedure works in linear time in the total length of strings in S,
most twice the total length of strings in S.

Now, we show the main result.
Theorem 4. Greedy-R algorithm can be implemented in time linear in the total length of strings
in S.
Proof. By Lemma 3, we can make the input set reverse-factor-free in linear time. Let S =
{s1 , . . . , sm } be the set of remaining strings and n the total length of strings in S.
We actually implement the equivalent algorithm Greedy-R2. We cannot store the whole
e S , since this would take too much space. Therefore we only store its vertex set, whereas
graph G
we will be considering the edges of the graph in an indirect way.
Denote by Pref (X) the set of all diﬀerent preﬁxes of strings in X. Each element of this
set can be represented as a state of the Aho-Corasick automaton constructed for X, thus using
O(1) space per element. Further, given a string w, denote by PrefSet(w, X), SufSet(w, X) the
sets (represented as lists of identiﬁers) of strings in X having w as a preﬁx, suﬃx, respectively.
Ukkonen [17] applied the Aho-Corasick automaton for X to show the following fact:
Claim 2 ([17]). PrefSet(w, X), SufSet(w, X) for all w ∈ Pref (X) can be computed in time linear
in the total length of the strings in X.
e PrefSet(w, S)
e and SufSet(w, S).
e Our
In the implementation we use sets of the form Pref (S),
e S ) inimplementation actually requires PrefSet and SufSet sets to consist of vertices α ∈ V (G
stead of strings str (α). Thus, we replace every string identiﬁer with one or two vertex identiﬁers
if the string is not a palindrome or is a palindrome, respectively.
Instead of simulating the main loop directly, we will consider all overlaps w of str (α) and
e S ). Observe that at subsequent
str(β) to ﬁnd the maximum-weight arc e = (α, β) ∈ E(G
e
iterations of the loop, the weight w(e) may only decrease. Hence, we iterate over all w ∈ Pref (S)
in decreasing length order and for each w check if there exists an appropriate arc e = (α, β)
such that F ∪ {e, eR } forms a collection of disjoint paths. More formally, we seek vertices
e S ) such that:
α, β ∈ V (G

(a) a path formed by F ends in α and a different path formed by F starts at β,

(b) β 6= αR , and
(c) w is the overlap of str(α) and str (β).
Once we ﬁnd such an arc e, we set F := F ∪ {e, eR }.
Let us explain how this approach can be implemented eﬃciently. To iterate through all
e in decreasing length order we simply traverse all the states of the Aho-Corasick
w ∈ Pref (S)
automaton in reverse-BFS order, breaking ties arbitrarily. To check the conditions (a)-(c), we
e and α ∈ SufSet(w, S)
e and verify if
could iterate through pairs of elements β ∈ PrefSet(w, S)
they satisfy the conditions. However, to avoid repetitively scanning redundant elements, we
e and α ∈ SufSet(w, S)
e if no path starts in β and no path ends in α,
remove β ∈ PrefSet(w, S)
respectively. For each vertex we will remember if a path starts or ends there, and, if so, what is
e there are at most two
the other endpoint of the path. Observe that for each α ∈ SufSet(w, S)
e
non-redundant elements β ∈ PrefSet(w, S) for which the arc e = (α, β) is not valid. Indeed,
these might only be αR and the starting vertex of the path ending at α.
6

Hence, with amortized constant-time overhead, either an arc e = (α, β) satisfying (a)-(c) is
found, or it can be veriﬁed that no such arc exists for this particular string w and then we can
e If an arc is found, we start the next search with
continue iterating through strings in Pref (S).
the same string w, since there could still be arcs satisfying conditions (a)-(c) for the same string
w.
To conclude: in every step of the simulation, in amortized constant time we either ﬁnd a
e The former
pair of arcs to be introduced to F or discard the given candidate w ∈ Pref (S).
situation takes place at most m − 1 times and the latter happens at most n times. The whole
algorithm thus works in O(n) time.

4

Compression Ratio

In this section we prove that the compression ratio of the Greedy-R algorithm is always at least
1
2 , and that this value is eﬀectively achieved, so the bound is tight.
Let S = {s1 , . . . , sm } be the input set of strings. We assume that S is already reverse-factore S . Let pgreedy(S)
free. Let opt(S) be the length of a longest semi-Hamiltonian path in G = G
denote the length of the semi-Hamiltonian path produced by the Greedy-R algorithm for S.
We will show that pgreedy(S) ≥ 12 opt(S).
In the proof we use as a tool the following fact from [15] (see Lemma 3.1 in [15]):
Lemma 5. If strings x1 , x2 , x3 , x4 satisfy
max(ov(x1 , x4 ), ov(x2 , x3 )) ≤ ov(x1 , x3 ),
then
ov(x1 , x4 ) + ov(x2 , x3 ) ≤ ov(x1 , x3 ) + ov(x2 , x4 ).
We proceed with the following crucial lemma.
Lemma 6. Let S be a set of strings and let u, v ∈ Se be two elements for which ov(u, v)
is maximal (u ∈
/ {v, v R }). Set OV = ov(u, v). Let opt(S) be the length of a longest semiHamiltonian path in G and let opt′ (S) be the length of a longest semi-Hamiltonian path in G
that contains the arc (u, v). Then:
opt′ (S) ≥ opt(S) − OV .
Proof. We consider the path π corresponding to opt(S) and show how it can be modiﬁed without
losing its semi-Hamiltonicity so that the arc (u, v) occurs in the path and the length of the path
decreases by at most OV .
Obviously, if π already contains the arc (u, v), nothing is to be done. If both u and v occur in
π, we perform transformations as in the proof of a similar fact from [15] related to the ordinary
SCS problem. If u occurs in π before v then we select π ′ as in Fig. 1 and:
ov(π ′ ) ≥ ov(π) − ov(u, b) − ov(c, v) + ov(u, v) ≥ ov(π) − ov(u, b) ≥ ov(π) − OV .
Note that both nodes b, c exist (they could be the same node, though). If any of the remaining
nodes does not exist, it is simply skipped on the path.
If v occurs before u, then by applying the inequality of Lemma 5 (with x1 = u, x2 = a,
x3 = v, x4 = d) we have
ov(u, d) + ov(a, v) ≤ ov(u, v) + ov(a, d).
7

π

s

a

u

b

c

v

d

t

π′

s

a

u

b

c

v

d

t

Figure 1: Proof of Lemma 6, ﬁrst case: u occurs in π before v.
By this inequality, for the path π ′ deﬁned in Fig. 2 we have:
ov(π ′ ) ≥ ov(π) − ov(a, v) − ov(u, d) + ov(u, v) + ov(a, d) − ov(v, b)
≥ ov(π) − ov(v, b) ≥ ov(π) − OV .
As before, if any of the depicted nodes does not exist, we simply skip the corresponding part of
the path. In particular, if any of the nodes u, v is an endpoint of the path π, we do not need to
use the aforementioned inequality to show that ov(π ′ ) ≥ ov(π) − OV .
π

s

a

v

b

c

u

d

t

π′

s

a

v

b

c

u

d

t

Figure 2: Proof of Lemma 6, second case: u occurs in π after v.
Diﬀerently from the original SCS problem considered in [15], it might not be the case that
u and v are in π. If none of them is, then π contains both uR and v R and by reversing π (that
is, taking the path π R ) we obtain a semi-Hamiltonian path that contains both u and v, which
was the case considered before. Thus, we can assume that u and v R occur in π (the case of uR
and v is symmetric). Again, we have two cases, depending on which of the two nodes comes
ﬁrst in π. If u occurs before v R in π, then we have (note that ov(c, v R ) = ov(v, cR )):
ov(π ′ ) ≥ ov(π) − ov(u, b) − ov(v R , d) + ov(u, v) ≥ ov(π) − ov(u, b) ≥ ov(π) − OV ,
see also Fig. 3.
Finally, if v R occurs before u, then (see Fig. 4):
ov(π ′ ) ≥ ov(π) − ov(v R , b) − ov(u, d) + ov(u, v) ≥ ov(π) − ov(v R , b) ≥ ov(π) − OV .
This completes the proof of the lemma.
To conclude the proof of the compression ratio of the Greedy-R algorithm we use an inductive
argument. Assume that pgreedy(S ′ ) ≥ 21 opt(S ′ ) for all S ′ such that |S ′ | < |S|. By Lemma 6,
for S ′ = S \ {u, v, uR , v R } ∪ {u ⊗ v}:
opt(S) − OV ≤ opt′ (S) ≤ opt(S ′ ) + OV ,
so that opt(S ′ )+2OV ≥ opt(S). Moreover, pgreedy(S) = pgreedy(S ′ )+OV and, by the inductive
hypothesis, pgreedy(S ′ ) ≥ 12 opt(S ′ ). Consequently:
1
1
pgreedy(S) = pgreedy(S ′ ) + OV ≥ (opt(S ′ ) + 2OV ) ≥ opt(S).
2
2
8

π

s

a

u

b

c

vR

d

t

π′

s

a

u

bR

cR

v

d

t

Figure 3: Proof of Lemma 6, third case: u occurs in π before v R .
π

s

a

vR

b

c

u

d

t

π′

sR

aR

v

b

c

u

d

t

Figure 4: Proof of Lemma 6, third case: u occurs in π after v R .
We arrive at the following theorem.
Theorem 7. Greedy-R has compression ratio 21 .
It turns out that the bound on the compression ratio of the Greedy-R algorithm is tight. It
suﬃces to consider the set of strings {abh , bh c, bh+1 } (this is actually the same example as from
the analysis of the Greedy algorithm [1]). The output of Greedy-R can be the string abh cbh+1
with total overlap h, whereas an optimal solution to SCS-R is abh+1 c of total overlap 2h.

5

NP-completeness of the SCS-R Problem

Let Γ = Σ ∪ {$, #}, where $, # 6∈ Σ. Let h be the morphism from Σ∗ to Γ∗ deﬁned by
h(c) = $# c, for every c ∈ Σ. Given k ≥ 1, we also deﬁne the morphism gk (c) = ck , for every
c ∈ Σ.
Observation 1. For every nonempty strings u, v, the strings h(u) and h(v)R have an overlap of
length at most one.
Observation 2. For every nonempty strings u, v, one has
|h(gk (u))| = 3k|u|

and

ov(h(gk (u)), h(gk (v))) = 3k · ov(u, v).

In the decision version of the SCS-R problem we need to check if a given set of strings
admits a common superstring with reversals of length at most ℓ, where ℓ is an additional input
parameter.
Proposition 8. The decision version of the SCS-R problem is NP-complete.
Proof. Let s1 , . . . , sm be an instance of the SCS problem. Set yi = h(gm (si )), for i = 1, . . . , m.
We have the following claim.

9

Claim 3. There exists a common superstring of s1 , . . . , sm of length at most ℓ if and only if
there exists a common superstring with reversal of y1 , . . . , ym of length at most 3mℓ.
Proof. (⇒) If u is a common superstring of s1 , . . . , sm , then h(gm (u)) is a common superstring
of y1 , . . . , ym . Hence, h(gm (u)) is also a common superstring with reversals of y1 , . . . , ym . If
|u| = ℓ, then |h(gm (u))| = 3mℓ.
(⇐) Let u be a common superstring with reversals of y1 , . . . , ym . We will show that, thanks to
the special form of the strings, there exists a common superstring without reversals of y1 , . . . , ym
of length not much greater than |u|.
Let π = zi1 , . . . , zim be the sequence of nodes on the path in the overlap graph G that
corresponds to u; here {i1 , . . . , im } = {1, . . . , m} and each zi is either yi or yiR . Let us construct
a new sequence of nodes π ′ , that ﬁrst contains all nodes from π of the form yi in the same order
as in π, and then all nodes from π of the form yiR , but given in the reverse order and taken
without reversal. Let u′ be the common superstring corresponding to π ′ . By Observation 1,
|u′ | ≤ |u| + m − 1. Note that u′ is an ordinary common superstring of y1 , . . . , ym .
By Observation 2, |u′ | is a multiple of 3m and u′ corresponds to a common superstring v of
s1 , . . . , sm of length |u′ |/(3m). If |u| ≤ 3mℓ, then




|u| + m − 1
|u′ |
≤
≤ ℓ.
|v| =
3m
3m
The claim provides a reduction of the decision version of the SCS problem to the decision
version of the SCS-R problem. This shows that the latter is NP-hard, hence NP-complete, as
it is obviously in NP.

6

Acknowledgments

The authors thank anonymous referees for a number of helpful comments and remarks.
This work started during a visit of Gabriele Fici to the University of Warsaw funded by the
Warsaw Center of Mathematics and Computer Science.
Gabriele Fici is supported by the PRIN 2010/2011 project “Automi e Linguaggi Formali:
Aspetti Matematici e Applicativi” of the Italian Ministry of Education (MIUR). Tomasz Kociumaka is supported by Polish budget funds for science in 2013-2017 as a research project under
the ‘Diamond Grant’ program. Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń are
supported by the Polish National Science Center, grant no 2014/13/B/ST6/00770.

References
[1] Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear approximation of shortest superstrings. Journal of the ACM, 41(4):630–647, 1994.
[2] Raphael Cliﬀord, Zvi Gotthilf, Moshe Lewenstein, and Alexandru Popa. Restricted common superstring and restricted common supersequence. In Combinatorial Pattern Matching, volume 6661 of Lecture Notes in Computer Science, pages 467–478. Springer Berlin
Heidelberg, 2011.
[3] Maxime Crochemore, Marek Cygan, Costas Iliopoulos, Marcin Kubica, Jakub Radoszewski,
Wojciech Rytter, and Tomasz Waleń. Algorithms for three versions of the shortest common
superstring problem. In Combinatorial Pattern Matching, volume 6129 of Lecture Notes in
Computer Science, pages 299–309. Springer Berlin Heidelberg, 2010.
10

[4] John Gallant, David Maier, and James A. Storer. On ﬁnding minimal length superstrings.
Journal of Computer and System Sciences, 20(1):50–58, 1980.
[5] John K. Gallant. String compression algorithms. PhD thesis, Princeton University, 1982.
[6] Theodoros P. Gevezes and Leonidas S. Pitsoulis. The shortest superstring problem. In
Optimization in Science and Engineering, pages 189–227. Springer New York, 2014.
[7] Zvi Gotthilf, Moshe Lewenstein, and Alexandru Popa. On shortest common superstring
and swap permutations. In String Processing and Information Retrieval, volume 6393 of
Lecture Notes in Computer Science, pages 270–278. Springer Berlin Heidelberg, 2010.
[8] Tao Jiang and Ming Li. Approximating shortest superstrings with constraints. Theoretical
Computer Science, 134(2):473 – 491, 1994.
[9] Tao Jiang, Ming Li, and Ding-Zhu Du. A note on shortest superstrings with ﬂipping.
Information Processing Letters, 44(4):195–199, 1992.
[10] Haim Kaplan and Nira Shafrir. The greedy algorithm for shortest superstrings. Information
Processing Letters, 93(1):13–17, 2005.
[11] John D. Kececioglu and Eugene W. Myers. Combinatiorial algorithms for DNA sequence
assembly. Algorithmica, 13(1/2):7–51, 1995.
[12] Bin Ma. Why greed works for shortest common superstring problem. Theoretical Computer
Science, 410(51):5374–5381, 2009.
[13] David Maier and James A. Storer. A note on the complexity of the superstring problem.
Technical Report 233, Princeton University, 1977.
[14] Marcin Mucha. Lyndon words and short superstrings. In Proceedings of SODA 2013, pages
958–972, 2013.
[15] Jorma Tarhio and Esko Ukkonen. A greedy approximation algorithm for constructing
shortest common superstrings. Theoretical Computer Science, 57:131–145, 1988.
[16] Jonathan S. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83(1):1–20, 1989.
[17] Esko Ukkonen. A linear-time algorithm for ﬁnding approximate shortest common superstrings. Algorithmica, 5(3):313–323, 1990.

11

