Difference between Hamiltonian path and ST
I was reading up algorithms for finding the minimum spanning tree(in case of weighted graphs) and for finding if a graph has a hamiltonian path(which depends on the presence of a hamiltonian cycle). I got everything messed up. So whats the difference between a hamiltonian path and a spanning tree? Both cover all the vertices in the graph. While we can have efficient algorithms to find a spanning tree(perhaps a minimum spanning tree), why cant we have algorithms for finding a hamiltonian circuit?? We can keep on adding and removing one edge at a time till we reach a cycle and perhaps, we could find a hamiltonian cycle??
Answer
The two problems are quite different. Think of the minimum spanning tree as the problem of connecting places where you only have to pay once to build the road, but you can use it as many times as you like. It's easy to come up with the cheapest configuration of roads (e.g. by Kruskal's algorithm) that allows you to travel from any place to any other.
The Hamiltonian cycle, on the other hand, wants you to minimize the actual travel distance, i.e. every move from one place to another counts. (It also asks you never to visit a place twice, but that's a minor detail.) This problem is fundamentally non-local, in the sense that you cannot tell whether you're doing the right thing just by locally exploring the options for the next step. By comparison, the greedy MST algorithm is guaranteed to pick the right next edge to add to the tree at every step.
By the way, nobody says that "we cannot have efficient algorithms for HP". It might be that we just haven't found one yet :-)