\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Petr Kolman and Tomasz Wale\'n}
%
%
\medskip
\noindent
%
%
{\bf Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set}
%
%
\vskip 5mm
\noindent
%
%
%
%
In the last decade there has been an ongoing interest in string
comparison problems; to a large extend the interest was stimulated by
genome rearrangement problems in computational biology but related
problems appear in many other areas of computer science.  Particular
attention has been given to the problem of {\em sorting by reversals}
({\hbox{SBR}}): given two strings, $A$ and $B$, find the minimum
number of reversals that transform the string $A$ into the string $B$
(a {\em reversal} $\rho(i,j)$, $i<j$, transforms a string $A=a_1\ldots
a_n$ into a string $A'=a_1\ldots a_{i-1} a_{j} a_{j-1} \ldots a_{i}
a_{j+1} \ldots a_n$).  Closely related is the {\em minimum common
string partition} problem (\hbox{MCSP}): given two strings, $A$ and
$B$, find a minimum size partition of $A$ into substrings
$P_1,\ldots,P_l$ (i.e., $A=P_1\ldots P_l$) and a partition of $B$ into
substrings $Q_1,\ldots,Q_l$ such that $(Q_1,\ldots,Q_l)$ is a
permutation of $(P_1,\ldots,P_l)$.

Primarily the {\hbox{SBR}} problem has been studied for strings in
which every symbol appears exactly once (that is, for permutations)
and only recently attention has been given to the general case where
duplicates of the symbols are allowed. In this paper we consider the
problem $k$-{\hbox{SBR}}, a version of {\hbox{SBR}} in which
each symbol is allowed to appear up to $k$ times in each string, for
some $k\geq 1$. The main result of the paper is a
$\Theta(k)$-approximation algorithm for $k$-{\hbox{SBR}} running
in time $O(n)$; compared to the previously known algorithm for
$k$-{\hbox{SBR}}, this is an improvement by a factor of
$\Theta(k)$ in the approximation ratio, and by a factor of $\Theta(k)$
in the running time.  We approach the $k$-{\hbox{SBR}} by finding
an approximation for the $k$-{\hbox{MCSP}} first and then turning
it into a solution for $k$-{\hbox{SBR}}.  Crucial ingredients of
our algorithm are the suffix tree data structure and a linear time
algorithm for a special case of a disjoint set union problem.

\bye

.
