Find all cycles through a given vertex

Question

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.

Answer 1

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][1]. 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

• https://stackoverflow.com/q/2908575/781723
• https://stackoverflow.com/q/2939877/781723
• What is the difference in 'logical array blocked' and array list B, and what do they represent?

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