Traveling Salesman Problem .. MST or not?

LithiumDex · Post by **LithiumDex** » Mon Apr 23, 2007 8:24 pm

I've heard this problem is NP Complete, but looking at it... it seems like it could be solved with a simple minimum spanning tree algorithm -- can someone explain this?

sohel · Post by **sohel** » Mon Apr 23, 2007 8:34 pm

It is an NP complete problem!!

Can you explain your simple MST approach?

LithiumDex · Post by **LithiumDex** » Mon Apr 23, 2007 8:37 pm

Don't we just have an undirected graph of N nodes, each edge having a weight? Why would you think MST would fail for this?

sohel · Post by **sohel** » Mon Apr 23, 2007 8:55 pm

Travelling Salesman Problem
Given N nodes and the costs of the edges between every pair of nodes, what is the cheapest round-trip route that visits every node exactly once and then returns to the starting node?

Minimum Spanning Tree
Given a graph consiting of N nodes, find a connected subgraph which has N-1 edges and sum of these edges is minimized.

So these two things aren't exactly identical. The degree of every node in the subgraph of a TSP is exactly 2, but this isn't true for the subgraph of a MST.

LithiumDex · Post by **LithiumDex** » Mon Apr 23, 2007 8:57 pm

I understand, thanks.

stubbscroll · Post by **stubbscroll** » Tue Apr 24, 2007 1:35 am

Actually, MST can be used (as part of the algorithm) to approximately solve TSP when the triangle inequality holds for the graph.

http://en.wikipedia.org/wiki/Travelling ... cial_cases