Faster exponential-time algorithms in graphs of bounded average degree (Q2347799)

The paper provides a simple algorithm that computes a permanent of an \(m\times n\) matrix over an arbitrary commutative semiring with at most \(dm\) non-zero entries, \(d\geq 2\), using \(O^*(2^{(1-1/(3.55d))m})\) time and semiring operations, improving and simplifying the recent result of \textit{T. Izumi} and \textit{T. Wadayama} [``A new direction for counting perfect matchings'', in: Proceedings of the 53rd IEEE annual symposium on foundations of computer science, FOCS'12. Los Alamitos, CA: IEEE Computer Society. 591--598 (2012; \url{doi:10.1109/FOCS.2012.28})]. Next, a simple algorithm for counting perfect matchings in an \(n\)-vertex graph in \(O(2^{n/2})\) time and polynomial space is given. It is based on the observation that the problem of counting perfect matchings in general graphs can be reduced to a problem of counting some special types of cycle covers. The provided algorithm matches the complexity bounds of the algorithm of \textit{A. Björklund} [``Counting perfect matchings as fast as Ryser'', in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA'12. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 914--921 (2012)], but relies on the inclusion-exclusion principle instead of algebraic transformations. Finally, two combinatorial lemmas are shown that bound the number of ``Hamiltonian-like'' structures in a graph of bounded average degree: 1. a minimum weight Hamiltonian cycle in an \(n\)-vertex graph with average degree bounded by \(d\) can be found in \(O^*(2^{(1-\varepsilon_d)n})\) time and exponential space for a constant \(\varepsilon_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-\varepsilon^\prime_d)n})\) time and exponential space, for a constant \(\varepsilon^\prime_d\) depending only on \(d\).