Finding a Lower Bound for k-Unbounded Hamiltonian Cycles

Methods to determine the existence of Hamiltonian Cycles in graphs have been extensively studied. However, little research has been done following cases when no Hamiltonian Cycle exists. Let a vertex be "unbounded" if it is visited more than once in a path. Furthermore, let a k-Unbounded Hamiltonian Cycle be a path with finite length that visits every vertex, has adjacent start and end vertices, and contains k unbounded vertices. I consider a variant of the Hamiltonian Cycle Problem in which the objective is to find an m-Unbounded Hamiltonian Cycle where m is the minimum value of k such that a k-Unbounded Hamiltonian Cycle exists. I provide an exponential-time brute-force algorithm for the determination of such a path. Furthermore, I present a polynomial-time heuristic for the determination of an m-Unbounded Hamiltonian Cycle that also functions as an effective heuristic for the original Hamiltonian Cycle Problem. I also consider the task on trees and discuss efficient approaches for this subclass of graphs.