<p>This question came up in the analysis of the puzzle game <a href="https://www.thinkfun.com/products/swish/" rel="nofollow noreferrer"><em>Swish</em></a>. One way of representing the solvability problem is this: given a directed graph <span class="math-container">$G$</span> where each edge of the graph is labeled with an element of a group <span class="math-container">$\mathcal{G}$</span> (in this case, <span class="math-container">$D_4$</span>, but the question obviously makes sense for any group), is there a vertex <span class="math-container">$v\in G$</span> and a simple cycle in the graph starting at vertex <span class="math-container">$v$</span> where the product of the edges in the cycle is the identity of <span class="math-container">$\mathcal{G}$</span> (or some specified element <span class="math-container">$g\in\mathcal{G}$</span>)?</p>
<p>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?</p>

CC BY-SA 4.0
2020-09-07T05:56:24.087Z
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?
Laakeri
CC BY-SA 4.0
2020-09-07T06:21:09.013Z
@Laakeri That's exactly right. I'm interested in the problem particularly for fixed small $\mathcal{G}$.
Steven Stadnicki
CC BY-SA 4.0
2020-09-08T17:58:58.840Z
@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.
Steven Stadnicki
CC BY-SA 4.0
2020-09-08T19:10:44.003Z
@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.
Steven Stadnicki
CC BY-SA 4.0
2020-09-08T21:15:05.913Z
@NealYoung I do; mea culpa.
Steven Stadnicki
<cc.complexity-theory><graph-theory><gr.group-theory>
Computational complexity of finding paths with specified product in a (group-labeled) directed graph
Steven Stadnicki
# Computational complexity of finding paths with specified product in a (group-labeled) directed graph

(Asked by: username_0 on 2020-09-07)

This question came up in the analysis of the puzzle game [*Swish*](https://www.thinkfun.com/products/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?

**Tags:** cc.complexity-theory, graph-theory, gr.group-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 That's exactly right. I'm interested in the problem particularly for fixed small $\mathcal{G}$.  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_0**: @NealYoung I do; mea culpa.  

---

## 0 answers

