Kourovka Notebook Problem 16.72

Definitions and mathematical statement

A group $G$ is fully residually free if, for every finite subset $S\subseteq G\setminus\{1\}$, there exist a free group $F$ and a homomorphism $\varphi:G\to F$ such that $\varphi(s)\ne 1$ for every $s\in S$. It is finitely generated if $G=\langle X\rangle$ for some finite subset $X\subseteq G$.

Question (source formulation). Does there exist an exponential-time algorithm which, given a finitely generated fully residually free group $G$, outputs a JSJ-decomposition of $G$? The algorithm is required to work for every group in this class.

A graph-of-groups decomposition describes $G$ as the fundamental group of a graph of groups. The requested JSJ-decomposition is a particular kind of such decomposition, but the supplied record does not specify the allowed edge groups, relative subgroups, or the precise JSJ convention. It also does not specify an effective input representation, an input-length measure, an output encoding, or the intended meaning of exponential time. Thus the question above preserves the source's target, but a fully precise complexity statement requires these choices. In particular, no finite-presentation input convention or specific exponential bound is imposed here.

The source reports that an algorithm was obtained in the 2005 reference listed below; its question concerns the exponential-time requirement. This historical assertion is supplied source information and is not independently verified here.

Short English statement

The problem asks whether a JSJ-decomposition of every finitely generated fully residually free group can be computed in exponential time. The source reports an existing algorithm, but leaves the JSJ convention and the computational representations and complexity bound unspecified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $701264$, exact source code catalogue entry, titled Kourovka Notebook Problem 16.72. The registry labels the problem open; this label is supplied curation, not an independently verified mathematical assessment.
• The Kourovka Notebook (Unsolved Problems in Group Theory), original problem 16.72, 16th issue (2006); also attributed by the supplied record to the 21st issue edition (2026), arXiv identifier 1401.0300v48. Proposed by A. G. Myasnikov and O. G. Kharlampovich. The supplied collection description names E. I. Khukhro and V. D. Mazurov as editors.
• O. Kharlampovich and A. Myasnikov, contribution in Algorithms, Languages, Logic, Contemporary Mathematics, AMS, volume $378$ (2005), pp. 87--212. The supplied record cites this contribution for the existence of an algorithm, but supplies no contribution title or external link. This citation has not been independently checked.