Approximation of Geodesics in Metabelian Groups

Abstract

It is known that the bounded Geodesic Length Problem in free metabelian groups is NP-complete (in particular, the Geodesic Problem is NP-hard). We construct a 2-approximation polynomial time deterministic algorithm for the Geodesic Problem. We show that the Geodesic Problem in the restricted wreath product of a finitely generated non-trivial group with a finitely generated abelian group containing $Z^2$ is NP-hard and there exists a Polynomial Time Approximation Scheme for this problem. We also show that the Geodesic Problem in the restricted wreath product of two finitely generated non-trivial abelian groups is NP-hard if and only if the second abelian group contains $Z^2$.

10 pages, 1 figure; International Journal of Algebra and Computation (IJAC), 2011

Cited by in corpus (2)

• Some degree and distance-based invariants of wreath products of graphs
• Dead ends on wreath products and lamplighter groups