Abstract: We describe some necessary conditions for the existence of a Hamiltonian path in any graph (in other words, for a graph to be traceable). These conditions result in a linear-time algorithm to decide the Hamiltonian path problem for cactus graphs. We apply this algorithm to several molecular databases to report the numbers of graphs that are traceable cactus graphs.
The Hamiltonian Challenge
Finding a Hamiltonian path—a route that visits every vertex in a graph exactly once—is a notoriously difficult NP-complete problem. Because of this complexity, even the most advanced algorithms have exponential runtimes, making them impractical for large-scale datasets like those found in chemical informatics.
While much research focuses on sufficient conditions (properties that guarantee a path exists), this work focuses on necessary conditions (properties that, if missing, guarantee a path cannot exist). By establishing fast "pre-filters," we can instantly rule out non-traceable graphs and save the massive computational cost of running exponential-time algorithms on candidates that have no chance of success.
Structural Necessary Conditions
The proposed method leverages the structural properties of articulation vertices and biconnected components (BCCs) to identify bottlenecks that prevent the existence of a Hamiltonian path.
- Criticality Test: An articulation vertex is a point whose removal disconnects the graph. The "criticality" of a vertex is the number of components it splits the graph into. In any traceable graph, no vertex can have a criticality higher than 2. Intuitively, a Hamiltonian path is a "string" that must thread through the graph; if a single vertex acts as a hub for three or more separate branches, the path would have to visit that hub multiple times, violating the "visit once" rule.
- Biconnected Component Test: A biconnected component is a maximal subgraph that remains connected even if one vertex is removed. In a traceable graph, each BCC can contain at most two articulation vertices.
These tests are computationally efficient. By utilizing standard algorithms like Tarjan’s for finding biconnected components, the entire check runs in linear time ($O(V+E)$).
The Cactus Graph Case
For "cactus graphs"—where every BCC is either a single edge or a simple cycle—the author provides a complete solution. If the two conditions above are met, and if any BCC with two articulation vertices ensures those vertices share an edge, the graph is guaranteed to be traceable. This provides a definitive, linear-time algorithm for a class of graphs that frequently appears in molecular modeling.
Experimental Results
The efficiency of these conditions was evaluated on three major molecular databases: NCI-HIV (~43k compounds), NCI-2012 (~250k compounds), and ZINC (nearly 9 million compounds). Molecular graphs often possess low-degree, "tree-like" or "cactus-like" structures, making them ideal for these structural tests.
The results demonstrate the power of these conditions as a high-speed sieve. For the ZINC dataset, the necessary conditions identified almost all 9 million graphs as non-traceable, leaving only 7 graphs that required further investigation. Processing the entire ZINC database took only 70.31 seconds on a standard desktop CPU, with the actual tests adding negligible overhead compared to data parsing.
Conclusion
By breaking non-biconnected graphs into their components, we can reduce massive NP-complete problems into manageable sub-problems. While these are only necessary conditions for general graphs—meaning a graph passing the test might still be non-traceable—their performance as a filter for big data is exceptional. Future work may extend this logic to more complex graph classes beyond the cactus structure.
Summary updated