Over the past 10 years I.I.G., Inc. specialists have been actively pursuing investigations of NP-completeness in different areas of discrete mathematics (Appl. No. 09/006,367, US Patent No. 6,636,840 B1¹, Appl. No. 10/438,305).  

 

We make it possible for all who wish to become acquainted with the code "HCP Solver", which was developed for finding a cycle in special graphs generated with the use of generator "Leaper" (TSPLIB/HCP). The optimization algorithm "HCP Solver" is an approximate polynomial algorithm with O(N³). It is based on the concept of successive iterative decreases in cycle length, in which the iterative procedure begins with a randomly chosen cycle. As different edges of the graph are assigned the weights 0 and 1, the cycle length is determined in view of the edges with the unit weight. Each iteration is completed by replacement of several edges in the cycle. In this case the cycle length either decreases or remains unchanged. A Hamiltonian cycle in the graph exists if its length is equal to zero (H = 0). Polynomial complexity of the algorithm results from the fact that the number of iterations for each unit edge of the cycle (i.e., when a correlation is made between the unit edges of the cycle and all zero edges of the graph) is finite. The algorithm makes it possible to find a minimal cycle in the graph, provided that any separate parts of the graph (if they exist) are connected by no less than three edges. (If parts of the graph are connected by two edges, then they are called weakly connected.) In these cases the completeness of the correlated edges holds, and a necessary prerequisite is created for rendering a proper decision, viz., the cycle is minimal or it may be enhanced. Testing with the use of other types of generators and codes showed that no errors in determining the minimal cycle were found for all the graphs where the connectivity requirements were met. At the same time, if these conditions were not satisfied for any particular graph, the completeness of the correlated edges was not always reached, resulting in the aforementioned errors.  

 

Testing also demonstrated that the polynomial characteristics of the algorithm do not depend on the type of graph and on its dimension (size). This is indicative of the versatility of the algorithm (US Patent No. 6,636,840 B1¹). The time required to determine the minimal cycle in the graph of a given dimension is essentially dependent on the following three factors: the initial cycle which is randomly specified; the existence of a cycle in the graph; and graph connectivity (vertex degree of the graph and the availability of weakly connected parts). The algorithm calculating time depends critically on the initial cycle in weakly connected graphs and can vary several dozen times for the same graph.  

 

The solution algorithm for the problem "Hamiltonian Cycle in a Graph" has an important distinctive feature when compared with the general "Traveling Salesman" problem. This lies in the fact that each graph has a preconcerted boundary value of the cycle H = 0, which enables one to leave the program at any stage of its work. However, it is known that a boundary of that kind does not exist in the "Traveling Salesman" problem. For this reason, in most cases the time required by this algorithm for determining the cycle itself differs essentially from the time taken to prove that the cycle does not exist. For most of the graph types the minimal cycle is determined much faster than (we can get) data on its non-existence.  

 

As an illustration, we can refer to the average (rated at 1000 tests) time for determining the minimal cycle. The results presented in the Table were obtained for 11 graphs taken from the well-known Internet library TSPLIB using a standard PC with an Intel^® Pentium^® M 1700 MHz processor, 1 MB Cache, 400 MHz Bus Clock, and 512 MB RAM, and controlled by OS Windows^® XP Pro.  

 

Table. Average (rated at 1000 tests) running times for determining a minimal cycle in various graphs