The power word problem in graph groups

Abstract

This thesis studies the complexity of the power word problem in graph groups. The power word problem is a variant of the word problem, where the input is a power word. A power word is a compact representation of a word. It may contain powers p^x, where p is a finite word and x is a binary encoded integer. A graph group, also known as right-angled Artin group or partially commutative group is a free group augmented with commutation relations. We show that the power word problem in graph groups can be decided in polynomial time, and more precisely it is AC^0-Turing-reducible to the word problem of the free group with two generators F_2. Being a generalization of graph groups, we also look into the power word problem in graph products. The power word problem in a fixed graph product is AC^0-Turing-reducible to the word problem of the free group F_2 and the power word problem of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups C, the uniform power word problem in a graph product is CL-Turing-reducible to the word problem in the free group F_2 and the uniform power word problem in C. Finally, we show that as a consequence of our results on the power word problem the uniform knapsack problem in graph groups is NP-complete.