Some algorithmic problems in group theory

In this thesis we consider two different types of algorithmic problems over groups. In the first part, we consider the geodesic problem in finitely generated free metabelian groups as well as finitely generated wreath products. In particular, we show that there exists a 2-approximation algorithm for the geodesic problem in finitely generated free metabelian groups. We also show that the geodesic problem in the restricted wreath product of a finitely generated non-trivial group A with a finitely generated abelian group B containing the free abelian group of rank 2, is NP-hard. Moreover, we prove that if the geodesic problem is polynomially decidable in A, then there exists a Polynomial Time Approximation Scheme for the geodesic problem in the restricted wreath product of A and B.In the second part of the thesis (Chapter 3 and Chapter 4), we consider equations over groups. We show that minimal solutions to systems of equations over finitely generated free groups with alphabetic constraints are polynomially compressible in the size of the input. We also give a polynomial bound on the lengths of minimal solutions of quadratic equations over torsion-free hyperbolic groups as well as toral relatively hyperbolic groups.Dans cette thèse, nous nous intéressons à deux types différents de problèmes algorithmiques sur les groupes. Dans la première partie, nous considérons le problème des géodésique dans les groupes métabeliens libres de type fini ainsi que dans les produits en couronne de type fini. En particulier, nous prouvons qu’il y a un algorithme de 2-approximation pour le problème des géodésique dans les groupes métabeliens libres de type fini. Nous montrons aussi que le problème des géodésique dans le produit en couronne restreint d’un groupe de type fini et non-trivial A avec un groupe abélien de type fini B contenant le groupe abélien libre de rang 2 est NP-difficile. En outre, nous prouvons que si le problème des géodésique est décidable dans A en temps polynomial, alors il existe un “Polynomial Time Approximation Scheme” pour le problème des géodésique dans le produit en couronne restreint de A et B.Dans la deuxième partie (Chapitre 3 and Chapitre 4), nous considérons des équations dans des groupes. Nous montrons que les solutions minimales des systèmes d’équations dans les groupes libres de type fini avec des contraintes alphabétiques sont polynomialement compressibles en la taille des données. Nous donnons aussi une majoration polynomiale sur la taille des solutions minimales des équations quadratiques dans les groupes hyperboliques sans torsion et dans les groupes relativement hyperboliques toriques