Minimum distance in an undirected weighted graph to cover k nodes using teleportations

Question

I have been practicing problems on graphs and shortest paths and I encountered a problem that I'm struggling to understand.

Can you give me any tips and/or can you confirm that I got the general concept of the problem right?

In a given undirected weighted graph $G=(V,E)$ and an integer $k$ and edges with positive weights, the starting point is node $v_0$. You have to visit every node from $v_0, v_1, v_2, \dots, v_{k-1}$. If you visit any of those $k$ nodes you are allowed to create a portal in them. You can only make portals in those $k$ nodes. From one portal you can teleport to any other without any cost to the path.

You have to create a function double shortestPath(int k) that returns a shortest path to visit all $k$ nodes using teleportation system (if necessary).

I sketched this graph and tried to understand the problem here. Lets say we have to visit nodes 0,1 and 2.

Edited (Please check the reply to see better example of the problem)

My approach is this: If I take this route $0 \to 5$ (cost 1) then $5 \to 4$ (cost 2), $4 \to 2$ (cost 3) and then jump from $2 \to 0$ and go $0 \to 1$ (cost 9). This is the shortest path using teleportations.

Can someone tell me if I understood this problem correctly and maybe give some tips on how to implement the algorithm?

Answer 1

You can do this in polynomial time with a greedy algorithm by always traveling to the nearest un-visited terminal, and dropping a portal in every terminal.

The crucial observations are these:

1. Since it's free to drop a portal and use one, you always put a portal in each of the terminals.
2. There is no point traveling anywhere but to a terminal.
3. When you move to a terminal, you always travel from the closest portal.

Let $G = (V, E, w)$ be the input graph and $T \subseteq V$ be your $k$ terminals, with $v_0 \in T$.

Start with $T' = \{v_0\}$. While $|T'|<k$, pick a terminal not in $T'$ that is of shortest distance from $T'$ and add it to $T'$. Sum up the distances traveled in total.

Notice that you can preprocess your graph in $O(t^2 (n+m))$ time to get a new (complete) graph $G' = (T, E', w')$ with only vertices from $T$ and where the edge $t_1t_2$ has $w'(t_1, t_2) = \text{dist}_G(t_1, t_2)$.

Edit: This answer is updated. The previous answer was based on Steiner Tree.

Answer 2

Reply to @Pål GD:

Lets try and apply Steiner algorithm to this graph where $b,e$ and $g$ are terminals. Starting point will be node $b$. Closest of nodes $e$ and $g$ to the node $b$ is node $e$ with cost of $6+7=13$. So, for now, we have a subgraph with nodes $b \rightarrow c \rightarrow e $ . Finally we need $g$ in our subgraph that will make a minimum spanning tree which would cover terminal nodes. The closest node in our graph to the node $g$ is $c$ with the cost $15$. Thus our final subgraph will look like this:

And this subgraph indeed covers all the terminal nodes with the cost of 28. But in the exercise with teleportation we are allowed to make a portal in nodes $b,e$ and $g$ after we visit them. In this case, our starting point is $b$ and we make a portal in it. Next node we visit is $c$ with the cost $6$, after that we go to the node $e$ with the cost $6+7=13$ and now we're allowed to make a portal in node $e$. So in this case it's better to teleport back to the node $b$ and go to the node $f$ via $c$ than going back from $e$ to $c$ and then to $f$ with the cost of $10$. Cost to $f$ in this case would be additional $9$ to current $13$ and we have total cost for now of $22$. Now we visit $d$ and finally $g$ with additional cost of $12$ and the final cost would be $34$ with our teleportation system.

With the Steiners algorithm I could use the subgraph to traverse it with portals (still have no effective idea of changing Steiners algorithm to work like this). But the problem is, if we take a look at the graph we see that the best possible subgraph would be made of nodes $b,a,d,g,c$ and $e$. Lets explain why.

We're starting from the node $b$ and traverse all to the node $g$ via nodes $a$ and $d$ with the cost of $16$. We have now two portals: one in $g$ and oen in $b$ so we're allowed to teleport back to $b$ with the cost of $0$. Then we can traverse to the node $e$ via nodes $c$ and $e$ with the cost of $13$ and the final cost would be $29$ which is better than $34$ of the previous case.

This would apply in the case I understood Steiner algorithm correctly and would be pleased if You could confirm it.