2014/07/16 by Inna Bumagin, Bumagin, Inna · 1 citation
Computer Science · Mathematics · #05C25 (Secondary) #20F06 #20F65 (Primary) 20F67 #57M07 #Advanced Combinatorial Mathematics #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #math.GR #msc:05C25 #msc:20F06 #msc:20F65 #msc:20F67 #msc:57M07 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1407.4528
27 pages, 3 figures
arxiv created 2014/07/16 · openalex publication_date 2014/07/16 · arxiv updated 2014/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.