Time complexity of the conjugacy problem in relatively hyperbolic groups
arXiv:1407.4528
Abstract
If and are two conjugate elements of a hyperbolic group then the length of a shortest conjugating element for and 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 and are two conjugate hyperbolic elements of a relatively hyperbolic group then the length of a shortest conjugating element for and is linear in terms of their lengths.
arXiv comment27 pages, 3 figures
References in corpus (5)
- Relative hyperbolicity and relative quasiconvexity for countable groups
- The conjugacy problem for relatively hyperbolic groups
- Finite generating sets of relatively hyperbolic groups and applications to geodesic languages
- Presenting parabolic subgroups
- Conjugacy Search Problem for Relatively Hyperbolic Groups