# Computational complexity of finding paths with specified product in a (group-labeled) directed graph

This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $$G$$ where each edge of the graph is labeled with an element of a group $$\mathcal{G}$$ (in this case, $$D_4$$, but the question obviously makes sense for any group), is there a vertex $$v\in G$$ and a simple cycle in the graph starting at vertex $$v$$ where the product of the edges in the cycle is the identity of $$\mathcal{G}$$ (or some specified element $$g\in\mathcal{G}$$)?

The problem is obviously in NP, but I don't immediately see a reduction from anything like 3-SAT, or a dynamic programming approach to the problem that would solve it in polynomial time. What's the complexity of this problem?

• Is the cycle required to be simple? If not, then it can be solved in time $O(|V(G)|^2 |\mathcal{G}|)$ by considering all starting points and doing dynamic programming over (vertex of G, element of $\mathcal{G}$) pairs. If it is required to be simple, then hamiltonian cycle can be reduced to it if allow arbitrary $\mathcal{G}$. So I guess the hard version which you are interested in is where $\mathcal{G}$ is fixed/small compared to $G$, and a simple cycle is required? Sep 7, 2020 at 5:56
• @Laakeri That's exactly right. I'm interested in the problem particularly for fixed small $\mathcal{G}$. Sep 7, 2020 at 6:21
• @D.W. 'Based' here just means a cycle and basepoint; since the product around the cycle can depend on where it's started from (if $\mathcal{G}$ is non-Abelian) I felt like it was worth calling out explicitly that this isn't strictly speaking just a question about the cycle. Sep 8, 2020 at 17:58
• @D.W. Very nearly so! I was also looking for the vertex (and have tweaked your edit to say so), but that obviously has no bearing on the possible NP-completeness of the problem. Sep 8, 2020 at 19:10
• @NealYoung I do; mea culpa. Sep 8, 2020 at 21:15