arXiv preprint ·
A Deterministic $O^*((3/2)^n)$ Algorithm for the Parity of Directed Hamiltonian Cycles
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a deterministic algorithm for the parity of the number of directed Hamiltonian cycles in an $n$-vertex digraph. For $n\geq 2$, the running time is $O^*((3/2)^n)$ and the space usage is $2^{O(n/\log n)}$. The construction starts from the local-degree identity of Björklund and Husfeldt. Their surviving terms are solutions of a quadratic system over $\mathbb{F}_2$. We encode each coordinate of this system by one of three states and observe that forbidding one state per coordinate makes the system affine-linear. A cover of the ternary cube by antipodal binary subcubes then gives a small family of affine systems. The cover is made constructive and deterministic. We use the even-induced-subgraph construction of Kuang and Wang, together with conditional expectations, to obtain a cover of a block of $b$ coordinates with at most $2(3/2)^b-1$ centers. A canonical owner for every ternary state removes all duplicate enumeration. A second conditional-expectation argument chooses the artificial self-loops so that the total number of affine solutions generated by all systems is no larger than the number of systems. The remaining contribution of each state is evaluated by one Gaussian elimination over $\mathbb{F}_2$. We include complete proofs of the encoding, the owner rule, the two derandomizations, and the complexity bound. The degenerate one-vertex case is handled separately because a self-loop can then itself be a Hamiltonian cycle.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Smoothed Picard Hamiltonian Monte Carlo
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Frequency Moments Beyond Equality: Streaming Cosine Density Moments
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.