I am dealing with directed graphs that consist of two types of (uniquely non-negative weighted) node, "OR" nodes and "AND" nodes. Given a single source and a single target, I want to find the shortest path (with minimal weight) between them.
"OR" nodes are regular nodes: they can be visited if at least one of their parents has been visited first. "AND" nodes have a constraint: all their parents must have been visited first.
Now, when trying to find the shortest path to an "AND" node, simply summing up the node's parents' weight won't work, since they might have ancestors in common, which would lead to the ancestors' weight being accounted for several times.
Does anybody know of an algorithm that would solve this? And if yes, what would be its complexity? I have not been able to find much in the literature. I probably am not using the right terminology. Or?
Thanks a lot!
We can reduce the travelling salesman problem (which is strongly NP-hard) to your problem. To check what is the best path that starts and ends at $v$, add a dummy vertex $v_\mathrm{and}$ of type "and" with edges to all the vertices of $V$ and their lengths being equal to the respective distances in $G$, then run a query for your problem between $v$ and $v_\mathrm{and}$. Minimum over the answers for all vertices of $V$ will be the answer to the TSP problem.
I hope this helps $\ddot\smile$
Edit: Removed the part about vertex cover, which was incorrect.