Faster exponential-time algorithms in graphs of bounded average degree

We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n×nn×n matrix over an arbitrary commutative ring with at most dn   non-zero entries using O⋆(2(1−1/(3.55d))n)O⋆(2(1−1/(3.55d))n) time and ring operations,1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].Second, we present a simple algorithm for counting perfect matchings in an n  -vertex graph in O⋆(2n/2)O⋆(2n/2) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations.Third, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that1.a minimum weight Hamiltonian cycle in an n-vertex graph with average degree bounded by d   can be found in O⋆(2(1−εd)n)O⋆(2(1−εd)n) time and exponential space for a constant εdεd depending only on d;2.the number of perfect matchings in an n-vertex graph with average degree bounded by d   can be computed in O⋆(2(1−εd′)n/2) time and exponential space, for a constant εd′ depending only on d. The algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree.