---
author:
- |
    Jinshan  Zhang[^1]  and Fengshan Bai[^2]\
    Department of Mathematical Sciences,   Tsinghua University,\
    Beijing 100084, China
title: '[ [An Improved FPRAS for Counting the Number of Hamiltonian Cycles in Dense Digraphs]{}]{}'
---

**Abstract**

We propose an improved algorithm for counting the number of Hamiltonian cycles in a directed graph. The basic idea of the method is sequential acceptance/rejection, which is successfully used in approximating the number of perfect matchings in dense bipartite graphs. As a consequence, a new ratio of the number of Hamiltonian cycles to the number of 1-factors is proposed. Based on this ratio, we prove that our algorithm runs in expected time of $O(n^{8.5})$ for dense problems. This improves the Markov Chain Monte Carlo method, the most powerful existing method, a factor of at least $n^{4.5}(\log n)^{4}$ in running time. This class of dense problems is shown to be nontrivial in counting, in the sense that they are $\#$P-Complete.\
\

\
\
\
****

A Hamiltonian cycle is a closed directed path that visits each vertex once and only once. In this paper we use digraph to denote directed graph. Counting the number of Hamiltonian cycles is a very challenging problem and has applications, for 