ETH, paridad y decisión.

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 [5] 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 [2] 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 [4], 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 [4].


Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de

Estás comentando usando tu cuenta de Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )


Conectando a %s

A %d blogueros les gusta esto: