A (1.4 + )-approximation algorithm for the
2-Max-Duo problem∗†
Yao Xu1 , Yong Chen2,1 , Guohui Lin‡1 , Tian Liu3 , Taibo Luo4,1 , and
Peng Zhang‡5
1

Department of Computing Science, University of Alberta. Edmonton, Alberta
T6G 2E8, Canada. {xu2,taibo,guohui}@ualberta.ca
Department of Mathematics, Hangzhou Dianzi University. Hangzhou,
Zhejiang 310018, China. chenyong@hdu.edu.cn
Key Laboratory of High Confidence Software Technologies (MOE), Institute of
Software, School of Electronic Engineering and Computer Science, Peking
University. Beijing 100871, China. lt@pku.edu.cn
Business School, Sichuan University. Chengdu, Sichuan 610065, China.
School of Computer Science and Technology, Shandong University. Jinan,
Shandong 250101, China. algzhang@sdu.edu.cn

2

arXiv:1702.06256v2 [] 5 Sep 2017

3

4
5

Abstract
The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the
well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted
version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the
strings, which is readily reduced into the well known maximum independent set (MIS) problem
on a graph of maximum degree ∆ ≤ 6(k − 1). In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS
problem. 2-Max-Duo was proved APX-hard and very recently a (1.6 + )-approximation was
claimed, for any  > 0. In this paper, we present a vertex-degree reduction technique, based on
which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.
1998 ACM Subject Classification F.2.2 Pattern matching; G.2.1 Combinatorial algorithms; G.4
Algorithm design and analysis
Keywords and phrases Approximation algorithm, duo-preservation string mapping, string partition, independent set
Digital Object Identifier 10.4230/LIPIcs...

1

Introduction

The minimum common string partition (MCSP) problem is a well-studied string comparison
problem in computer science, with applications in fields such as text compression and
bioinformatics. MCSP was first introduced by Goldstein et al. [16], and can be defined
as follows: Consider two length-n strings A = (a1 , a2 , . . . , an ) and B = (b1 , b2 , . . . , bn ) over
some alphabet Σ, such that B is a permutation of A. Let PA be a partition of A, which is a

∗
†
‡

This work was partially supported by NSERC Canada and NSF China.
An extended abstract appears in Proceedings of the 28th International Symposium on Algorithms and
Computation (ISAAC 2017). LIPICS 92, Article No. 66, pp. 66:1–66:12.
Correspondence authors.
© Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, Peng Zhang;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

(1.4 + )-approximation for 2-Max-Duo

multi-set of substrings whose concatenation in a certain order becomes A. The cardinality
of PA is the number of substrings in PA . The MCSP problem asks to find a minimum
cardinality partition PA of A which is also a partition of B. k-MCSP denotes the restricted
version of MCSP where every letter of the alphabet Σ occurs at most k times in each of the
two strings.
Goldstein et al. [16] have shown that the MCSP problem is NP-hard and APX-hard,
even when k = 2. There have been several approximation algorithms [10, 11, 12, 16, 18, 19]
presented since 2004, among which the current best result is an O(log n log∗ n)-approximation
for the general MCSP and an O(k)-approximation for k-MCSP. On the other hand, MCSP
is proved to be fixed parameter tractable (FPT), with respect to k and/or the cardinality of
the optimal partition [13, 17, 7, 8].
An ordered pair of consecutive letters in a string is called a duo of the string [16], which
is said to be preserved by a partition if the pair resides inside a substring of the partition.
Therefore, a length-` substring in the partition preserves ` − 1 duos of the string. With the
complementary objective to that of MCSP, the problem of maximizing the number of duos
preserved in the common partition is referred to as the maximum duo-preservation string
mapping problem by Chen et al. [9], denoted as Max-Duo. Analogously, k-Max-Duo is the
restricted version of Max-Duo where every letter of the alphabet Σ occurs at most k times
in each string. In this paper, we focus on 2-Max-Duo, to design an improved approximation
algorithm.
Along with Max-Duo, Chen et al. [9] introduced the constrained maximum induced
subgraph (CMIS) problem, in which one is given an m-partite graph G = (V1 , V2 , . . . , Vm , E)
with each Vi having n2i vertices arranged in an ni × ni matrix, and the goal is to find ni
vertices in each Vi from different rows and different columns such that the number of edges
in the induced subgraph is maximized. k-CMIS is the restricted version of CMIS where
ni ≤ k for all i. Given an instance of Max-Duo, we may construct an instance of CMIS
by setting m to be the number of distinct letters in the string A, and ni to be the number
of occurrences of the i-th distinct letter; the vertex in the (s, t)-entry of the ni × ni matrix
“means” mapping the s-th occurrence of the i-th distinct letter in the string A to its t-th
occurrence in the string B; and there is an edge between a vertex of Vi and a vertex of Vj if
the two corresponding mappings together preserve a duo. Therefore, Max-Duo is a special
case of CMIS, and furthermore k-Max-Duo is a special case of k-CMIS. Chen et al. [9]
presented a k 2 -approximation for k-CMIS and a 2-approximation for 2-CMIS, based on a
linear programming and randomized rounding techniques. These imply that k-Max-Duo
can also be approximated within a ratio of k 2 and 2-Max-Duo can be approximated within
a ratio of 2.
Alternatively, an instance of the k-Max-Duo problem with the two strings A =
(a1 , a2 , . . . , an ) and B = (b1 , b2 , . . . , bn ) can be viewed as a bipartite graph H = (A, B, F ),
constructed as follows: The vertices in A and B are a1 , a2 , . . . , an in order and b1 , b2 , . . . , bn
in order, respectively, and there is an edge between ai and bj if they are the same letter. The
two edges (ai , bj ), (ai+1 , bj+1 ) ∈ F are called a pair of parallel edges. This way, a common
partition of the strings A and B corresponds one-to-one to a perfect matching in H, and the
number of duos preserved by the partition is exactly the number of pairs of parallel edges in
the matching.
Moreover, from the bipartite graph H = (A, B, F ), we can construct another graph
G = (V, E) in which every vertex of V corresponds to a pair of parallel edges of F , and there
is an edge between two vertices of V if the two corresponding pairs of parallel edges of F
cannot co-exist in any perfect matching of H (called conflicting, which can be determined in

Y. Xu et al.

constant time; see Section 2 for more details). This way, one easily sees that a set of duos
that can be preserved together, by a perfect matching of H, corresponds one-to-one to an
independent set of G [16, 5]. Therefore, the Max-Duo problem can be cast as a special
case of the well-known maximum independent set (MIS) problem [15]; furthermore, Boria
et al. [5] showed that in such a reduction, an instance of k-Max-Duo gives rise to a graph

