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