# Path between two vertices in directed graph without cyclic vertices

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

• Ok, I think I understand your question now. I have edited your clarifications into the question. Feel free to edit some more if I got something wrong. – Discrete lizard Apr 20 at 14:24

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