First off, I know this response is not going to solve your problem. I do not know of an implementation you can use immediately. I do know that Graph::Base has some useful methods that you could use in writing your own solution. For example, methods are available to return biconnectedness and mean density statistics.

The only information (I'm no expert on graph theory!) that I can add to the NP-completeness issue comes from Steven S. Skiena's excellent The Algorithm Design Manual, page 324, which provides a thorough overview of this class of problem, including references to implementations.

"For sufficiently dense graphs, there always exists at least one Hamiltonian cycle, and further, such a cycle can be found quickly. An efficient algorithm for finding a Hamiltonian cycle in a graph where all vertices have degree >= n/2 is given in U. Manber. Introduction to Algorithms."

Here's hoping that your graphs are sufficiently dense! Happy solving.