# Find all cycles through a given vertex

Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$?

I found a question that describes how to enumerate all simple cycles in $G$, but I want only the cycles that pass through $v$, so this question is a bit different. The total number of cycles in $G$ can be exponentially larger than the number of cycles passing through $v$, so just enumerating all cycles in $G$ and keeping only those that go through $v$ might be inefficient.

I'm not asking to count the number of cycles; I want an algorithm to list them all. I would like an output-sensitive algorithm, where the running time is some low-order polynomial of the number of cycles that go through $v$. I know there can be exponentially many cycles, so there is no hope for an algorithm whose running time is polynomial in the size of the graph.

Motivation: This is a cleaned-up version of Given a directed graph and a vertex v, find all cycles that go through v?. I wanted to ask the more general version of the question.

• Can't you compute a cycle basis for the graph and use that? I know the concept of a cycle basis extends to directed graphs, but I don't know details. Here is a survey – adrianN Jul 7 '16 at 13:43
• @adrianN, cool, thanks! Unfortunately that seems to only work for undirected graphs. – D.W. Jul 7 '16 at 18:34

## Solution: Modify Johnson's algorithm

Johnson's algorithm can be used to enumerate all cycles in $G$. It can be easily modified to enumerate only and all the cycles that contain $v$.

Johnson's algorithm works by numbering the vertices from $1$ to $n$, and classifying each cycle according to the smallest-numbered vertex in the cycle. It first enumerate all cycles whose smallest-numbered vertex is $1$, then all whose smallest-numbered vertex is $2$, and so on.

So, here is the modification to Johnson's algorithm. Choose a vertex numbering where $v$ receives the number $1$, and the other vertices are numbered in any order. Run Johnson's algorithm, but only enumerate the cycles whose smallest-numbered vertex is $1$. This will enumerate all the cycles containing $v$, and only the cycles containing $v$.

## Running time

The running time of this algorithm is $O((m+n)(q+1))$, where $q$ is the total number of cycles containing $v$, $n$ is the number of vertices, and $m$ is the number of edges. Its space consumption is $O(n+m)$.

## References

Here is a full citation to Johnson's paper describing the algorithm:

[Finding all the elementary circuits of a directed graph]. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

See also Find the Simple Cycles in a Directed Graph. For help understanding Johnson's algorithm, see

For pointers to implementations of Johnson's algorithm and discussion of other algorithms to find all cycles in a graph, see https://stackoverflow.com/q/546655/781723. I don't know if there's a way to modify them to enumerate only cycles that contain $v$.