3
$\begingroup$

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?

$\endgroup$
1
1
$\begingroup$

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.

$\endgroup$

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.