APPROXIMATION OF GEODESICS IN METABELIAN GROUPS

DOI10.1142/S0218196711006789MaRDI QIDQ5389112zbMATH OpenFDO

Authors Olga Kharlampovich, Atefeh Mohajeri Moghaddam

Publication date 24 April 2012

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.4035

zbMATH Keywords

algorithmic problemscomplexitygeodesic problemgeodesicsmetabelian groupsNP-complete problems

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16) Geometric group theory (20F65) Analysis of algorithms and problem complexity (68Q25)

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$.

Recommendations

• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.
• Some geodesic problems in groups
• On Weighted Geodesics in Groups
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Non-commutative lattice problems
• scientific article; zbMATH DE number 3874607
• The Length of Elements in Free Solvable Groups
• Average-case complexity and decision problems in group theory.
• A characterisation of virtually free groups.
• The word and geodesic problems in free solvable groups.

Cites work

• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The word and geodesic problems in free solvable groups.

Cited in

(5)

• Some degree and distance-based invariants of wreath products of graphs
• Approximate groups and doubling metrics
• Some geodesic problems in groups
• On Weighted Geodesics in Groups
• Dead ends on wreath products and lamplighter groups

This page was built for publication: APPROXIMATION OF GEODESICS IN METABELIAN GROUPS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5389112)