4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you want a simple cycle (a cycle without vertex repetition), or do you allow a cycle to repeat a vertex? $\endgroup$
    – Yoshio Okamoto
    Apr 21, 2011 at 14:25
  • $\begingroup$ 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. $\endgroup$
    – qwerty1793
    Apr 21, 2011 at 19:56
  • $\begingroup$ Can an edge be repeated? Out of curiosity, what's your interest in this question? $\endgroup$
    – Josephine Moeller
    Apr 21, 2011 at 23:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – qwerty1793
    Apr 22, 2011 at 8:15
  • $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Apr 26, 2011 at 15:03

1 Answer 1

Reset to default
1
$\begingroup$

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'$ 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – qwerty1793
    Apr 29, 2011 at 8:16
  • $\begingroup$ 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. $\endgroup$
    – bbejot
    Apr 29, 2011 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.