with a maximum degree ∆ ≤ 6(k − 1). It follows that the state-of-the-art  (∆ + 3)/5 +  approximation algorithm for MIS [2], for any  > 0, is a (6k − 3)/5 +  -approximation
algorithm for k-Max-Duo. Especially, 2-Max-Duo can now be better approximated within
a ratio of 1.8 + . Boria et al. [5] proved that 2-Max-Duo is APX-hard, similar to 2-MCSP
[16], via a linear reduction from MIS on cubic graphs. For MIS on cubic graphs, it is NP-hard
to approximate within 1.00719 [3]. Besides, Boria et al. [5] claimed that 2-Max-Duo can be
approximated within 1.6 + , for any  > 0.
Recently, Boria et al. [4] presented a local search 3.5-approximation for the general
Max-Duo problem. In the meantime, Brubach [6] presented a 3.25-approximation using a
novel combinatorial triplet matching. Max-Duo has also been proved to be FPT by Beretta
et al. [1], with respect to the number of preserved duos in the optimal partition. Most
recently, two local search algorithms were independently designed for the general Max-Duo
problem at the same time, achieving approximation ratios of 2.917 [20] and 2+  [14] for any
 > 0, respectively. They both exceed the previously the best (6k − 3)/5 +  -approximation
algorithm for k-Max-Duo, when k ≥ 3. In this paper, we focus on the 2-Max-Duo problem;
using the above reduction to the MIS problem, we present a vertex-degree reduction scheme
and design an improved (1.4 + )-approximation, for any  > 0.
The rest of the paper is organized as follows. We provide some preliminaries in Section
2, including several important structural properties of the graph constructed from the two
given strings. The vertex-degree reduction scheme is also presented as a separate subsection
in Section 2. The new approximation algorithm, denoted as Approx, is presented in Section
3, where we show that it is a (1.4 + )-approximation for 2-Max-Duo. We conclude the
paper in Section 4.

2

Preliminaries

Consider an instance of the k-Max-Duo problem with two length-n strings A = (a1 , a2 , . . . , an )
and B = (b1 , b2 , . . . , bn ) such that B is a permutation of A. Recall that we can view the
instance as a bipartite graph H = (A, B, F ), where the vertices in A and B are a1 , a2 , . . . , an
in order and b1 , b2 , . . . , bn in order, respectively, and there is an edge between ai ∈ A and
bj ∈ B if they are the same letter, denoted as ei,j . See Figure 2.1a for an example, where
A = (a, b, c, d, e, f, b, c, d, e) and B = (f, b, c, d, e, a, b, c, d, e). Note that |F | ≤ kn, and so H
can be constructed in O(n2 ) time.
The two edges ei,j , ei+1,j+1 ∈ F are called a pair of parallel edges (and they are said to be
parallel to each other); when both are included in a perfect matching of H, the corresponding
duo (ai , ai+1 ) of A is preserved. Two pairs of parallel edges are conflicting if they cannot
co-exist in any perfect matching of H. This motivates the following reduction from the
k-Max-Duo problem to the MIS problem: From the bipartite graph H = (A, B, F ), we
construct another graph G = (V, E) in which a vertex vi,j of V corresponds to the pair of
parallel edges (ei,j , ei+1,j+1 ) of F ; two vertices of V are conflicting if and only if the two
corresponding pairs of parallel edges are conflicting, and two conflicting vertices of V are
adjacent in G. One can see that a set of duos of A that can be preserved all together, a set
of pairwise non-conflicting pairs of parallel edges of F , and an independent set in G, are

XX:3

XX:4

(1.4 + )-approximation for 2-Max-Duo

1
A: a

2
b

3
c

4
d

5
e

6
f

7
b

8
c

9
d

10
e

B: f
1

b
2

c
3

d
4

e
5

a
6

b
7

c
8

d
9

e
10

(a) The bipartite graph H = (A, B, F ), where
the ten edges in bold form a perfect matching.

v1,6

v2,2

v3,3

v6,1

v2,7

v3,8

v4,4

v7,2

v4,9

v7,7

v8,3

v8,8

v9,9

v9,4

(b) The instance graph G = (V, E) of MIS, where the eight
filled vertices form an independent set.
Figure 2.1 An instance of the k-Max-Duo problem with A = (a, b, c, d, e, f, b, c, d, e) and
B = (f, b, c, d, e, a, b, c, d, e). Figure 2.1a is the graphical view as a bipartite graph H = (A, B, F ),
where a perfect matching consisting of the ten bold edges form into eight pairs of parallel edges,
corresponding to the eight preserved duos (a, b), (b, c), (c, d), (d, e), (f, b), (b, c), (c, d) and (d, e). Figure 2.1b shows the instance graph G = (V, E) of MIS constructed from H, where the independent
set {v1,6 , v2,7 , v3,8 , v4,9 , v6,1 , v7,2 , v8,3 , v9,4 } corresponds to the eight pairs of parallel edges shown in
Figure 2.1a, and consequently also corresponds to the eight preserved duos. In this instance, we have
k = 2. Any maximum independent set of G must contain some of the degree-6 vertices, invalidating
the (1.6 + )-approximation for 2-Max-Duo proposed in [5].

