6
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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? $\endgroup$
    – Laakeri
    Commented Sep 7, 2020 at 5:56
  • 1
    $\begingroup$ @Laakeri That's exactly right. I'm interested in the problem particularly for fixed small $\mathcal{G}$. $\endgroup$
    – Steven Stadnicki
    Commented Sep 7, 2020 at 6:21
  • $\begingroup$ @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. $\endgroup$
    – Steven Stadnicki
    Commented Sep 8, 2020 at 17:58
  • $\begingroup$ @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. $\endgroup$
    – Steven Stadnicki
    Commented Sep 8, 2020 at 19:10
  • $\begingroup$ @NealYoung I do; mea culpa. $\endgroup$
    – Steven Stadnicki
    Commented Sep 8, 2020 at 21:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.