How to determine if a labelled digraph contains a cycle with given labels? Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at most 1 edge labelled $x$ connecting out of $v$, i.e. there is at most one edge labelled $x$ with tail $v$. 

Let $w$ be a word made using elements of $X$ as letters. For a given vertex $v$, $w$ defines a path through G by following the correctly labelled edges (if they exist) starting at $v$. I would like to determine if a $w$ forms a cycle anywhere within G.


  Is there a more efficient way to determine if there is a $v \in V$ such that $w$ forms a cycle when started at $v$ than checking where the path $w$ terminates for every starting vertex?
The following suggestion may speed up your solution if you need to answer queries for many different words.

Define the set $U_i^w$ to be a set of pairs $(v, A)$ where $A \subseteq V$ and $v$ is reached by some vertex in $A$ after traversing the first $i$ labels of the word $w$.  Then to check if $w$ forms a cycle in the graph, loop through all $(v, A) \in U_{|w|}^w$ and if ever $v \in A$, then a cycle does exist.

Note that if the first $i$ elements of $w$ and $w&#39;$ are the same, then $U_i^w = U_i^{w&#39;}$.  Also, $U_0^w = \{(v, \{v \} ) | v \in V \} $.

As you process queries, dynamically construct a trie such that each node (including the inner nodes) stores $U_i^w$ for some $i$ and $w$.  This way, if $w$ and $w&#39;$ have the same first $k$ elements and $w$ is processed before $w&#39;$, then $U_k^{w&#39;}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.