# Find all vertices that are included in a simple cycle through a fixed vertex in a directed graph

Given a directed graph $$G = (V, E)$$ and a vertex $$v \in V$$, how to find all vertices $$v'$$ such that exists a simple cycle $$v \to ... \to v' \to ... \to v$$? That is, to find the set of vertices $$V' = \{v' : \exists c, \text{c is a simple cycle in G}, v \in c, v' \in c \}$$

I found this question related: Find all cycles through a given vertex. I can first find all cycles and then union them to get $$V'$$. However, is there a more efficient way to do so?

I believe the problem is NP-hard, by reduction from the two disjoint paths problem.

The two disjoint paths problem is as follows:

Given a directed graph $$G$$ and $$(s_1,t_1),(s_2,t_2)$$, find two paths $$s_1 \leadsto t_1$$ and $$s_2 \leadsto t_2$$ that are vertex-disjoint (they have no vertex in common).

This problem is NP-hard.

We can reduce two disjoint paths to your problem. In particular, given $$G$$ and $$(s_1,t_1),(s_2,t_2)$$, we construct a new graph $$G'$$ by adding new vertices $$v,v'$$ and adding edges $$v \to s_1$$, $$t_1 \to v'$$, $$v' \to s_2$$, $$t_2 \to v$$.

Notice that any pair of vertex-disjoint paths $$s_1 \leadsto t_1$$, $$s_2 \leadsto t_2$$ will yield a simple cycle

$$v \to s_1 \leadsto t_1 \to v' \to s_2 \leadsto t_2 \to v.$$

Also, within any simple cycle $$v \leadsto v' \leadsto v$$ we can find simple paths $$s_1 \leadsto t_1$$, $$s_2 \leadsto t_2$$ that are vertex-disjoint. It follows that there exists a simple cycle $$v \leadsto v' \leadsto v$$ in $$G'$$ iff there exist two vertex-disjoint paths $$s_1 \leadsto t_1$$, $$s_2 \leadsto t_2$$ in $$G$$. So, any algorithm for solving your problem would immediately yield an algorithm for solving the two disjoint paths problem.