Instead of "path", Let us use "walk" for a sequence of edges which joins a sequence of vertices (that can revisit vertices and edges). We will reserve "path" for its usual meaning, a walk in which all vertices are distinct.
This answer describes a linear algorithm that given a directed graph $G=(V,E)$ and $U \subseteq V$, finds if there is a walk that visits every node in $U$. The main idea is to take advantage of the longest distances from the root in a directed acyclic graph (DAG) to speed up the search for a path.
Reduce to a rooted DAG
Compute the condensation of $G$, a DAG that which is attained when each strongly-connected component of $G$ is contracted to a single vertex. This DAG is called "the meta-graph of strongly connected components" in D.W.'s answer. The computation can be done by any one of the linear-time algorithms.
Denote the condensation of $G$ by $G'=(V', E')$. Let $U'$ be the vertices in $V'$ that represent the strongly-connected components that contain at least one vertices in $U$. Since $G'$ is acyclic, any walk in $G'$ is a path.
Add a vertex $s$ to $G'$ and an edge from $s$ to every root of $G'$. (A vertex in a DAG is called root if there is no incoming edge to it). Now $G'$ is a connected DAG with a unique root, $s$.
The problem is transformed to finding if there is a (walk) path in $G'$ that visits every node in $U'$.
Replacing $(G, V, E, U)$ with $(G', V', E', U')$, we will assume henceforth that $G$ is is a connected DAG with the unique root $s$.
Longest distance from $s$ to each vertex
For each $v\in V$, let $dist[v]$ be the longest distance from $s$ to $v$, i.e., the biggest number of edges in a path from $s$ to $v$.
Here is a simple and useful property of $dist$. If there is an edge or a path from vertex $v_1$ to $v_2$, then $dist[v_1]<dist[v_2]$.
Compute $dist$ using dynamic programming as follows.
- Initialize a hash table/hash map $dist$ with $dist[v] = 0$ for all $v\in V$.
- Create a topological order of all vertices. This can be done by some linear-time algorithm.
- For every vertex $v\in V$ in topological order,
- For every adjacent vertex $w$ of $v$:
- if $dist[w] < dist[v] + 1$:
$\quad dist[w] = dist[v] + 1$.
Check if there is a path from $u_i$ to $u_{i+1}$
Sort all vertices in $U$ by $dist[\cdot]$. Since $dist[v]$ is an integer between $0$ and $|V|$ for every vertex $v$, this sorting can be done in linear time with counting sort. (We can also simply select all vertices in $U$ from the sequence obtained in the step 2 above.)
Let $U=\{u_1, u_2, \cdots\}$, $dist[u_i]\le dist[u_{i+1}]$.
For $i$ from $1$ up to $|U|$, do the following:
- If $dist[u_i]=dist[u_{i+1}]$, there is no wanted path. The algorithm ends.
- do a breadth-first search (or a depth-first search) starting with $u_i$, in order to check if there is a path from $u_i$ to $u_{i+1}$. To speed up the search, whenever we see an edge that ends at a vertex $w\not=u_{i+1}$ such that $dist[w]\ge dist[u_{i+1}]$, we will remove that edge from $G$ and ignore $w$, since for all $j\ge i$, no path from $u_j$ to $u_{j+1}$ can include that edge. (Note that edge must start at a vertex with $dist$ smaller than $dist[u_{i+1}]$.)
- If $u_{i+1}$ has not been reached, there is no wanted path. The algorithm ends.
When the algorithm have reached here, we know there is path from $u_i$ to $u_{i+1}$ for all $i$. Connecting all paths together, we obtain a path that passes all vertices in $U$.
Note the for-loop accesses each edge in $U$ at most once. Hence it takes linear time to complete the for-loop.
Linear-time complexity
It takes linear time to do each step of the three steps above. Hence this algorithm runs in linear time.
Some of the steps in the algorithm can be implemented faster. For example, when we compute the condensation of the original $G$ using Kosaraju's algorithm, we may obtain the topological order of $V'$ and $U'$ in parallel. We may also compute $dist[\,]$ at the same time.
