 The associated decision problem of determining whether "K" edges can be added to a given graph to produce a Hamiltonian graph is NP-complete.Moreover, Hamiltonian completion belongs to the APX complexity class, i.e., it is unlikely that efficient constant ratio approximation algorithms exist for this problem.The problem may be solved in polynomial time for certain classes of graphs, including series-parallel graphs and their generalizations, which include outerplanar graphs, as well as for a line graph of a tree
or a cactus graph.