Path connecting certain vertices in a neural graph

Consider a special kind of graph where the nodes can be partitioned into $$n$$ layers. There are edges only between successive layers and no edges between the nodes of any given layer. So for example, the nodes in layer-1 are connected only to the nodes in layer-2, the nodes in layer-2 are connected only to the ones in layer-3 and so on. I call such a graph a "neural graph" since neural networks happen to look like this. Also note that such graphs are bi-partite since all nodes can be colored with two colors in a way that no edge has the same color on both ends.

I'm given a set of nodes, each belonging to different layers in the graph. I need to find any path (represented as an array of nodes) that starts at layer $$1$$, ends at layer $$n$$ and necessarily goes through all these nodes in the set. If no such path exists, the algorithm should return an empty array. Any ideas for doing this efficiently?

The graph can be represented in any representation, but adjacency list is preferred.

• Is the graph full between any two layers? That is, im asking if for every $v$ in layer 1 there is an edge to any other $u$ in layer 2. Commented Jun 28, 2021 at 0:26
• No, that is not guaranteed. If it helps, what is guaranteed is that there are no "dead end nodes" meaning every node is compatible with at-least some nodes in the next layer (apart from layer $n$ of course). But the question is well-framed even without this requirement. Commented Jun 28, 2021 at 0:29
• Also, there is no node not connected to any nodes in the previous layer (apart from the nodes in layer $1$). Commented Jun 28, 2021 at 0:38
• What do you mean by "goes through all these nodes in the set"? This is the first time you mention any set, so I don't know what set you are referring to.
– D.W.
Commented Jun 28, 2021 at 3:13
• "I'm given a set of nodes, each belonging to different layers in the graph". Commented Jun 28, 2021 at 3:15

Use BFS from some arbitrary node $$v$$ in that set. Then, denote by $$u_1,\dots,u_k$$ the nodes that you want to go through, and take the path $$u_1\rightsquigarrow v\rightsquigarrow u_2 \rightsquigarrow v \rightsquigarrow\dots\rightsquigarrow u_k$$.
If you want to start at the first layer and end at the last layer then just append a path from any node on the first layer to $$v$$ and then to $$u_1$$, and also append a path from $$u_k$$ to $$v$$ to some node on the last layer.
• All paths start at layer $1$ and end at layer $n$, so they all have the same length ($n$). Commented Jun 28, 2021 at 17:59