Faster exponential-time algorithms in graphs of bounded average degree
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\).
- Faster exponential-time algorithms in graphs of bounded average degree
- Counting perfect matchings as fast as Ryser
- On the number of Hamilton cycles in bounded degree graphs
- Approximating the permanent of graphs with large factors
- Exact algorithms for exact satisfiability and number of perfect matchings
- A Dynamic Programming Approach to Sequencing Problems
- A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
- Computing sparse permanents faster
- Counting perfect matchings as fast as Ryser
- Dynamic Programming Treatment of the Travelling Salesman Problem
- Evaluation of permanents in rings and semirings
- Exact algorithms for exact satisfiability and number of perfect matchings
- Families with infants: a general approach to solve hard partition problems
- Fourier meets M\"{o}bius: fast subset convolution
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- On the complexity of k-SAT
- On the possibility of faster \textsc{SAT} algorithms
- Partitioning into sets of bounded cardinality
- Set partitioning via inclusion-exclusion
- The traveling salesman problem in bounded degree graphs
- Trimmed Moebius inversion and graphs of bounded degree
- A better lower bound on average degree of online \(k\)-list-critical graphs
- Computing the permanent modulo a prime power
- Exploiting sparsity for bipartite Hamiltonicity
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- Counting integral points in polytopes via numerical analysis of contour integration
- Faster exponential-time algorithms in graphs of bounded average degree
- Counting perfect matchings as fast as Ryser
- The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
- Breaking the 2ⁿ barrier for 5-coloring and 6-coloring
This page was built for publication: Faster exponential-time algorithms in graphs of bounded average degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347799)
