2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot for your answer. However, as you can probably guess from the way I defined my problem, I am far from being a graph theory expert (it's a work in progress), and I am having a hard time understanding your suggestion. Could you elaborate a bit? Thanks again! $\endgroup$ – AleVe Nov 9 '16 at 17:03
  • $\begingroup$ In other words, it will be rather hard (see here) to find an efficient algorithm to solve this problem in general case exactly (due to vertex cover reduction) or even with arbitrarily close approximation (due to TSP reduction). The only thing you can hope is to try some heuristics or special cases. In fact there exists SAT-solvers that work quite well in practice despite being exponential in general. $\endgroup$ – dtldarek Nov 9 '16 at 17:13
  • $\begingroup$ Thanks again. Could you explain what was wrong about the vertex cover reduction? I have applied it to a small example and to me it seemed correct. $\endgroup$ – AleVe Dec 4 '16 at 19:14
  • $\begingroup$ !Vertex Cover Reduction $\endgroup$ – AleVe Dec 4 '16 at 19:21
  • $\begingroup$ @AleVe For whatever reason I was thinking about multiple paths that would visit the vertices "in parallel", but in your question you have only one path. It means the path has to return to the source to go back again (or use some other edge), and then it is not that easy to get the example working (althouh, I believe, possible). With the TSP there is no such problem. $\endgroup$ – dtldarek Dec 4 '16 at 23:02

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.