9
$\begingroup$

Consider a layerwise directed acyclic graph DAG, $G=(V,E)$ and two vertices $s$ and $t$. $s$ is connected to all vertices in $L_0$, $L_0$ is connected to all vertices in $L_1$ and so forth. Consider all possible paths between $s$ and $t$. In addition there is a set $R$ of requirements whose elements are of the form of tuples $(a,b)$ interpreted as : if node $a$ is present in a path, $b$ must also be present. For example, in the figure if a path contains the red node, the blue node must also be present. Similarly if a path contains the green node, the yellow node must also be present. All tuples $(a,b)$ are between vertices which have edges directly connecting them, i.e., $(a,b) \in E$, hence they must be in successive layers. How to find the shortest path from $s$ to $t$ which satisfies all requirements in $R$.

There is a linear time algorithm that find the shortest paths in a DAG by relaxing all the edges in topological sorted order. However how to consider the requirement set $R$?

enter image description here

$\endgroup$
  • $\begingroup$ Does the dependence go both ways? For instance, if you include the yellow node, must you also include the green node? If yes, Marco's answer requires also deleting arcs into the second node of a pair from any node other than its partner. $\endgroup$ – prubin Oct 3 at 20:43
  • $\begingroup$ No, one way @prubin $\endgroup$ – ephemeral Oct 4 at 5:54
14
$\begingroup$

Wouldn't eliminating all outgoing arcs from the red node except to the blue node, and eliminating all arcs from the green node except to the yellow node, or in general, eliminating all arcs from $a$ except those to $b$ already do the job?

$\endgroup$

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.