2013/02/15 by Marek Cygan, Marcin Pilipczuk, Cygan, Marek +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1302.3763
openalex publication_date 2013/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-\epsd)n) time and exponential space for a constant \epsd 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*(2n/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-\eps2d)n/2) time and exponential space, where \eps2d 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].