  If $u$ and $v$ are two conjugate elements of a hyperbolic group then the
length of a shortest conjugating element for $u$ and $v$ can be bounded by a
linear function of the sum of their lengths, as was proved by Lysenok. Bridson
and Haefliger showed that in a hyperbolic group the conjugacy problem can be
solved in polynomial time. We extend these results to relatively hyperbolic
groups. In particular, we show that both the conjugacy problem and the
conjugacy search problem can be solved in polynomial time in a relatively
hyperbolic group, whenever the corresponding problem can be solved in
polynomial time in each parabolic subgroup. We also prove that if $u$ and $v$
are two conjugate hyperbolic elements of a relatively hyperbolic group then the
length of a shortest conjugating element for $u$ and $v$ is linear in terms of
their lengths.
