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 x n matrix over an arbitrary commutative ring with at most dn non-zero entries using O~*(2~((1-1/(3.55d)))~n) time and ring operations, 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~*(2~(n/2)) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Bjoerklund [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 that 1. 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) time and exponential space for a constant ε_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 Bjoerklund et al. [TALG 2012] on graphs of bounded degree.