# 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

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.

• I liked the idea of 3SAT reduction - tried with HP but couldn't articulate it well enough. Upvoted. – lox Apr 22 at 10:00
• I love this cool reduction with enlightening illustration. Upvoted the question as well. – Apass.Jack Apr 24 at 4:20