A '1+1' Algorithm for the Hamilton Cycle Problem

Abstract

Deciding if a graph is a Hamilton graph, also named the Hamilton cycle problem, is important for discrete mathematics and computer science. Due to no characterization to identify Hamilton graphs effectively, there are no tractable algorithms to solve the Hamilton cycle problem. Grinberg Theorem is a necessary condition only for planar Hamilton graphs. In this paper, based on new studies on the Grinberg Theorem, in which we provided new properties of Hamilton graphs with respect to the cycle bases and improved the Grinberg Theorem to derive an efficient condition for Hamilton graphs, we present a new precise algorithm for deciding Hamilton graphs, named the '1+1' algorithm. Theoretically, the '1+1' algorithm terminates in $O(|E(G){|}^3)$ worst time complexity, where $|\text{E}(\text{G})|$ is the size of the given graph $\text{G}$.

arXiv comment24 pages, 8 figures