Determinant Sums for Undirected Hamiltonicity

Andreas Björklund

Source-linked AI summary

Determinant Sums for Undirected Hamiltonicity

Andreas Björklund

arXiv:1008.0541v1Aug 3, 2010cs.DS

TL;DR

The paper addresses Hamiltonicity detection in undirected graphs, a problem related to the Traveling Salesman Problem and known to be NP-hard. It reduces Hamiltonicity to weighted cycle-cover counting and uses determinant evaluation with randomized polynomial identity testing, yielding faster Monte Carlo algorithms.

Problem
Hamiltonicity detection is an NP-hard problem and a special case of the Traveling Salesman Problem.
Method
The approach counts weighted directed cycle covers over characteristic-two fields, evaluates them with determinants, and uses randomized fingerprinting to test whether the resulting polynomial is zero.
Results
O^*(1.657^n) time detects Hamiltonicity in undirected graphs, while a given independent set of size i yields O^*(2^(n−i)) time and lightest positive-integer-weight TSP tours take O^*(w1.657^n) time.
Takeaways & Limitations
The algorithm can be implemented using polynomial space, extending the determinant-based approach beyond Hamiltonicity detection to weighted TSP optimization.
Takeaways & Limitations
The approach crucially requires undirected graphs and efficient randomized polynomial identity testing, and does not appear able to approximate the number of solutions.

Abstract

from arXiv · show

