Introduction
The Hamiltonian Cycle Problem (HCP) is a foundational challenge in graph theory, asking whether a path exists that visits every vertex in a graph exactly once before returning to the origin. While the undirected version of this problem has been extensively studied, the Directed Hamiltonian Cycle Problem (DHCP)—where edges possess specific directions—has historically received less attention. Despite its complexity, DHCP is critical for applications ranging from DNA mapping in bioinformatics to strategic modeling in game theory.
Because DHCP is NP-complete, no known algorithm can solve every instance efficiently. Existing approaches typically rely on general-purpose solvers like Concorde (optimized for the Traveling Salesman Problem) or pure Boolean satisfiability (SAT) encodings. However, these methods often struggle with specific directed graph topologies. This paper introduces AP-SAT, a hybrid algorithm that combines fast combinatorial optimization with the logical rigor of SAT solvers to achieve state-of-the-art performance.
The AP-SAT Algorithm
AP-SAT utilizes a multi-stage pipeline designed to solve easy instances rapidly while maintaining the completeness required for difficult cases. The pipeline consists of four primary phases:
- The Assignment Problem (AP) Step: The algorithm initially treats the graph as an Assignment Problem, seeking a set of cycles that cover all vertices. This step is computationally efficient, with a complexity of $O(n^3)$, but it often produces multiple disjoint subcycles rather than a single Hamiltonian cycle.
- Karp-Steele Patching (KSP): To resolve subcycles quickly, the algorithm employs a KSP heuristic that attempts to "patch" these smaller loops into a single global cycle.
- Perturbation and Iteration: If patching fails, the algorithm perturbs the costs of the edges used in the previous AP solution. This forces the solver to explore alternative cycle sets. This process can iterate up to $n$ times.
- Incremental SAT Solving: For instances that resist heuristic methods, AP-SAT employs a SAT solver (MiniSat). Rather than encoding the entire "no-subcycle" constraint into a massive, unwieldy formula, the algorithm adds "no-good" constraints incrementally. Each time the SAT solver identifies a solution containing subcycles, a new rule is added to forbid that specific configuration, narrowing the search space dynamically.
Experimental Methodology
The researchers evaluated AP-SAT against a comprehensive suite of 4,266 instances:
- Random Graphs ($G_{n,m}$): Ranging from 100 to 1,600 vertices with varying edge densities to observe scaling behavior.
- TSPLIB: A standard benchmark containing 26 asymmetric Traveling Salesman Problem instances.
- DIMACS Challenge Instances: 240 non-random instances derived from various problem generators (e.g.,
amat,coin,stilt), representing complex, structured graphs.
Key Insights and Results
Performance and Scalability
AP-SAT demonstrated significant superiority over existing methods, including the Martello algorithm and the industry-standard Concorde TSP solver. Notably, while Concorde failed to solve 16 of the DIMACS instances within a one-hour time limit, AP-SAT failed on only 7. On random graphs, the average running time of AP-SAT scales polynomially ($O(n^3)$). This efficiency stems from the fact that the expensive SAT component is rarely triggered; the AP and KSP steps solve the majority of instances almost instantaneously.
Refining the Phase Transition
A significant contribution of this research is the experimental refinement of the "phase transition" in random directed graphs. This transition represents the edge density threshold where a graph shifts from being almost certainly non-Hamiltonian to almost certainly Hamiltonian. While theoretical models previously predicted this transition at a degree parameter of $c = 1.0$, the authors' experimental evidence suggests the transition actually occurs earlier, at approximately $c \approx 0.9$.
Limitations and Future Directions
Despite its success, AP-SAT faces challenges with undirected (symmetric) graphs. In these instances, the AP solver frequently identifies numerous two-vertex cycles (back-and-forth edges), which forces the SAT solver to process an excessive number of subcycle elimination constraints. Additionally, certain highly structured "stilt" instances caused the SAT solver to exceed memory limits.
Future work may involve extending the incremental subcycle elimination technique to the Traveling Salesman Problem (TSP) itself. By integrating these logical constraints into traditional TSP solvers, it may be possible to achieve similar performance gains in broader combinatorial optimization tasks.
Summary updated