Path between two vertices in directed graph without cyclic vertices

Question

I have been searching online for some time but I have not found an answer.

Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic vertices can be found:

A path $v_1,\ldots , v_n$ (so $v_i\rightarrow v_{i+1}\in E$ for all $i$) has cyclic vertices when $v_{j}\rightarrow v_i \in E$ for some $i < j$.

For example: a the path $m \rightarrow v \rightarrow n\rightarrow u$ has cyclic vertices when $u\rightarrow v$.

Answer 1

My previous suggestion was wrong. So I have deleted, and will now modestly suggest another approach. Hope this works.

It seems your problem is NP hard. I will sketch a reduction from 3SAT. take a formula $\varphi$. Construct a single line of vertices, with alternatives in between. The path describes a valuation, and a verification that all clauses are true.

First, let the variables be $x_1,x_2, \dots,x_n$. Then we have vertices $u_0,u_1, \dots u_n$, $x_1, \dots x_n$, and $\bar x_1, \dots \bar x_n$. And we set edges $(u_{k-1},x_k)$, $(x_k,u_k)$ and $(u_{k-1},\bar x_k)$, $(\bar x_k,u_k)$ for $k=1,\dots,n$. A path from $u_0$ to $u_n$ sets the variables.

Now consider the $m$ clauses. We continue by having $m$ fresh vertices $v_0,v_1, \dots v_m$. Connect $u_n$ to $v_0$. Let the $k$th clause be (for instance, to avoid too many variables) $(x_3\lor \lnot x_7 \lor x_8)$. For have three vertices $c_1, c_2,c_3$ for the alternatives, and connect these in parallel between $v_{k-1}$ and $v_k$: edges $(v_{k-1},c_i)$ and $(c_i,v_k)$. Now we want to be able to choose a path via $c_i$ if the corresponding variable makes the clause true: so connect $c_1$ with a back edge to $\bar x_3$, $c_2$ with a back edge to $x_7$, and $c_3$ with a back edge to $\bar x_8$.

This somehow reminds me of a problem called Geography, which also uses a similar reduction, but is even PSPACE complete! So, check out that reduction, for reference. Your problem has no two players, and is within NP: one easily guesses and verifies a solution in polynomial time.