  The problem of efficiently computing and visualizing the structural
resemblance between a pair of protein backbones in 3D has led Bereg et al. to
pose the Chain Pair Simplification problem (CPS). In this problem, given two
polygonal chains $A$ and $B$ of lengths $m$ and $n$, respectively, one needs to
simplify them simultaneously, such that each of the resulting simplified
chains, $A'$ and $B'$, is of length at most $k$ and the discrete \frechet\
distance between $A'$ and $B'$ is at most $\delta$, where $k$ and $\delta$ are
given parameters.
  In this paper we study the complexity of CPS under the discrete \frechet\
distance (CPS-3F), i.e., where the quality of the simplifications is also
measured by the discrete \frechet\ distance. Since CPS-3F was posed in 2008,
its complexity has remained open. However, it was believed to be \npc, since
CPS under the Hausdorff distance (CPS-2H) was shown to be \npc. We first prove
that the weighted version of CPS-3F is indeed weakly \npc\, even on the line,
based on a reduction from the set partition problem. Then, we prove that CPS-3F
is actually polynomially solvable, by presenting an $O(m^2n^2\min\{m,n\})$ time
algorithm for the corresponding minimization problem. In fact, we prove a
stronger statement, implying, for example, that if weights are assigned to the
vertices of only one of the chains, then the problem remains polynomially
solvable. We also study a few less rigid variants of CPS and present efficient
solutions for them.
  Finally, we present some experimental results that suggest that (the
minimization version of) CPS-3F is significantly better than previous
algorithms for the motivating biological application.