We present a Monte Carlo algorithm for Hamiltonicity detection in an $n$-vertex undirected graph running in $O^*(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^*(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^*(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örklund STACS 2010) to evaluate it.

1 Introduction

The paper develops randomized algorithms that improve exponential-time Hamiltonicity detection, including a stronger bound for graphs with a large independent set. Its approach combines algebraic sieving, weighted cycle-cover counting, and determinant summation, while retaining polynomial space with additional care.

Problem setting: Hamiltonicity asks whether an undirected n-vertex graph contains a cycle visiting every vertex exactly once.The problem is a special case of TSP and has an O(n^2 2^n) dynamic-programming bound from the early 1960s.
Main results: O*(1.657^n) time detects Hamiltonicity in undirected graphs using a Monte Carlo algorithm with no false positives.False negatives occur with probability exponentially small in n.
Main results: O*(2^(n−i)) time detects Hamiltonicity when the graph has a given independent set of size i.The algorithm has no false positives and exponentially small false-negative probability.
Extensions: The algorithm extends to integer-weight TSP in O*(w1.657^n) time, where w is the sum of all edge weights.This extension uses selfreducibility and has exponentially small error probability.
Limitations: With extra care, the Hamiltonicity algorithms use polynomial space, but they rely on randomized polynomial identity testing and do not support directed graphs or solution counting.The paper also states that the strategy does not seem able to approximate the number of solutions.
Approach: The method counts weighted directed cycle covers over characteristic-two fields and uses determinants to evaluate the resulting sums.Hamiltonian cycles are contained among the cycle covers, and multivariate-polynomial sieving helps isolate them.

2 Preliminaries

The paper defines labeled cycle-cover sums and shows how characteristic-two cancellation removes non-Hamiltonian covers while preserving Hamiltonian contributions. Determinant-based identities then evaluate these sums with exponential dependence on labels and polynomial dependence on graph size.

A cycle cover selects exactly one outgoing and one incoming arc per vertex; Hamiltonian cycle covers consist of one cycle spanning all vertices.
The Labeled Cycle Cover Sum weights cycle covers whose arc labels are nonempty, pairwise disjoint, and collectively exhaust the label set.
2.1 Cycle Cover Cancelation in Characteristic Two: Bidirectionality, characteristic two, and an s-oriented mirror function make labeled non-Hamiltonian cycle covers cancel in dual pairs.
2.2 Preserving Hamiltonian Contributions: Hamiltonian cycles can retain nonzero contributions because opposite orientations around the special vertex s use different variables, yielding unique monomials.
2.2 Preserving Hamiltonian Contributions: Random evaluation over a finite field tests whether the resulting polynomial is identically zero, with a nonzero fingerprint certifying that at least one Hamiltonian cycle exists.
2.3 Determinants and Inclusion–Exclusion: Determinant summation evaluates the labeled cycle-cover sum using characteristic-two determinant–permanent equivalence, with runtime exponential in labels but polynomial in graph size.

3 The Reduction

The reduction transforms Hamiltonicity into a Labeled Cycle Cover Sum on a smaller bidirected graph, using vertices as labels and finite-field evaluation. A bipartite specialization yields an O*(2^(n/2)) algorithm, while random partitions and label handling give the general O*(1.657^n) bound and an O*(2^(n-i)) bound when an independent set of size i is supplied.

3 The Reduction: The reduction partitions G into two equal vertex sets, constructs a bidirected graph D on one half, and uses the other half as labels in a Labeled Cycle Cover Sum.For bipartite graphs, the cycle alternates between the two parts, making this partition immediate.
3.1 Warm-up: Hamiltonicity in Bipartite Graphs: Λ(D, V2, f) is the zero polynomial if and only if the graph has no Hamiltonian cycle, establishing the correctness of the bipartite reduction.Hamiltonian cycles contribute distinct monomials, while opposite orientations are handled through the special vertex s.
3.2 The General Case: In the general case, a random equal partition is used because the vertices encountered alternately by a Hamiltonian cycle are not known in advance.Arcs whose endpoints lie in V1 are treated as unlabeled by V2, while other arcs are labeled by vertices of V2 or extra labels Lm.
3.2 The General Case: The generalized polynomial is zero if and only if the relevant Hamiltonian-cycle subset is empty, with each cycle contributing distinct monomials across orientations and label permutations.The construction expands cycles in D through labeled and unlabeled arcs, requiring all labels to be used and the unlabeled arcs to correspond to edges in G.
3.2.2 Analysis: O*(1.657^n) is obtained by optimizing the maximum number of unlabeled arcs and the number of repetitions, while a supplied independent set of size i gives O*(2^(n−i)).The analysis sets mmax = 0.205 and uses r = n^O(1)2^0.024n runs; for an independent set, mmax = n − 2i.

4 Polynomial Space

The paper modifies its algorithm to use only polynomial space by replacing exponential-space tabulation with walk-based computations and matrix products. The resulting identities preserve the needed characteristic-two cancellations while enabling efficient evaluation.

4 Polynomial Space: Polynomial space is obtained by replacing simple-path tabulation with inclusion–exclusion over walks, which can be evaluated efficiently.The walk formulation supports the same sieving goal while avoiding exponential-space storage.
4 Polynomial Space: The function g is defined on selected arcs and labels, and is zero elsewhere, providing the walk-based analogue of f.This construction underlies the polynomial-space evaluation of the Labeled Cycle Cover Sum.
4 Polynomial Space: Lemma 11 establishes that the walk-based construction yields the corresponding expression for the original function f.Its proof rewrites q(g, r) using characteristic-two determinant–permanent equivalence and cycle-cover interpretations.
4 Polynomial Space: Characteristic-two cancellation removes contributions from incomplete label unions and overlapping label sets, while degree filtering isolates the relevant monomial.The proof uses even multiplicities for cancellation and selects the term whose total degree matches |L|.
4 Polynomial Space: The coefficient can be recovered by evaluating q(g, r) at |L| values and applying Lagrange interpolation, without tabulating g exponentially.The inner sum is evaluated in polynomial time and space; matrix products such as B A^l B^T provide the needed computations.

5 TSP with Bounded Integer Weights

The paper extends its algebraic method to bounded-integer-weight TSP by encoding tour weights as powers of an auxiliary variable. Fourier interpolation then identifies the smallest weight whose coefficient is nonzero.

5 TSP with Bounded Integer Weights: TSP seeks the Hamiltonian cycle with minimum total weight, and each edge contribution is multiplied by y^ℓ(uv) to encode that weight algebraically.The resulting monomials sort Hamiltonian cycles by their total edge weight.
5 TSP with Bounded Integer Weights: A nonzero coefficient of y^l occurs only if a Hamiltonian cycle of total weight l exists.The polynomial is formed from the summed Labeled Cycle Cover expressions.
5 TSP with Bounded Integer Weights: The Fast Fourier Transform over GF(2^k) retrieves all coefficients, provided the field size exceeds the maximum y-degree to prevent wraparound.Evaluations at powers of a multiplicative generator are followed by an inverse Fourier transform.
5 TSP with Bounded Integer Weights: Repeating the algorithm with different vertex partitions increases the probability that the lightest cycle is detected, after which the smallest nonzero coefficient is output.This repetition accounts for the method’s restriction to cycles with at most m_max arcs unlabeled by V2.