We show that deciding if a right-angled Artin group is free-by-free is an NP-complete problem. The work is based on an earlier result by Susan Hermiller and the speaker stating that the right-angled Artin group AΓ defined by the graph Γ is free-by-free if and only if Γ is 2-breakable (a graph Γ is 2-breakable if there exists an independent set D of vertices in Γ such that every cycle in Γ contains as least two vertices from D). We reduce the 3SAT Problem to the problem of deciding if a given graph is 2-breakable (in fact, k-breakable, for any fixed k ≥ 1). Once it is shown that the problem is NP-complete, it is not difficult to show that it stays NP-complete even if we restrict it to right-angled Artin groups defined by planar graphs. Note that the more special problem of deciding if a right-angled Artin group is free-by-infinite-cyclic has a very simple answer. Namely, it follows easily from known results that the following three statements are equivalent. (1) AΓ is free-by-infinite-cyclic. (2) Γ is a forest. (3) AΓ embeds in the right angled group defined by the path of length 3. (Joint work with David Carroll and Benjamin Francisco.)
You must be logged in to post a comment.