We first show that the Traveling Salesman Problem in an n-vertex graph with average degree bounded by d can be solved in $\mathcal{O}^\star (2^{(1-\varepsilon _d)n})$ time and exponential space for a constant ed depending only on d. Thus, we generalize the recent results of Bjorklund et al. [TALG 2012] on graphs of bounded degree.#R##N##R##N#Then, we move to the problem of counting perfect matchings in a graph. We first present a simple algorithm for counting perfect matchings in an n-vertex graph in $\mathcal{O}^\star (2^{n/2})$ time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Bjorklund [SODA 2012], but relies on inclusion-exclusion principle instead of algebraic transformations. Building upon this result, we show that the number of perfect matchings in an n-vertex graph with average degree bounded by d can be computed in $\mathcal{O}^\star (2^{(1-\varepsilon _{2d})n/2})$ time and exponential space, where e2d is the constant obtained by us for the Traveling Salesman Problem in graphs of average degree at most 2d.#R##N##R##N#Moreover 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 $\mathcal{O}^\star (2^{(1-1/(3.55 d))n})$ time and ring operations, improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].
['Marek Cygan', 'Marcin Pilipczuk']
Faster exponential-time algorithms in graphs of bounded average degree