Time complexity of the conjugacy problem in relatively hyperbolic groups
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 in [Some algorithmic properties of hyperbolic groups, Izv. Akad. Nauk SSSR Ser. Mat.53(4) (1989) 814-832, 912]. Bridson and Haefliger showed in [Metrics Spaces of Non-Positive Curvature (Springer-Verlag, Berlin, 1999)] 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.
|Keywords||Algorithmic problems, conjugacy problem, relatively hyperbolic groups, time complexity|
|Journal||International Journal of Algebra and Computation|
Bumagin, I. (2015). Time complexity of the conjugacy problem in relatively hyperbolic groups. International Journal of Algebra and Computation, 25(5), 689–723. doi:10.1142/S0218196715500162