Source-linked AI summary
Directed Hamiltonian-Cycle Parity in $O^*((3/2)^n)$ Deterministic Time and Polynomial Space
Hanqing Li
TL;DR
The work makes the graph-based cover usable within the parity framework, with complete bounds on construction, regeneration, overlap handling, and all solution visits. The algorithm adapts the local-degree formula by covering its ternary state space with affine systems, bounding solution visits, and assigning overlapping states canonical owners. O(n^4(3/2)^n) time and O(n^2) bits of working space suffice to compute Hamiltonian-cycle parity deterministically.
Problem
The work makes the graph-based cover usable within the parity framework, with complete bounds on construction, regeneration, overlap handling, and all solution visits.
Source: §1 · p. 2Method
The algorithm adapts the local-degree formula by covering its ternary state space with affine systems, bounding solution visits, and assigning overlapping states canonical owners.
Source: §1 · p. 2, §5.1 · p. 8Results
O(n^4(3/2)^n) time and O(n^2) bits of working space suffice to compute Hamiltonian-cycle parity deterministically.
Source: §1 · p. 1Takeaways & Limitations
The complete-enumeration barrier leaves open faster ways to evaluate the weighted parity sum through aggregation or other methods that avoid visiting every solution.
Source: §8 · p. 13Complete P2 enumeration can require Ω((3/2)^n) visits even with an optimal diagonal, but this is not a lower bound for evaluating Hamiltonian-cycle parity.
Source: §7 · p. 13
Abstract
from arXiv · showhide
We give a deterministic algorithm that computes the parity of the number of Hamiltonian cycles in an $n$-vertex directed graph in $O(n^4(3/2)^n)$ time and $O(n^2)$ bits of working space, improving the $O^*(\varphi^n)$ bound of Bj\"orklund and Husfeldt. Their local-degree formula reduces the problem to a weighted sum over solutions of structured quadratic equations. We cover the corresponding ternary state space by binary subcubes, each inducing an affine system. The Kuang--Wang cover can be regenerated within the target bound; canonical ownership resolves its overlaps, while self-loop conditional expectations bound every affine solution visit. Rollback elimination shares the work across cover prefixes. The same cover gives a Las Vegas algorithm listing all $L$ solutions of $m$ affine product constraints in $N$ Boolean variables in expected time $\operatorname{poly}(N,m)((3/2)^m+L)$ and polynomial space. Finally, we show that complete enumeration can require $\Omega((3/2)^n)$ visits even on strongly connected digraphs after an optimal self-loop choice. This is a limitation of the enumeration method, not a general lower bound for Hamiltonian-cycle parity.
1 Introduction
The paper improves deterministic Hamiltonian-cycle parity counting on unrestricted directed graphs to a (3/2)^n exponential base with polynomial space. It adapts a ternary-state cover to the weighted parity framework and also studies affine-constraint enumeration and its limits.
1 Introduction
- The parity algorithm improves on Björklund and Husfeldt’s deterministic O*(φ^n)-time, polynomial-space bound for general digraphs [2].Their expected-time O*((3/2)^n) bound applies to bipartite digraphs.Source: §1 · p. 1
- O(n^4(3/2)^n) time and O(n^2) bits of working space suffice to compute Hamiltonian-cycle parity deterministically on n-vertex directed graphs.The algorithm attains on unrestricted digraphs the exponential base previously obtained in expected time on bipartite digraphs.Source: §1 · p. 1
- The method retains the local-degree formula’s P3 contribution test and improves P2 by covering its ternary state space with binary subcubes that induce affine systems.A diagonal is chosen so total affine solution visits are bounded, and a regenerable cover with canonical ownership handles overlaps.Source: §1 · pp. 1–2
- The same mechanism lists all L solutions of m affine product constraints in N Boolean variables in expected time poly(N, m)((3/2)^m + L) and polynomial space.Feasibility and search take deterministic poly(N, m)(3/2)^m time; enumeration is Las Vegas and duplicate-free.Source: §1 · p. 2
- The affine-constraint enumeration bound measures the number of constraints, unlike the dimension-based randomized search bound for PAF-SAT [1].The paper does not derandomize that dimension bound for an arbitrary number of constraints.Source: §1 · p. 2
- Complete P2 enumeration can require Ω((3/2)^n) visits even after an optimal self-loop choice, but this is not a lower bound for evaluating the weighted parity sum.The paper leaves open faster aggregation methods that avoid complete enumeration.Source: §1 · p. 2
2 The local-degree interface
The local-degree interface expresses Hamiltonian-cycle parity as a weighted sum over nonempty feasible subsets. Feasibility is checked by P2, while P3 computes each subset’s contribution through an affine system.
2 The local-degree interface
- A nonempty subset contributes to the sum only when its indicator vector satisfies x ◦(Ax) = x, the P2 feasibility condition.The parity of the solution count of the associated affine system determines its P3 contribution.Source: §2 · p. 3
- For nonempty X, f_A(X) is one exactly when its associated affine system has a unique solution, so Gaussian elimination computes the contribution in polynomial time and space.An affine system over F2 has either no solutions or a power-of-two number of solutions; its count is odd exactly when it is a singleton.Source: §2 · p. 3
- The diagonal choice changes feasible sets and their weights, but the weighted sum remains invariant; the parity of K_B(c) alone is not the target.The parity identity is obtained by pairing color classes in the integer formula before dividing by two, without division in F2.Source: §2 · p. 3
3 From a cover to a weighted affine fiber
The P2 solutions are represented as a fiber of a map from ternary states, then covered by binary subcubes that induce affine systems. A deterministic diagonal choice bounds total solution visits, including repetitions across overlapping subcubes.
3 From a cover to a weighted affine fiber
- The legal P2 states form a fiber of the map π_B, and covering the ternary state space with binary subcubes turns that fiber into affine systems.A center specifies a binary subcube by prohibiting one of the three legal states at each coordinate.Source: §3 · p. 4
3.1 Restricting a fiber to a binary subcube
- Within each center’s subcube, a Boolean parametrization converts the fiber condition into an affine system M_q z = c + d_q.The maps between Boolean parameters and subcube states are inverse even when M_q is singular, and M_q and d_q do not depend on c.Source: §3.1 · p. 4, Table 1 · p. 4
3.2 Controlling all solution visits by choosing the diagonal
- A deterministic diagonal c can be found with V(c) ≤ M, where V counts all affine solution visits, including repeated states from overlapping subcubes.Conditional expectation chooses each diagonal bit by comparing the counts for both prefixes; canonical ownership then processes each P2 solution at exactly one center without a visited-state list.Source: §3.2 · pp. 4–5
4 Deterministic covers that can be regenerated in polynomial space
The section builds an input-independent cover of ternary states that can be generated in polynomial space, with deterministic ownership of overlaps. Geometric blocks keep construction and every complete regeneration within poly(m)(3/2)^m time.
4.1 The Kuang–Wang construction and an ownership map
- The centers are distinct and cover the ternary state space, and a deterministic polynomial-time map assigns each state to a containing center.Ownership avoids storing a table of assignments.Source: §4.1 · p. 6
4.2 Choosing each auxiliary graph without a subset table
- A deterministic conditional-expectation construction chooses each auxiliary graph without a subset table, then enumerates its centers without repetition in poly(b)2^b time and polynomial space.It evaluates both choices for each edge and selects the one that does not increase the conditional expectation.Source: §4.2 · pp. 6–7
4.3 Geometric blocks and the cost of regeneration
- Geometrically decreasing block sizes control both the local center bounds and the subset scans needed during product-cover regeneration.The traversal may restart inner loops without caching; the block schedule is part of the time analysis.Source: §4.3 · pp. 7–8
- The cover representation, construction, and every complete center enumeration fit in poly(m)(3/2)^m time and polynomial space, with a canonical center computable for each state.The same bound applies to subsequent complete enumerations.Source: §4.3 · p. 7
- The regeneration theorem bounds complete traversals, not the delay between consecutive centers.The algorithm relies on making only polynomially many complete traversals.Source: §4.3 · p. 8
5 The deterministic algorithm and rollback implementation
The algorithm enumerates affine systems from a regenerable cover, assigns each generated state one owning center, and accumulates its contribution. Rollback elimination shares work across product-cover prefixes to achieve the stated deterministic time and space bounds.
5 The deterministic algorithm and rollback implementation
- The algorithm constructs the cover, selects a diagonal by prefix conditional expectations, and regenerates centers to form and process their affine systems.The input diagonal is deleted before cover construction.Source: §5 · p. 8, §5.2 · p. 9
5.1 Enumeration, ownership, and contribution accumulation
- The algorithm processes a generated state only at its owner, so retained states correspond exactly to the target parity contribution and the returned bit is correct.The one-vertex case is handled by its input loop bit.Source: §5.1 · p. 8
5.2 Sharing column elimination along the product traversal
- Rollback inserts a block’s columns on entry and removes them on return, sharing elimination work across traversal nodes without saving a matrix snapshot at each node.The stored unreduced echelon basis uses a stack of pivot slots for rollback.Source: §5.2 · p. 9
- O(n^4(3/2)^n) deterministic time and O(n^2) bits of working space suffice for the algorithm.The bound follows from the cover-size, diagonal-pass, and final-traversal costs.Source: §5.2 · p. 10
6 Solving and listing affine product constraints
The section gives output-sensitive, polynomial-space enumeration for affine product constraints and deterministic feasibility and search. It uses affine systems from a ternary-state cover, with translation controlling repeated visits without affecting correctness.
6 Solving and listing affine product constraints
- poly(N, m)((3/2)^m + L) expected time and polynomial space suffice to list all L solutions without repetition.The algorithm is Las Vegas; its random translation affects running time alone.Source: §6 · pp. 10–11
- For each coordinate, excluding symbols 0, 1, or 2 imposes, respectively, ui(ξ)+vi(ξ)=1, ui(ξ)=0, or vi(ξ)=0, yielding an affine system in the original N variables.Source: §6 · p. 10
- Deterministic feasibility and search test affine-system consistency across the cover, returning a solution when one exists or correctly reporting none.A consistent system yields a solution to the product constraints, and every product-system solution is covered by some system.Source: §6 · pp. 10–11
- A translated cover assigns each solution to one canonical owner, so every solution is output once for every translation.The expected total number of visits is bounded by the number of centers; polynomial-space streaming then gives the stated expected running time.Source: §6 · p. 11
7 Limits of complete enumeration
The section proves lower bounds on both the size of a universal legal affine cover and the visits required to enumerate some input fibers. The fiber bound holds for strongly connected digraphs, but it limits complete enumeration rather than parity computation generally.
7 Limits of complete enumeration
- A legal affine cover of the entire ternary state space needs at least ⌈(3/2)^m⌉ pieces.Each legal affine subspace can be enlarged to a binary subcube, and the volume bound gives 3^m ≤ M2^m.Source: §7 · pp. 11–12
- For every n ≥ 36, a strongly connected zero-diagonal digraph has min_c K_B(c) ≥ (4/27)(3/2)^n, while min_c K_B(c) ≤ (3/2)^n.The lower bound holds uniformly over diagonal choices; the proof extends the construction by adding a vertex connected in both directions to every old vertex.Source: §7 · pp. 12–13
- The construction bounds bad fibers using pairwise independence of solution indicators for distinct nonzero vectors.For distinct nonzero x and z, the joint expectation factors as E(IxIz) = EIxEIz.Source: §7 · p. 12
- The fiber lower bound uses a control space in which at most one map input reaches a bad syndrome for each fixed syndrome.A joint second-moment argument gives pairwise-independent solution indicators; a choice of D and T then avoids differences between bad syndromes.Source: §7 · p. 12
- The lower bound is a barrier for explicitly visiting every P2 solution, not a lower bound for computing Hamiltonian-cycle parity.Structural shortcuts or aggregation may avoid complete enumeration, and the witness argument does not provide an efficient construction.Source: §7 · p. 13
8 Discussion
The discussion attributes the smaller exponential base to combining a regenerable cover, canonical ownership, and a bound on every affine-solution visit. It identifies output-sensitive derandomization for general affine product systems as unresolved.
8 Discussion
- The smaller base combines a regenerable cover, ownership, and a budget for every affine-solution visit.For general affine product systems, deterministic feasibility already has the same exponential bound in the number of constraints.Source: §8 · p. 13
- Derandomizing output-sensitive enumeration remains open because partial ternary translations lack the simple rank-based conditional counts available for Hamiltonian diagonal choices.The discussion points to aggregate summation or covers adapted to an input fiber as possible ways beyond the complete-enumeration barrier.Source: §8 · p. 13