# 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?

• Do you want a simple cycle (a cycle without vertex repetition), or do you allow a cycle to repeat a vertex? – Yoshio Okamoto Apr 21 '11 at 14:25
• I do not care about the cycle being simple. I should point out that the graph may also contain loop edges connecting back to the same vertex. – qwerty1793 Apr 21 '11 at 19:56
• Can an edge be repeated? Out of curiosity, what's your interest in this question? – Josephine Moeller Apr 21 '11 at 23:04
• Yes, there can be multiple edges connecting from / to the same vertices (although they must have different labels in order that 'there is at most one edge labelled x with tail v'). The question comes from computational topology where the vertices of the graph represent simple loops on a punctured 2-manifold. The edges represent the action of Dehn twists on these loops and w is a sequence of twists specifying a monodromy for a mapping torus. The torus is reducible if and only if w forms a loop somewhere in this graph. – qwerty1793 Apr 22 '11 at 8:15
• Which do you mean by “forms a cycle”: (1) The starting vertex and the ending vertex of the path are the same. (2) During the path, you visit some vertex more than once. In other words, does the path A-B-C-D-B-E (where A, B, C, D and E are vertices of a graph) “form a cycle” or not? – Tsuyoshi Ito Apr 26 '11 at 15:03

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'$ are the same, then $U_i^w = U_i^{w'}$. 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'$ have the same first $k$ elements and $w$ is processed before $w'$, then $U_k^{w'}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.
• Surely this only works if $A$ consists of a single vertex? For example consider the digraph with 2 vertices {x, y} and a directed edge labelled 1 connecting from each to the other. If $U^{1}_{1} = \lbrace x, \lbrace x,y \rbrace \rbrace$ then $v \in A$ but the word "1" doesn't form a cycle anywhere in this graph. – qwerty1793 Apr 29 '11 at 8:16
• Hello @qwerty. $U_1^1$ would consist of pairs $(v, A)$ such that such that $A$ consists of all vertices $u$ which have a path to $v$ by traveling along an edge labeled 1. In your example, $U_1^1 = \{(x, \{y\}), (y, \{x\})\}$. Thus it contains no $(v, A)$ with $v \in A$. Hope this helps make it clearer. – bbejot Apr 29 '11 at 13:05