Path in digraph passing through given set of vertices

Question

Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f passing through all vertices from W; if yes, return any of such paths. By "path" i mean path in the most general sense: repetitions of edges and vertices are allowed.

Unfortunately no information about graph is known: it needn't be connected in any sense, it might have oriented cycles, etc.

My idea was to modificate DFS somehow but i didn't manage to proceed. Any ideas and hints will be highly appreciated. Thanks in advance.

Answer 1

Decompose the graph into strongly connected components. You get a DAG, each vertex of which represents a strongly connected component. Let $S,F$ be the strongly connected components containing $s,f$. There is a path from $s$ to $f$ if there is a path from $S$ to $F$ in the decomposition (this includes the case $S=F$). Any such path can only pass through (genuine) vertices in the connected components that appear on the path from $S$ to $F$ in the decomposition, and conversely we can arrange it to pass through all of them (since you allow the paths not to be simple). This leads to a simple criterion for your problem – can you state it?