3
$\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$

1 Answer 1

4
$\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$
9
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 9:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .