A Deterministic $O^*((3/2)^n)$ Algorithm for the Parity of Directed Hamiltonian Cycles

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\"orklund 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.