Faster exponential-time algorithms in graphs of bounded average degree

DOI10.1007/978-3-642-39206-1_31MaRDI QIDQ5326575zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Pilipczuk

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.3763

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Determinants, permanents, traces, other special matrix functions (15A15) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We first show that the Traveling Salesman Problem in an n-vertex graph with average degree bounded by d can be solved in O*(2^{(1-eps_d)n}) time and exponential space for a constant eps_d depending only on d, where the O*-notation suppresses factors polynomial in the input size. Thus, we generalize the recent results of Bjorklund et al. [TALG 2012] on graphs of bounded degree. 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 O*(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 O*(2^{(1-eps_{2d})n/2}) time and exponential space, where eps_{2d} is the constant obtained by us for the Traveling Salesman Problem in graphs of average degree at most 2d. Moreover we obtain a simple algorithm that counts the number of perfect matchings in an n-vertex bipartite graph of average degree at most d in O*(2^{(1-1/(3.55d))n/2}) time, improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].

Recommendations

• Faster exponential-time algorithms in graphs of bounded average degree
• The traveling salesman problem in bounded degree graphs
• Counting perfect matchings as fast as Ryser
• The Travelling Salesman Problem in Bounded Degree Graphs
• The traveling salesman problem for cubic graphs.

Cited in

(7)

• A better lower bound on average degree of online \(k\)-list-critical graphs
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Faster exponential-time algorithms in graphs of bounded average degree
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• The traveling salesman problem in bounded degree graphs
• Families with infants: speeding up algorithms for NP-hard problems using FFT
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

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 Q5326575)