We're given a graph $G=(V,E)$, nodes $s\neq t\in V$ and a subset of nodes $U \subseteq V$ such that $\emptyset\neq U\neq V$ and $s,t \notin U$.
For every path $P$ we'll use $l(P)$ as the length of the path (number of edges) and $P(U)$ will signify the number of $U$ nodes in the path.
I need to find an algorithm that finds a path from $s$ to $t$ and travels through $U$ twice and the path is minimal from other possible paths. That is the algorithm must return a path from $s$ to $t$ such that $P(U)=2$ and if there're other possible paths $P'$ from $s$ to $t$ such that $P'(U)=2$ then $l(P')\ge l(P)$.
It is possible that there're not simple paths, that is a path may go through a node more than once.
A tip that was given in the exercise is that the problem should be solved with reduction.
I don't really see how to reduce the problem. I was thinking that first should run BFS algorithm in order to find a node that belongs to $U$. But once we find a node in $U$ I'm not sure which node from $U$ to choose next (provided $|U| \ge 2$) in order to stay in linear run time.
Best Answer
Create a new graph, which consists of 3 "copies" of $G$. Each node $(a, n)$ of this new graph represents a situation "I've got to node $a$ of original graph and have visited nodes from $U$ exactly $n$ times". $n$ can be 0, 1 or 2.
Now you need to prepare edges. Edges would be directed and the rules are quite obvious: original edge between nodes $a$ and $b$ corresponds to several edges in a new graph: $(a, m) -> (b, m + x)$ where x is 1 if $b$ belongs to $U$ and 0 otherwise.
And now you only need to find a shortest way from $(s, 0)$ to $(t, 2)$.