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

Recently \textit{A. Myasnikov, V. Roman'kov, A. Ushakov} and \textit{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 \textit{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 \textit{V. Diekert} and \textit{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.