×

A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups. (English) Zbl 1234.20048

Recently A. Myasnikov, V. Roman’kov, A. Ushakov and A. Vershik [Trans. Am. Math. Soc. 362, No. 9, 4655-4682 (2010; Zbl 1207.20026)] proved that for free metabelian groups with standard generating sets, the following ‘bounded geodesic problem’ is NP-complete: given a word in the generators and an integer \(k\), decide whether the geodesic length of the word is less than \(k\). The author and A. Rechnitzer [Groups Complex. Cryptol. 2, No. 2, 223-229 (2010; Zbl 1222.20023)] show that this problem is equivalent to the ‘geodesic problem’ (find for a word a geodesic word representing the same element) and simultaneously to the ‘length geodesic problem’ (find for a word its geodesic length).
A deterministic algorithm is given which takes as input a word of length \(n\) in the generators in the Baumslag-Solitar group \(B(1,p)=\langle a,t\mid tat^{-1}=a^p\rangle\) for any integer \(p\geq 2\), and outputs a geodesic word representing the same element, in time \(O(n)\). Consequently, the three problems mentioned above are solvable in linear time.
Recent work of V. Diekert and J. Laun [Int. J. Algebra Comput. 21, No. 1-2, 119-145 (2011; Zbl 1235.20041)] extends the result of this paper to groups of the form \(\langle a,t\mid ta^pt^{-1}=a^q\rangle\) when \(p\) divides \(q\). Their algorithm runs in quadratic time, but in the case \(p=1\) the time reduces to linear, although their algorithm is qualitatively different.

MSC:

20F65 Geometric group theory
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
20F16 Solvable groups, supersolvable groups
20F05 Generators, relations, and presentations of groups
PDFBibTeX XMLCite
Full Text: arXiv Euclid