Improved Approximation for the Number of Hamiltonian Cycles in Dense Digraphs

2008/12/05 by Jinshan Zhang, Zhang, Jinshan
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.0 #FOS: Computer and information sciences #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.0812.1123

20 pages

arxiv created 2009/11/21 · arxiv updated 2009/12/08

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 bound on the number of Hamiltonian cycles in a directed graph is proved, by using the ratio of the number of 1-factors. Based on this bound, we prove that our algorithm runs in expected time of O(n^8.5) for dense problems. This improves the Markov chain method, the most powerful existing method, a factor of at least n^4.5(log n)⁴ in running time. This class of dense problems is shown to be nontrivial in counting, in the sense that it is #P-Complete.

Related

• The Parity of Directed Hamiltonian Cycles
• Upper Bounds for the Number of Hamiltonian Cycles
• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• The Complexity of Determining Existence a Hamiltonian Cycle is O(n³)