Un sorprendente nuevo resultado sobre el problema de recorridos hamiltonianos en dígrafos generales.

**Título.** *The Parity of Directed Hamiltonian Cycles*

**Abstract**.

*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.

**Extracto.**

*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].

### Me gusta:

Me gusta Cargando...

*Relacionado*

This entry was posted on enero 31, 2013 at 2:35 pm and is filed under ALGORITHMICS, NEW SUBRUTINES, US PATENT APPLICATION RESEARCH. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## 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.