CODEWITHSUNDEEP
graphhamiltonian-cycle
Andrei
Andrei

Reputation: 5

Find a Hamiltonian cycle of no more than twice the minimum cost in O(m+n log n) in an undirected graph with costs satisfying the triangle inequality

So I've been given this task and I do not know how to use the information regarding the costs. This is the requirement and I have no additional information.

Upvotes: 0

Views: 1206

Answers (1)

Jakub Moravec
Jakub Moravec

Reputation: 191

This should be solvable by Double Tree approximation algorithm for solving TSP (Traveling Salesman Problem) / Hamilton Circuit. It requires two conditions of input graph to be met:

  • triangle inequality (you have this)
  • complete graph (Do you have this? It means there has to be an edge between every two vertexes in the graph.)

The algorithm works like this:

  • find a minimum spanning tree of input graph (there are a few algorithms for this; if you graph representation is adjestancy list, the complexity is O(e+v*log(v)))
  • Double every edge in the spanning tree - you will have multigraph (O(e))
  • make a Eulers path in this graph - if You meet a vertex for the second time, skip it and take a direct edge to next vertex (this edge exists in the graph since you have complete graph) - this should be also something like O(e + some logarithm)
  • You are done - you have found a Hamilton Circuit (and solved TSP)

This algorithm is 2-approx (the cost of the circuit is at max double the optimal solution - there is a proof for this which I can provide if you want). The worst complexity is O(e + vlog(v)) - e is number of edges, v number of vertexes... this should map to yours O(m + nlog(n)).

I could not find any good link with the algorithm explanation at the moment, I will try to provide it later.

Upvotes: 1

Related Questions