2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ @Yos I've edited the answer to make it more clear. I think it's not important which letter ($n$ or $m$) to use in the last sentence, meaning is the same: number of times I've visited nodes from $U$ so far. I'd rather use different letters because the contexts are different: $n$ was used when I described the nodes of the graph, $m$ - when describing edges creation rules. But you can substitute $m$ with $n$. $\endgroup$ – lesnik Nov 2 '17 at 11:00
  • 1
    $\begingroup$ @Yos So, the nodes of the new graph have form $(a, n)$, where $a$ is a node of original graph, and $n$ is a number 0, 1, 2. "2" here is not $|U|$ or $|G|$. This is a number of times you have visited nodes from $U$ along some path. Suppose you move $a->b$ in original graph, having not visited any nodes from $U$ yet, and $b$ belongs to $U$. This will correspond to transition $(a, 0) -> (b, 1)$ in a new graph. Your purpose is to reach $t$ in original graph having visited nodes from $U$ exactly twice: that would correspond to reaching node $(t, 2)$ in a new graph. $\endgroup$ – lesnik Nov 2 '17 at 15:49
  • 1
    $\begingroup$ @Yos You can imagine the new graph having 3 layers. Each layer looks very much like original graph, except that edges are directed now, so instead of one edge $a - b$ there are two edges "back" and "forth". And if the edge leads to a node from $U$ it actually leads one layer higher (if there is a higher layer). $\endgroup$ – lesnik Nov 2 '17 at 15:57
  • 1
    $\begingroup$ @Yos. Nice picture. Some amendments required. All nodes on first level should have form $(a, 0)$, all nodes on second level: $(a, 1)$, etc. New graph has no "blue" undirected edges, only grey directed edges. Edge $s - t$ should be replaced with two edges $(s, n)->(t, n)$ and $(t, n) -> (s, n)$ on each level (total 6 edges). Edge $s - u_1$ should be replaced with directed edges $(s,0)->(u_1, 1)$, $(u_1, 0) ->(s, 0)$, etc., total 5 edges. And so on. $\endgroup$ – lesnik Nov 3 '17 at 9:10
  • 1
    $\begingroup$ @Yos Now for every path on original graph there is a corresponding path on a new graph, which goes through the same letters, and increases level each time the original path visits a node from $U$. (Well, if original path visits a node from $U$ third time, there would be no corresponding path in a new graph because there are no nodes like $(a, 3)$ in there, but we are not interested in such paths.) And for each path on new graph there is a corresponding path on original graph. Path from $(s, 0)$ to $(t, 2)$ corresponds to path from $s$ to $t$ with 2 visits of $U$ nodes. $\endgroup$ – lesnik Nov 3 '17 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.