Computing Permanents and Counting Hamiltonian Cycles Faster

2023/09/27 by Li, Baitian
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2309.15422

Abstract

We show that the permanent of an n× n matrix of poly(n)-bit integers and the number of Hamiltonian cycles of an n-vertex graph can both be computed in time 2^n-Ω(√(n)), improving an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica 2019) that runs in time 2^{n - Ω(√(n/log log n))}. A key tool of our approach is to design a data structure that supports fast "r-order evaluation" of permanent and Hamiltonian cycles, which cooperates with the new approach on multivariate multipoint evaluation by Bhargava, Ghosh, Guo, Kumar, and Umans (FOCS 2022).

Related

• Below All Subsets for Some Permutational Counting Problems
• The Parity of Directed Hamiltonian Cycles
• An O(n) time algorithm for finding Hamilton cycles with high probability
• A fast algorithm on average for solving the Hamilton Cycle problem
• A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank