traveling salesman minimum spanning tree variant

2
votes

I'm trying to solve the following graph exercise:

In an undirected weighted graph, there are V vertices and E edges. Find the minimum weight needed to visit T(T<=V) vertices, starting from the vertex labeled as 0. Additionally, if there is an edge between two visited vertices, its weight is set to 0.

This isn't a classic traveling salesman problem, because of the added condition that if you visit two vertices, the weight of the edge between them is reduced to 0.

Approaching it with Prim's minimum spanning tree algorithm solves the problem if T == V, but since you don't necessarily have to visit all vertices, this will not always return the minimum weight.

I thought about finding the minimum spanning tree and then cutting every edge that wouldn't hinder my ability to reach all of my 'target' vertices, but that seems excessive and possibly incorrect.

Any thoughts?

EDIT: I'll give you an example. Suppose we have a graph with 4 vertices labeled 0,1,2 and 3. We have the following edges(from,to,weight): (0,1,1) (0,2,2) (1,3,4) (2,3,1) The minimum spanning tree would contain edges: (0,1,1), (0,2,2) and (2,3,1). With it, every vertex is reachable starting from 0. However, the goal of the exercise is to reach a T number of those vertices. That being said, we might, for example, only need to reach vertices 2 and 3, making the edge (0,1,1) unnecessary, and thus the total weight needed to reach our target vertices is 2+1, instead of 1+2+1.

1
algorithmgraphtraveling-salesmanminimum-spanning-treeprims-algorithm
If you need the minimum sum of weights, Prim's algorithm will give you correct partial sums as well. – Gassa
If you need to minimize the maximum edge used, you can binary search on that maximum. For a given maximum, it is easy (DFS or BFS) to find whether at least T vertices are possible to visit. – Gassa
@Gassa So if I have 10 vertices in total and I only need to visit vertices 1 4 and 7 for example, Prim's algorithm would give me minimum sum needed for that? – user2980055
Stopping Prim after T-1 iterations is not the answer. Consider a graph where 0 is connected to (1) a path where edges have length 10 (2) an edge of length 100, connected in turn to a path where edges have length 1. If T is sufficiently large, we want to use edge of length 1, but Prim will explore the 10s indefinitely. – David Eisenstat
@Gassa I added an example that should clarify the task. – user2980055

1 Answers

2
votes

Looks like your problem is essentially the Steiner tree problem, which is known to be NP-hard.

Indeed, you have an undirected weighted graph (V, E). Given T, a subset of V, you want to find a tree with minimum total weight which covers all vertices of T.

Here is an example where most obvious greedy ideas won't work. Suppose our graph is the vertices and edges of a non-regular tetrahedron ABCD where AB=BC=CA=5 and AD=BD=CD=3. If we want to connect A, B and C together, the best we can do is to use edges AD, BD and CD for a total weight of 9. If we decide not to use D, we have to take at two edges each of length 5 instead, for a total weight of 10. However, each two-vertex subset of the set ABC uses one direct edge of weight 5 (AB, BC or CA) and no edges to vertex D in the optimal solution.

(Ouch! The exact lengths are not possible in three-dimensional Euclidean geometry. Still, it will serve as an example.)