Determinant sums for undirected Hamiltonicity

DOI10.1137/110839229MaRDI QIDQ5419040zbMATH OpenOpenAlexFDO

Authors Andreas Björklund

Publication date 4 June 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian cycleMonte Carlo algorithmundirected graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: We present a Monte Carlo algorithm for Hamiltonicity detection in an $n$-vertex undirected graph running in $O^{\ast }(1.657^n)$ time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the $O^{\ast }(2^n)$ bound established for TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems. For bipartite graphs, we improve the bound to $O^{\ast }(1.414^n)$ time. Both the bipartite and the general algorithm can be implemented to use space polynomial in $n$. We combine several recently resurrected ideas to get the results. Our main technical contribution is a new reduction inspired by the algebraic sieving method for $k$-Path (Koutis ICALP 2008, Williams IPL 2009). We introduce the Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. We reduce Hamiltonicity to Labeled Cycle Cover Sum and apply the determinant summation technique for Exact Set Covers (Bj"orklund STACS 2010) to evaluate it.

Recommendations

• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• An algorithm for finding Hamilton paths and cycles in random graphs

Cited in

(51)

• A Hopf algebra for counting cycles
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Exact algorithms for finding longest cycles in claw-free graphs
• Moderate exponential-time algorithms for scheduling problems
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Narrow sieves for parameterized paths and packings
• A multivariate framework for weighted FPT algorithms
• Solving the Hamiltonian cycle problem using symbolic determinants
• Randomized parameterized algorithms for the kidney exchange problem
• End-vertices of graph search algorithms
• Path contraction faster than 2ⁿ
• The parity of set systems under random restrictions with applications to exponential time problems
• Spotting trees with few leaves
• On the equivalence among problems of bounded width
• Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
• Finding tight Hamilton cycles in random hypergraphs faster
• Counting problems in parameterized complexity
• Exact Algorithms for the Minimum Load Spanning Tree Problem
• scientific article; zbMATH DE number 7559398 (Why is no real title available?)
• The set cover conjecture and subgraph isomorphism with a tree pattern
• Exploiting sparsity for bipartite Hamiltonicity
• Path Contraction Faster Than 2^n
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Engineering motif search for large motifs
• Derandomizing isolation in space-bounded settings
• Shortest two disjoint paths in polynomial time
• Spotting trees with few leaves
• Detecting and counting small pattern graphs
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• Fast exact algorithms for survivable network design with uniform requirements
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• Approximating long cycle above Dirac's guarantee
• Approximate and randomized algorithms for computing a second Hamiltonian cycle
• Parameterized algorithms for list \(K\)-cycle
• Computing paths of large rank in planar frameworks deterministically
• Computation of Hadwiger number and related contraction problems: tight lower bounds
• Another Hamiltonian cycle in bipartite Pfaffian graphs
• Exponential-time approximation schemes via compression
• Determinantal sieving
• Computing paths of large rank in planar frameworks deterministically
• Vector TSP: a traveling salesperson problem with racetrack-like acceleration constraints
• Beyond quasi-adjoint graphs: on polynomial-time solvable cases of the Hamiltonian cycle and path problems
• Fixed-parameter tractability of maximum colored path and beyond
• Moderate exponential-time algorithms for scheduling problems
• An asymptotically fast polynomial space algorithm for Hamiltonicity detection in sparse directed graphs
• On approximate symmetric polynomials and tightness of homogenization results
• Faster edge coloring by partition sieving
• Faster exponential algorithms for cut problems via geometric data structures
• (Almost-)optimal FPT algorithm and kernel for T-cycle on planar graphs

This page was built for publication: Determinant sums for undirected Hamiltonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419040)