equivalent to each other. See Figure 2.1b for an example of the graph G = (V, E) constructed
from the bipartite graph H shown in Figure 2.1a. We note that |V | ≤ k(n − 1) and thus G
can be constructed in O(k 2 n2 ) time from the instance of the k-Max-Duo problem.
In the graph G, for any v ∈ V , we use N (v) to denote the set of its neighbors, that is,
the vertices adjacent to v. The two ordered letters in the duo corresponding to the vertex v
is referred to as the letter content of v. For example, in Figure 2.1b, the letter content of v1,6
is “ab” and the letter content of v6,1 is “f b”.
Recall from the construction that there is an edge ei,j in the graph H = (A, B, F ) if
ai = bj , and there is a vertex vi,j in the graph G = (V, E) if the parallel edges ei,j and
ei+1,j+1 are in H = (A, B, F ).
I Lemma 2.1. The graph G = (V, E) has the following properties.
1. If vi,j , vi+2,j+2 ∈ V , then vi+1,j+1 ∈ V .
2. Given any subset of vertices V 0 ⊂ V , let F 0 = {ei,j |vi,j ∈ V 0 }, A0 = {ai |ei,j ∈ F 0 },
and B 0 = {bj |ei,j ∈ F 0 }. If the subgraph H 0 = (A0 , B 0 , F 0 ) in H is connected, then all
the vertices of V 0 have the same letter content; and consequently for any two vertices
vi,j , vh,` ∈ V 0 , we have both vh,j , vi,` ∈ V .
3. For any vi,j ∈ V , we have
[
[
N (vi,j ) =
{vi0 +p,j+p ∈ V | i0 6= i} ∪
{vi+p,j 0 +p ∈ V | j 0 6= j}.
(1)
p=−1,0,1

p=−1,0,1

Y. Xu et al.

Proof. By definition, vi,j ∈ V if and only if ei,j , ei+1,j+1 ∈ F .
1. If also vi+2,j+2 ∈ V , that is, ei+2,j+2 , ei+3,j+3 ∈ F , then ei+1,j+1 , ei+2,j+2 ∈ F leading
to vi+1,j+1 ∈ V .
2. Note that an edge ei,j ∈ F if and only if the two vertices ai and bj are the same letter, and
clearly each connected component in H is complete bipartite and all the vertices are the
same letter. It follows that if the induced subgraph H 0 = (A0 , B 0 , F 0 ) in H is connected,
then all its vertices are the same letter; furthermore, all the duos starting with these
vertices have the same letter content; and therefore for any two vertices vi,j , vh,` ∈ V 0 ,
both vh,j , vi,` ∈ V .
3. For any vertex vi,j , or equivalently the pair of parallel edges (ei,j , ei+1,j+1 ) in F , which
are incident at four vertices ai , ai+1 , bj , bj+1 , a conflicting pair of parallel edges can be
one of the six kinds: to share exactly one of the four vertices ai , ai+1 , bj , bj+1 , to share
exactly two vertices ai and ai+1 , and to share exactly two vertices bj and bj+1 . The
sets of these six kinds of conflicting pairs are as described in the lemma, for example,
{vi0 −1,j−1 ∈ V | i0 6= i} is the set of conflicting pairs each sharing only the vertex bj with
the pair vi,j .
J
From Lemma 2.1 and its proof, we see that for any vertex of V there are at most k − 1
conflicting vertices of each kind (corresponding to a set in Equation (1)). We thus have the
following corollary.
I Corollary 2.2. The maximum degree of the vertices in G = (V, E) is ∆ ≤ 6(k − 1).

2.1

When k = 2

We examine more properties for the graph G = (V, E) when k = 2. First, from Corollary 2.2
we have ∆ ≤ 6.
Berman and Fujito [2] have presented an approximation algorithm with a performance
ratio arbitrarily close to (∆ + 3)/5 for the MIS problem, on graphs with maximum degree ∆.
This immediately implies a (1.8 + )-approximation for 2-Max-Duo. Our goal is to reduce
the maximum degree of the graph G = (V, E) to achieve a better approximation algorithm.
To this purpose, we examine all the degree-6 and degree-5 vertices in the graph G, and show
a scheme to safely remove them from consideration when computing an independent set.
This gives rise to a new graph G2 with maximum degree at most 4, leading to a desired
(1.4 + )-approximation for 2-Max-Duo.
We remark that, in our scheme we first remove the degree-6 vertices from G to compute an
independent set, and later we add half of these degree-6 vertices to the computed independent
set to become the final solution. Contrary to the claim that there always exists a maximum
independent set in G containing no degree-6 vertices [5, Lemma 1], the instance in Figure 2.1
shows that any maximum independent set for the instance must contain some degree-6
vertices, thus invalidating the (1.6 + )-approximation for 2-Max-Duo proposed in [5].
In more details, the instance of 2-Max-Duo, illustrated in Figure 2.1, consists of two
length-10 strings A = (a, b, c, d, e, f, b, c, d, e) and B = (f, b, c, d, e, a, b, c, d, e). The bipartite
graph H = (A, B, F ) is shown in Figure 2.1a and the instance graph G = (V, E) of the
MIS problem is shown in Figure 2.1b. In the graph G, we have six degree-6 vertices:
v2,2 , v7,7 , v3,3 , v3,8 , v8,3 and v8,8 . One can check that {v1,6 , v2,7 , v3,8 , v4,9 , v6,1 , v7,2 , v8,3 , v9,4 }
is an independent set in G, of size 8. On the other hand, if none of these degree-6 vertices
is included in an independent set, then because the four vertices v4,4 , v4,9 , v9,4 , v9,9 form
a square implying that at most two of them can be included in the independent set, the

XX:5

XX:6

(1.4 + )-approximation for 2-Max-Duo

independent set would be of size at most 6, and thus can never be a maximum independent
set in G.
Consider a duo (ai , ai+1 ) of the string A and for ease of presentation assume its letter
content is “ab”. If no duo of the string B has the same letter content “ab”, then this duo
of the string A can never be preserved; in fact this duo does not even become (a part
of) a vertex of V of the graph G. If there is exactly one duo (bj , bj+1 ) of the string B
having the same letter content “ab”, then these two duos make up a vertex vi,j ∈ V , and
from Lemma 2.1 we know that the degree of the vertex vi,j ∈ V is at most 5, since there
is no such vertex vi,j 0 with j 0 6= j sharing exactly the two letters ai and ai+1 with vi,j .
Therefore, if the degree of the vertex vi,j ∈ V is six, then there must be two duos of the
string A and two duos of the string B having the same letter content “ab”. Assume the
other duo of the string A and the other duo of the string B having the same letter content
“ab” are (ai0 , ai0 +1 ) and (bj 0 , bj 0 +1 ), respectively. Then all four vertices vi,j , vi,j 0 , vi0 ,j , vi0 ,j 0
exist in V . We call the subgraph of G induced on these four vertices a square, and denote
it as S(i, i0 ; j, j 0 ) = (V (i, i0 ; j, j 0 ), E(i, i0 ; j, j 0 )), where V (i, i0 ; j, j 0 ) = {vi,j , vi,j 0 , vi0 ,j , vi0 ,j 0 }
and E(i, i0 ; j, j 0 ) = {(vi,j , vi,j 0 ), (vi,j , vi0 ,j ), (vi0 ,j 0 , vi,j 0 ), (vi0 ,j 0 , vi0 ,j )} due to their conflicting
relationships. One clearly sees that every square has a unique letter content, which is the
letter content of its four member vertices.
In Figure 2.1b, there are three squares S(2, 7; 2, 7), S(3, 8; 3, 8) and S(4, 9; 4, 9), with
their letter contents “bc”, “cd” and “de”, respectively. The above argument says that every
degree-6 vertex of V must belong to a square, but the converse is not necessarily true, for
example, all vertices of the square S(4, 9; 4, 9) have degree 4. We next characterize several
properties of a square.
The following lemma is a direct consequence of how the graph G is constructed and the
fact that k = 2.
I Lemma 2.3. In the graph G = (V, E) constructed from an instance of 2-Max-Duo,
1. for each index i, there are at most two distinct j and j 0 such that vi,j , vi,j 0 ∈ V ;
2. if vi,j , vi,j 0 ∈ V where j 0 6= j, and vi+1,j 00 +1 ∈ V (or symmetrically, vi−1,j 00 −1 ∈ V ), then
either j 00 = j or j 00 = j 0 .
I Lemma 2.4. For any square S(i, i0 ; j, j 0 ) in the graph G = (V, E), N (vi,j ) = N (vi0 ,j 0 ),
N (vi,j 0 ) = N (vi0 ,j ), and N (vi,j ) ∩ N (vi,j 0 ) = ∅. (Together, these imply that every vertex of
V is adjacent to either none or exactly two of the four member vertices of a square.)
Proof. Consider the two vertices vi,j and vi0 ,j 0 , which have common neighbors vi,j 0 and vi0 ,j
in the square.
Note that vi,j 0 and vi,j share both the letters ai and ai+1 . If there is a vertex adjacent to
vi,j by sharing ai+1 but not ai , then this vertex is vi+1,j 00 +1 with j 00 6= j, and thus it has to
be vi+1,j 0 +1 (by Lemma 2.3). We consider two subcases: If i + 1 = i0 − 1, then j 0 + 1 = j − 1
due to k = 2. Thus, this vertex vi+1,j 0 +1 actually shares ai+1 and bj with vi,j ; also, it shares
ai0 and bj 0 +1 with vi0 ,j 0 ; and therefore it is adjacent to vi0 ,j 0 too, but not adjacent to vi,j 0 or
vi0 ,j . If i + 1 6= i0 − 1, then this vertex vi+1,j 0 +1 shares only aj+1 with the vertex vi,j ; also
it shares only bj 0 +1 with vi0 ,j 0 ; and therefore it is adjacent to vi0 ,j 0 too, but not adjacent to
vi,j 0 or vi0 ,j .
The other three symmetric cases can be discussed exactly the same and the lemma is
proved.
J
I Corollary 2.5. In the graph G = (V, E), the degree-6 vertices can be partitioned into pairs,
where each pair of degree-6 vertices belong to a square in G and they are adjacent to the
same six other vertices, two inside the square and four outside of the square.

Y. Xu et al.

XX:7

Proof. We have seen that every degree-6 vertex in the graph G must be in a square. The
above Lemma 2.4 states that the four vertices of a square S(i, i0 ; j, j 0 ) can be partitioned into
two pairs, {vi,j , vi0 ,j 0 } and {vi,j 0 , vi0 ,j }, and the two vertices inside each pair are non-adjacent
to each other and have the same neighbors. In particular, if the vertex vi,j in the square
S(i, i0 ; j, j 0 ) has degree 6, then Lemma 2.1 states that it is adjacent to the six vertices
vi−1,j 0 −1 , vi,j 0 , vi+1,j 0 +1 , vi0 −1,j−1 , vi0 ,j , vi0 +1,j+1 (see an illustration in Figure 2.2).
J
vi,j

vi−1,j ′ −1

vi,j ′

vi+1,j ′ +1

vi′ −1,j−1

vi′ ,j

vi′ +1,j+1

vi′,j ′

Figure 2.2 The square S(i, i0 ; j, j 0 ) shown in bold lines. The two non-adjacent vertices vi,j and
vi0 ,j 0 of the square form a pair stated in Corollary 2.5; they have 6 common neighbors, of which two
inside the square and four outside of the square.

I Corollary 2.6. If there is no square in the graph G = (V, E), then every degree-5 vertex is
adjacent to a degree-1 vertex.
Proof. Assume the vertex vi,j has degree 5. Due to the non-existence of any square in the
graph G and Lemma 2.1, either there is no vertex sharing exactly the two letters ai and
ai+1 with vi,j , or there is no vertex sharing exactly the two letters bj and bj+1 with vi,j . We
assume without loss of generality that there is no vertex sharing exactly the two letters ai
and ai+1 with vi,j , and furthermore assume vi0 ,j , i0 6= i, is the vertex sharing exactly the two
letters bj and bj+1 with vi,j .
It follows that N (vi,j ) = {vi−1,j 00 −1 , vi+1,j 000 +1 , vi0 −1,j−1 , vi0 ,j , vi0 +1,j+1 }, for some j 00 6= j
and j 000 6= j. Due to k = 2, this implies that ai−1 6= bj−1 = ai0 −1 and ai+2 6= bj+2 = ai0 +2 .
Therefore, there is no vertex of V sharing exactly the letter ai0 (ai0 +1 , bj , bj+1 , respectively)
with the vertex vi0 ,j , neither a vertex of V sharing exactly the two letters ai0 and ai0 +1 with
the vertex vi0 ,j . That is, the vertex vi0 ,j is adjacent to only vi,j in the graph G.
J
We say the two vertices vi,j and vi+1,j+1 of V are consecutive; and we say the two squares
S(i, i0 ; j, j 0 ) and S(i + 1, i0 + 1; j + 1, j 0 + 1) in G are consecutive. Clearly, two consecutive
squares contain four pairs of consecutive vertices. The following Lemma 2.7 summarizes
the fact that when two consecutive vertices belong to two different squares, then these two
squares are also consecutive (and thus contain the other three pairs of consecutive vertices).
I Lemma 2.7. In the graph G, if there are two consecutive vertices vi,j and vi+1,j+1 belonging
to two different squares S(i1 , i01 ; j1 , j10 ) and S(i2 , i02 ; j2 , j20 ) respectively, then i2 = i1 + 1, i02 =
i01 + 1, j2 = j1 + 1, j20 = j10 + 1, i.e., these two squares are consecutive.
Proof. This is a direct result of the fact that no two distinct squares have any member vertex
in common.
J
A series of p consecutive squares {S(i + q, i0 + q; j + q, j 0 + q), q = 0, 1, . . . , p − 1} in the
graph G, where p ≥ 1, is maximal if none of the square S(i − 1, i0 − 1; j − 1, j 0 − 1) and the
square S(i + p, i0 + p; j + p, j 0 + p) exists in the graph G. Note that the non-existence of

XX:8

(1.4 + )-approximation for 2-Max-Duo

A:

1
a

2
b

3
c

4
d

5
e

6
f

7
g

8
b

9
c

10
d

11
e

v5,13

12 13 14
h y x

v2,2

v1,7

B:

g
1

b
2

d
4

c
3

e
5

h
6

a
7

b
8

c
9

d
10

x
11

y
f
e
12 13 14

(a) The bipartite graph H = (A, B, F ).

A:

1
a

4
d

5
e

6
f

7
g

10
d

11
e

v2,8

v3,9

v8,8

v3,3

v4,4

v7,1

v8,2

v9,3

v11,5

v10,4

v9,9

(b) The instance graph G = (V, E).

12 13 14
h y x

v5,13
v4,4

B:

g
1

d
4

e
5

h
6

a
7

d
10

x
11

y
f
e
12 13 14

(c) The bipartite graph H 0 = (A0 , B 0 , F 0 )
after removal of S 2 (2, 8; 2, 8).

v1,7

v7,1

v11,5

v10,4
0

0

(d) The updated instance graph G = (V , E 0 )
after removal of S 2 (2, 8; 2, 8).

Figure 2.3 An instance of the 2-Max-Duo problem with A = (a, b, c, d, e, f, g, b, c, d, e, h, y, x)
and B = (g, b, c, d, e, h, a, b, c, d, x, y, e, f ). The bipartite graph H = (A, B, F ) is shown in Figure 2.3a
and the instance graph G = (V, E) of the MIS problem is shown in Figure 2.3b. There is a maximal
series of 2 squares S 2 (2, 8; 2, 8) in the graph G, with the four substrings “bcd”. The bipartite graph
H 0 = (A0 , B 0 , F 0 ) is shown in Figure 2.3c and the graph G0 = (V 0 , E 0 ) is shown in Figure 2.3d, on
A0 = (a, d, e, f, g, d, e, h, y, x) and B 0 = (g, d, e, h, a, d, x, y, e, f ). Applying the vertex contracting
process on G also gives the graph G0 .

the square S(i − 1, i0 − 1; j − 1, j 0 − 1) in G does not rule out the existence of some of the
four vertices vi−1,j−1 , vi0 −1,j 0 −1 , vi−1,j 0 −1 , vi0 −1,j−1 in V ; in fact by Lemma 2.1 there can be
as many as two of these four vertices existing in V (however, more than two would imply
the existence of the square). Similarly, there can be as many as two of the four vertices
vi+p,j+p , vi0 +p,j 0 +p , vi+p,j 0 +p , vi0 +p,j+p existing in V . In the sequel, a maximal series of p
consecutive squares starting with S(i, i0 ; j, j 0 ) is denoted as S p (i, i0 ; j, j 0 ), where p ≥ 1. See
for an example in Figure 2.3b where there is a maximal series of 2 consecutive squares
S 2 (2, 8; 2, 8), where the instance of the 2-Max-Duo is expanded slightly from the instance
shown in Figure 2.1.
I Lemma 2.8. Suppose S p (i, i0 ; j, j 0 ), where p ≥ 1, exists in the graph G. Then,
1. the two substrings (ai , ai+1 , . . . , ai+p ) and (ai0 , ai0 +1 , . . . , ai0 +p ) of the string A and the
two substrings (bj , bj+1 , . . . , bj+p ) and (bj 0 , bj 0 +1 , . . . , bj 0 +p ) of the string B are identical
and do not overlap;
2. if a maximum independent set of G contains less than 2p vertices from S p (i, i0 ; j, j 0 ), then
it must contain either the four vertices vi−1,j−1 , vi0 −1,j 0 −1 , vi0 +p,j+p , vi+p,j 0 +p or the four
vertices vi0 −1,j−1 , vi−1,j 0 −1 , vi+p,j+p , vi0 +p,j 0 +p .
Proof. By the definition of the square S(i + q, i0 + q; j + q, j 0 + q), we have ai+q = ai0 +q
and ai+q+1 = ai0 +q+1 ; we thus conclude that the two substrings (ai , ai+1 , . . . , ai+p ) and
(ai0 , ai0 +1 , . . . , ai0 +p ) are identical. In Figure 2.3b, for S 2 (2, 8; 2, 8) the two substrings are
“bcd”. If these two substrings overlapped, then there would be three occurrences of at least
one letter, contradicting the fact that k = 2. This proves the first item.
Note that the square S(i − 1, i0 − 1; j − 1, j 0 − 1) does not exist in the graph G, and thus

Y. Xu et al.

at most two of its four vertices (which are vi−1,j−1 , vi0 −1,j−1 , vi−1,j 0 −1 and vi0 −1,j 0 −1 ) exist
in V . We claim that if no vertex of the square S(i, i0 ; j, j 0 ) is in I ∗ , then there are exactly
two of the four vertices vi−1,j−1 , vi0 −1,j−1 , vi−1,j 0 −1 and vi0 −1,j 0 −1 exist in V and they both
are in I ∗ . Suppose otherwise there is at most one of the four vertices in I ∗ , say vi−1,j−1 ;
we may increase the size of I ∗ by removing vi−1,j−1 while adding either the two vertices
vi,j and vi0 ,j 0 or the two vertices vi0 ,j and vi,j 0 (depending on which vertices of the square
S(i + 1, i0 + 1; j + 1, j 0 + 1) are in I ∗ ), a contradiction.
Assume next that a vertex of the square S(i, i0 ; j, j 0 ) is in I ∗ , say vi,j ; then due to
maximality of I ∗ and Lemma 2.4 both vi,j and vi0 ,j 0 are in I ∗ . We claim and prove similarly
as in the last paragraph that if no vertex of the square S(i + 1, i0 + 1; j + 1, j 0 + 1) is in I ∗ , then
there are exactly two of the four vertices vi−1,j−1 , vi0 −1,j−1 , vi−1,j 0 −1 and vi0 −1,j 0 −1 exist in V
and they both are in I ∗ . If there is a vertex of the square S(i+1, i0 +1; j +1, j 0 +1) in I ∗ , then
it must be one of vi+1,j+1 and vi0 +1,j 0 +1 ; and due to maximality and Lemma 2.4 both vi+1,j+1
and vi0 +1,j 0 +1 are in I ∗ . And so on; repeatedly applying this argument, we claim and prove
similarly that if no vertex of the square S(i + p − 1, i0 + p − 1; j + p − 1, j 0 + p − 1) is in I ∗ , then
there are exactly two of the four vertices vi−1,j−1 , vi0 −1,j−1 , vi−1,j 0 −1 and vi0 −1,j 0 −1 exist in V
and they both are in I ∗ . If there is a vertex of the square S(i+p−1, i0 +p−1; j +p−1, j 0 +p−1)
in I ∗ , then it must be one of vi+p−1,j+p−1 and vi0 +p−1,j 0 +p−1 ; and due to maximality and
Lemma 2.4 both vi+p−1,j+p−1 and vi0 +p−1,j 0 +p−1 are in I ∗ .
To summarize, we proved in the above two paragraphs that if I ∗ contains less than 2p vertices from S p (i, i0 ; j, j 0 ), then there are exactly two of the four vertices vi−1,j−1 , vi0 −1,j−1 , vi−1,j 0 −1
and vi0 −1,j 0 −1 exist in V and they both are in I ∗ ; and these two vertices are either vi−1,j−1
and vi0 −1,j 0 −1 or vi0 −1,j−1 and vi−1,j 0 −1 . Symmetrically, there are exactly two of the four
vertices vi+p,j+p , vi0 +p,j+p , vi+p,j 0 +p and vi0 +p,j 0 +p exist in V and they both are in I ∗ ; and
these two vertices are either vi+p,j+p and vi0 +p,j 0 +p or vi0 +p,j+p and vi+p,j 0 +p . Clearly from
the above, when the combination is vi−1,j−1 and vi0 −1,j 0 −1 versus vi+p,j+p and vi0 +p,j 0 +p , we
may increase the size of I ∗ to contain exactly 2p vertices from S p (i, i0 ; j, j 0 ) without affecting
any vertex outside of S p (i, i0 ; j, j 0 ), a contradiction. Therefore, the only possible combinations
are vi−1,j−1 and vi0 −1,j 0 −1 versus vi0 +p,j+p and vi+p,j 0 +p , and vi0 −1,j−1 and vi−1,j 0 −1 versus
vi+p,j+p and vi0 +p,j 0 +p . This proves the second item of the lemma.
J
Suppose S p (i, i0 ; j, j 0 ), where p ≥ 1, exists in the graph G. Let A0 denote the string obtained from A by removing the two substrings (ai , ai+1 , . . . , ai+p−1 ) and (ai0 , ai0 +1 , . . . , ai0 +p−1 )
and concatenating the remainder together, and B 0 denote the string obtained from B by
removing the two substrings (bj , bj+1 , . . . , bj+p−1 ) and (bj 0 , bj 0 +1 , . . . , bj 0 +p−1 ) and concatenating the remainder. Let the graph G0 = (V 0 , E 0 ) denote the instance graph of the MIS
problem constructed from the two strings A0 and B 0 . See for an example G0 in Figure 2.3d,
where there is a maximal series of 2 consecutive squares S 2 (2, 8; 2, 8) in the graph G.
I Corollary 2.9. Suppose S p (i, i0 ; j, j 0 ), where p ≥ 1, exists in the graph G. Then, the union
of a maximum independent set in the graph G0 = (V 0 , E 0 ) and certain 2p vertices from
S p (i, i0 ; j, j 0 ) becomes a maximum independent set in the graph G = (V, E), where these
certain 2p vertices are vi,j , vi+1,j+1 , . . . , vi+p−1,j+p−1 and vi0 ,j 0 , vi0 +1,j 0 +1 , . . . , vi0 +p−1,j 0 +p−1
if vi−1,j−1 or vi+p,j+p is in the maximum independent set in G0 , or they are vi0 ,j , vi0 +1,j+1 , . . .,
vi0 +p−1,j+p−1 and vi,j 0 , vi+1,j 0 +1 , . . . , vi+p−1,j 0 +p−1 if vi0 −1,j−1 or vi0 +p,j+p is in the maximum
independent set in G0 .
Proof. Consider the construction of the graph G0 = (V 0 , E 0 ) from the two strings A0
and B 0 . Equivalently, starting with the graph G = (V, E), if we contract the p vertices
vi,j , vi+1,j+1 , . . . , vi+p−1,j+p−1 into the vertex vi+p,j+p if it exists or otherwise into a void

XX:9

XX:10

(1.4 + )-approximation for 2-Max-Duo

vertex, contract the p vertices vi0 ,j 0 , vi0 +1,j 0 +1 , . . . , vi0 +p−1,j 0 +p−1 into the vertex vi0 +p,j 0 +p if it
exists or otherwise into a void vertex, contract the p vertices vi0 ,j , vi0 +1,j+1 , . . . , vi0 +p−1,j+p−1
into the vertex vi0 +p,j+p if it exists or otherwise into a void vertex, and contract the p
vertices vi,j 0 , vi+1,j 0 +1 , . . . , vi+p−1,j 0 +p−1 into the vertex vi+p,j 0 +p if it exists or otherwise
into a void vertex, then we obtain a graph that is exactly G0 . In the graph G0 , the vertices
vi−1,j−1 and vi0 +p,j+p , if both exist in V , become adjacent to each other; so are the vertices
vi0 −1,j−1 and vi+p,j+p , if both exist in V . It follows that the maximum independent set in the
graph G0 = (V 0 , E 0 ) does not contain both vertices vi−1,j−1 and vi0 +p,j+p , or both vertices
vi0 −1,j−1 and vi+p,j+p . Therefore, starting with the maximum independent set in the graph
G0 = (V 0 , E 0 ), we can add exactly 2p vertices from S p (i, i0 ; j, j 0 ) to form an independent set
in G, of which the maximality can be proved by a simple contradiction.
We remark that in the extreme case where none of the vertices of S(i−1, i0 −1; j −1, j 0 −1)
and none of the vertices of S(i + p, i0 + p; j + p, j 0 + p) are in the maximum independent set
in G0 , we may add either of the two sets of 2p vertices from S p (i, i0 ; j, j 0 ) to form a maximum
independent set in G.
J
Iteratively applying the above string shrinkage process, or equivalently the vertex contracting process, associated with the elimination of a maximal series of consecutive squares.
In O(n) iterations, we achieve the final graph containing no squares, which we denote as
G1 = (V1 , E1 ).

3

An approximation algorithm for 2-Max-Duo

A high-level description of the approximation algorithm, denoted as Approx, for the 2-MaxDuo problem is depicted in Figure 3.1.
Algorithm Approx
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Construct the graph G = (V, E) from two input strings A and B;
while (there is a square in the graph) do
find a maximal series of squares;
locate the four identical substrings of A and B as in Lemma 2.8;
remove the corresponding substrings and accordingly update the graph;
end while
denote the resultant graph as G1 = (V1 , E1 );
set L1 to contain all degree-0 and degree-1 vertices of G1 ;
set N [L1 ] to be the closed neighborhood of L1 in G1 , i.e. N [L1 ] = L1 ∪ N (L1 );
set G2 = G1 [V1 − N [L1 ]], the subgraph of G1 induced on V1 − N [L1 ];
compute an independent set I2 in G2 by the ((∆ + 3)/5 + )-approximation in [2];
set I1 = I2 ∪ L1 , an independent set in G1 ;
return an independent set I in G using I1 and Corollary 2.9.

Figure 3.1 A high-level description of the approximation algorithm for 2-Max-Duo.

In more details, given an instance of the 2-Max-Duo problem with two length-n strings
A and B, the first step of our algorithm is to construct the graph G = (V, E), which is
done in O(n2 ) time. In the second step (Lines 2–7 in Figure 3.1), it iteratively applies the
vertex contracting process presented in Section 2 at the existence of a maximal series of
consecutive squares, and at the end it achieves the final graph G1 = (V1 , E1 ) which does not
contain any square. This second step can be done in O(n2 ) time too since each iteration
of vertex contracting process is done in O(n) time and there are O(n) iterations. In the
third step (Lines 8–10 in Figure 3.1), let L1 denote the set of singletons (degree-0 vertices)

Y. Xu et al.

XX:11
v5,13

v5,13

v2,2

v3,3

v4,4

v7,1

v8,2

v4,4
v1,7

v1,7

v7,1

(a) The independent set I1
=
{v1,7 , v7,1 , v10,4 , v11,5 , v5,13 } in G1 , consisting of all the five leaves of G1 = G0
shown in Figure 2.3d.

A:

B:

v3,9

v2,8

v9,3

v10,4

v11,5

v11,5

v10,4

v8,8

v9,9

(b) Using I1 , since v10,4 ∈ I1 , the four vertices
v2,8 , v3,9 , v8,2 , v9,3 are added to form an independent
set I in the original graph G shown in Figure 2.3b.

1
a

2
b

3
c

4
d

5
e

6
f

7
g

8
b

9
c

10
d

11
e

12 13 14
h y x

g
1

b
2

c
3

d
4

e
5

h
6

a
7

b
8

c
9

d
10

x
11

y
f
e
12 13 14

(c) The parallel edges of H corresponding to the independent
set I shown in Figure 3.2b, also correspond to the 9 preserved
duos (a, b), (b, c), (c, d), (e, f ), (g, b), (b, c), (c, d), (d, e), (e, h)
for the instance shown in Figure 2.3a.
Figure 3.2 Illustration of the execution of our algorithm Approx on the instance shown in
Figure 2.3. The independent set I1 in the graph G1 is shown in Figure 3.2a in filled circles, for which
we did not apply the state-of-the-art approximation algorithm for the MIS problem. The independent
set I in the graph G is shown in Figure 3.2b in filled circles, according to Corollary 2.9 the four
vertices v2,8 , v3,9 , v8,2 , v9,3 are added due to v10,4 ∈ I1 . The parallel edges of H corresponding to the
vertices of I are shown in Figure 3.2c, representing a feasible solution to the 2-Max-Duo instance
shown in Figure 2.3.

and leaves (degree-1 vertices) in the graph G1 ; our algorithm removes all the vertices of
L1 and their neighbors from the graph G1 to obtain the remainder graph G2 = (V2 , E2 ).
This step can be done in O(n2 ) time too due to |V1 | ≤ |V | ≤ 2n, and the resultant graph
G2 has maximum degree ∆ ≤ 4 by Corollaries 2.5 and 2.6. (See for an example illustrated
in Figure 3.2a.) In the fourth step (Lines 11–12 in Figure 3.1), our algorithm calls the
state-of-the-art approximation algorithm for the MIS problem [2] on the graph G2 to obtain
an independent set I2 in G2 ; and returns I1 = L1 ∪ I2 as an independent set in the graph
G1 . The running time of this step is dominated by the running time of the state-of-the-art
approximation algorithm for the MIS problem, which is a high polynomial in n and 1/. In
the last step (Line 13 in Figure 3.1), using the independent set I1 in G1 , our algorithm adds
2p vertices from each maximal series of p consecutive squares according to Corollary 2.9, to
produce an independent set I in the graph G. (For an illustrated example see Figure 3.2b.)
The last step can be done in O(n) time.
The state-of-the-art approximation algorithm for the MIS problem on a graph with
maximum degree ∆ has a performance ratio of (∆ + 3)/5 + , for any  > 0 [2].
I Lemma 3.1. In the graph G1 = (V1 , E1 ), let OPT1 denote the cardinality of a maximum
independent set in G1 , and let SOL1 denote the cardinality of the independent set I1 returned
by the algorithm Approx. Then, OPT1 ≤ (1.4 + )SOL1 , for any  > 0.

XX:12

(1.4 + )-approximation for 2-Max-Duo

Proof. Let L1 denote the set of singletons (degree-0 vertices) and leaves (degree-1 vertices) in
the graph G1 ; our algorithm Approx removes all the vertices of L1 and their neighbors from
the graph G1 to obtain the remainder graph G2 = (V2 , E2 ). The graph G2 has maximum
degree ∆ ≤ 4 by Corollaries 2.5 and 2.6. Let OPT2 denote the cardinality of a maximum
independent set in G2 , and let SOL2 denote the cardinality of the independent set I2
returned by the state-of-the-art approximation algorithm for the MIS problem. We have
OPT1 = |L1 | + OPT2 and OPT2 ≤ (1.4 + )SOL2 , for any  > 0. Therefore,
OPT1 ≤ |L1 | + (1.4 + )SOL2 ≤ (1.4 + )(|L1 | + SOL2 ) = (1.4 + )SOL1 .
This proves the lemma.

J

I Theorem 3.2. The 2-Max-Duo problem can be approximated within a ratio arbitrarily
close to 1.4, by a linear reduction to the MIS problem.
Proof. We prove by induction. At the presence of maximal series of p consecutive squares, we
perform the vertex contracting process iteratively. In each iteration to handle one maximal
series of p consecutive squares, let G and G0 denote the graph before and after the contracting
step, respectively. Let OPT0 denote the cardinality of a maximum independent set in G0 ,
and let SOL0 denote the cardinality of the independent set I 0 returned by the algorithm
Approx. Given any  > 0, from Lemma 3.1, we may assume that OPT0 ≤ (1.4 + )SOL0 .
Let OPT denote the cardinality of a maximum independent set in G, and let SOL denote
the cardinality of the independent set returned by the algorithm Approx, which adds 2p
vertices from the maximal series of p consecutive squares to the independent set I 0 in G0 ,
according to Corollary 2.9, to produce an independent set I in the graph G. Lemma 2.8
states that OPT = OPT0 + 2p. Therefore,
OPT = OPT0 + 2p ≤ (1.4 + )SOL0 + 2p ≤ (1.4 + )(SOL0 + 2p) = (1.4 + )SOL.
This proves that for the original graph G = (V, E) we also have OPT ≤ (1.4 + )SOL
accordingly. That is, the worst-case performance ratio of our algorithm Approx is 1.4 + ,
for any  > 0. The time complexity of the algorithm Approx has been determined to be
polynomial at the beginning of the section, and it is dominated by the time complexity of
the state-of-the-art approximation algorithm for the MIS problem. The theorem is thus
proved.
J

4

Conclusion

In this paper, we examined the Max-Duo problem, the complement of the well studied
minimum common string partition problem. Based on an existing linear reduction to the
maximum independent set (MIS) problem [16, 5], we presented a vertex-degree reduction
technique for the 2-Max-Duo to reduce the maximum degree of the constructed instance
graph to 4. Along the way, we uncovered many interesting structural properties of the
constructed instance graph. This degree reduction enables us to adopt the state-of-theart approximation algorithm for the MIS problem on low degree graphs [2] to achieve a
(1.4 + )-approximation for 2-Max-Duo, for any  > 0.
It is worth mentioning that our vertex-degree reduction technique can be applied for
k-Max-Duo with k ≥ 3. In fact, we had worked out the details for k = 3, to reduce the
maximum degree of the constructed instance graph from 12 to 10, leading to a (2.6 + )approximation for 3-Max-Duo, for any  > 0. Nevertheless, the (2.6 + )-approximation is
superseded by the (2 + )-approximation for the general Max-Duo [14].

Y. Xu et al.

It would be worthwhile to investigate whether the maximum degree can be further
reduced to 3, by examining the structural properties associated with the degree-4 vertices.
On the other hand, it is also interesting to examine whether a better-than-1.4 approximation
algorithm can be designed directly for the MIS problem on those degree-4 graphs obtained
at the end of the vertex contracting process.
Acknowledgements. All authors are supported by NSERC Canada. Additionally, Chen
is supported by the NSFC Grants No. 11401149, 11571252 and 11571087, and the China
Scholarship Council Grant No. 201508330054; Liu is supported by the NSFC Grant Nos.
61370052 and 61370156. Luo is supported by the NSFC Grant No. 71371129 and the PSF
China Grant No. 2016M592680; Lin and Zhang are supported by the NSFC Grant No.
61672323.
References
1
2
3

4

5

6

7

8

9

10

11

S. Beretta, M. Castelli, and R. Dondi. Parameterized tractability of the maximum-duo
preservation string mapping problem. Theoretical Computer Science, 646:16–25, 2016.
P. Berman and T. Fujito. On approximation properties of the independent set problem for
low degree graphs. Theory of Computing Systems, 32:115–132, 1999.
P. Berman and M. Karpinski. On some tighter inapproximability results. In Proceedings
of the of 26th International Colloquium on Automata, Languages and Programming (ICALP’99), pages 200–209, 1999.
N. Boria, G. Cabodi, P. Camurati, M. Palena, P. Pasini, and S. Quer. A 7/2-approximation
algorithm for the maximum duo-preservation string mapping problem. In Proceedings of
the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), volume 54
of LIPIcs, pages 11:1–11:8, 2016.
N. Boria, A. Kurpisz, S. Leppänen, and M. Mastrolilli. Improved approximation for the
maximum duo-preservation string mapping problem. In Proceedings of the 14th International Workshop on Algorithms in Bioinformatics (WABI 2014), volume 8701 of LNBI,
pages 14–25, 2014.
B. Brubach. Further improvement in approximating the maximum duo-preservation string
mapping problem. In Proceedings of the 16th International Workshop on Algorithms in
Bioinformatics (WABI 2016), volume 9838 of LNBI, pages 52–64, 2016.
L. Bulteau, G. Fertin, C. Komusiewicz, and I. Rusu. A fixed-parameter algorithm for
minimum common string partition with few duplications. In Proceedings of the 13th International Workshop on Algorithms in Bioinformatics (WABI 2013), volume 8126 of LNBI,
pages 244–258, 2013.
L. Bulteau and C. Komusiewicz. Minimum common string partition parameterized by
partition size is fixed-parameter tractable. In Proceedings of the Twenty-Fifth Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA’14), pages 102–121, 2014.
W. Chen, Z. Chen, N. F. Samatova, L. Peng, J. Wang, and M. Tang. Solving the maximum
duo-preservation string mapping problem with linear programming. Theoretical Computer
Science, 530:1–11, 2014.
X. Chen, J. Zheng, Z. Fu, P. Nan, Y. Zhong, S. Lonardi, and T. Jiang. Assignment of
orthologous genes via genome rearrangement. IEEE/ACM Transactions on Computational
Biology and Bioinformatics, 2:302–315, 2005.
M. Chrobak, P. Kolman, and J. Sgall. The greedy algorithm for the minimum common
string partition problem. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2004) and the 8th

