POLYNOMIAL ALGORITHM FOR FINDING A HAMILTONIAN CYCLE ON A GRAPH

Abstract

The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which in discrete mathematics belongs to the NP complexity class and still retains interest. The aim of this work is to develop a new algorithm for solving this problem, which guarantees finding the optimal solution with polynomial time. In [1], an analysis of the current state of the problem was performed, the shortcomings of existing methods of solving were noted, and new principles and method of finding solution were presented. Known methods for solving the problem are based on the implementation of a search of possible solutions or on intuitive heuristics. Enumeration methods of solutions are unacceptable in terms of costs, since they characterized by non-polynomial time. Heuristic methods are satisfactory in time, but they do not guarantee finding the optimal solution. The popularity of enumeration methods is explained by the linear simplicity of searching in a pre-known set of acceptable solutions to the problem. But the factorial dependence of the power of the set of solutions (n-1)! from the number of vertices of the graph n makes it impossible to use such methods for large-size problems in practice. The desire to significantly reduce time costs leads to attempts to reasonably reduce the enumeration set or to the development of various heuristics, which actually indicates that it is impossible to formulate conditions for finding the optimal solution to the problem as a whole. This article describes the conditions that determine the optimal solution of the problem and a polynomial algorithm for solving the problem that embodies the described method. Finding the optimal solution to the problem is reduced to finding a closed path in a new graph of shortest paths. The shortest paths graph built on the original graph of the problem by using Dijkstra's algorithm. The enumeration set for determining the optimal solution of the problem consists of solutions that are constructed from each vertex of the source graph in the shortest paths graph. The size of this set is estimated as n(n-1). The developed parallel algorithm guarantees finding the optimal solution, significantly reduces the initial search space, and allows you to find a solution with polynomial complexity. Testing of the program showed the efficiency of the developed method and algorithm for solving the problem.