Over the last decads I.I.G., Inc. specialists have been actively pursuing investigations of NPcompleteness in different areas of discrete mathematics (Appl. No. 09/006,367, US Patent No. 6,636,840 B1 ^{}^{}^{}^{}^{1}^{}, 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^{3}). 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 ^{}^{}^{}^{}^{1}^{}). 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 nonexistence.
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 wellknown 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
#

Name

Type

Average execution time

Minimal cycle length

1

alb1000

hcp

0.72 sec

H = 0

2

alb2000

hcp

3.29 sec

H = 0

3

alb3000a

hcp

8.36 sec

H = 0

4

alb3000b

hcp

8.02 sec

H = 0

5

alb3000c

hcp

8.43 sec

H = 0

6

alb3000d

hcp

8.48 sec

H = 0

7

alb3000e

hcp

8.03 sec

H = 0

8

alb4000

hcp

17.84 sec

H = 0

9

alb5000

hcp

30.85 sec

H = 0

10

leaper 7x8 on board 15x106

hcp

5.98 sec

H = 0

11

leaper 6x7 on board 13x76

hcp

55.17 sec

H > 0

