 Hamiltonian completion

The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.The problem is clearly NP-hard in general case (since its solution gives an answer to the NP-complete problem of determining whether a given graph has a Hamiltonian cycle).