Using FPGAs to solve the Hamiltonian cycle problem

The Hamiltonian Cycle (HC) problem is an important graph problem with many applications. The general backtracking algorithm normally used for random graphs often takes far too long in software. With the development of field-programmable gate arrays (FPGAs), FPGA-based reconfigurable computing offers promising choices for acceleration. This research exploits the idea of an instance-specific approach and proposes a system design based on a reconfigurable hardware implementation for solving the HC problems. In our implementation, only one FPGA is used, on an internal PCI-based board. The experimental results show that the reconfigurable hardware approach yields significant runtime speedups over the conventional approach, although the clock rate of the FPGA hardware is much slower than that of the workstation running the software solver.