Un sorprendente nuevo resultado sobre el problema de recorridos hamiltonianos en dígrafos generales.
Título. The Parity of Directed Hamiltonian Cycles
We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.618^n) time and polynomial space. For bipartite graphs, we give a 1.5n poly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
Inspired by the fact that the algorithm for the bipartite case in  actually computes the parity of the number of Hamiltonian cycles, we show how to compute this value for any directed graph in O(1.618^n) time. While this does not seem to shed any direct light on the decision problem in directed graphs, it does however ask a related interesting question: Could it really be easier to solve a ⊕P-complete problem than its decision counterpart? Even the known algorithm for the undirected graph decision case  is slower than our present algorithm.
We note in passing that for another wellknown problem, Set Cover, current evidence points in the opposite direction: It is known that a fast algorithm for computing the parity of the number of set covers would disprove the Strong Exponential Time Hypothesis , whereas no such connections are known for the decision variant.
Our paper accentuates the fact that the exponential time complexity of counting or deciding the Hamiltonian cycles in a directed graph is not very well understood. While there are several examples of ⊕P-complete problems whose decision analogue is computationally easier (e.g., ⊕2-Satisfiability), examples of the converse are not known to the authors.
Under the Exponential Time Hypothesis, the decision problem does not allow exp(epsilon*n)-time algorithms for arbitrary epsilon > 0, but there are no arguments for or against an O(1.999^n)-time algorithm for the decision problem.
For comparison, it is now known that the parity of the number of set covers of a given set system on n elements requires O(2^(1−ǫ)n) time under the Strong Exponential Time Hypothesis .