4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Apr 20 at 14:24
3
$\begingroup$

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

enter image description here

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.

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

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.