Faster exponential-time algorithms in graphs of bounded average degree
Marek Cygan, Marcin Pilipczuk · Information and Computation · 2014
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 × n matrix over an arbitrary commutative ring with at most dn non-zero entries using O ⋆ ( 2 ( 1 − 1 / ( 3.55 d ) ) 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 ⋆ ( 2 n / 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 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 Björklund et al. [TALG 2012] on graphs of bounded degree.