XX:13

XX:14

(1.4 + )-approximation for 2-Max-Duo

12
13

14

15
16

17
18

19
20

International Workshop on Randomization and Computation (RANDOM 2004), volume
3122 of LNCS, pages 84–95, 2004.
G. Cormode and S. Muthukrishnan. The string edit distance matching problem with moves.
ACM Transactions on Algorithms, 3:2:1–2:19, 2007.
P. Damaschke. Minimum common string partition parameterized. In Proceedings of the
8th International Workshop on Algorithms in Bioinformatics (WABI 2008), volume 5251
of LNBI, pages 87–98, 2008.
B. Dudek, P. Gawrychowski, and P. Ostropolski-Nalewaja. A family of approximation
algorithms for the maximum duo-preservation string mapping problem. arXiv, 1702.02405,
2017.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-completeness. W. H. Freeman and Company, San Francisco, 1979.
A. Goldstein, P. Kolman, and J. Zheng. Minimum common string partition problem:
Hardness and approximations. In Proceedings of the 15th International Symposium on
Algorithms and Computation (ISAAC 2004), volume 3341 of LNCS, pages 484–495, 2004.
H. Jiang, B. Zhu, D. Zhu, and H. Zhu. Minimum common string partition revisited. Journal
of Combinatorial Optimization, 23:519–527, 2012.
P. Kolman and T. Waleń. Reversal distance for strings with duplicates: Linear time approximation using hitting set. In Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA 2006), volume 4368 of LNCS, pages 279–289,
2006.
P. Kolman and T. Waleń. Approximating reversal distance for strings with bounded number
of duplicates. Discrete Applied Mathematics, 155:327–336, 2007.
Y. Xu, Y. Chen, T. Luo, and G. Lin. A local search 2.917-approximation algorithm for
duo-preservation string mapping. arXiv, 1702.01877, 2017.

