In the Hamiltonian Path problem we are given a graph $G=(V,E)$ and two distinct vertices $\{s,t\}$ and we ask if there is a path from $s$ to $t$ which traverses all other vertices exactly once. Clearly, the brute-force algorithm enumerates all possible vertex orderings and runs in $O(n!)$.
There is a elegant D&C (divide & conquer) style algorithm in Gurevich1987 which is stated to run in $O(2^{2n}\times2^{O(l)})$ with $l=\log_2 n$. But after checking several times the proof and performing an analysis in a different way, I would believe that the correct running time is rather $O(2^{2n}\times n^{O(l)})$. Interestingly, in that paper, this expression also appeared once, perhaps it's a typo, but it makes things really confusing for me.
In the following, I first provide some pointers then put the main idea of D&C and my own analysis.
- The paper: expected computation time for hamiltonian path problem
- The algorithm is called HPA3 on page 499 and 500.
- P499, 3rd line from the bottom: ...run-time...$2^{2n}$ times a polynomial in $n$
- P500, point (b), $T(n)=2^{2n}\times n^{O(l)}$ (which is a contradiction)
- P500, ...choose a $c$ such that $T(n)=2^{2n+cl}$....
Main idea of D&C Very simple, guess the middle vertex (note $m$) in the path $(s,t)$, then try all possible subset $A\subset V$, $|A|=(n-3)/2$, assuming the the path is somehow like $s,A,m,(V-A),t$. This divides the input instance into two half-size instances, and it yields a recurrence relation: $T(n)\leq (n-2)2^{n-3}T((n-3)/2)$, with $b$ some unknown constant.
My analysis To be simpler, note $n$ as the number of vertices except $\{s,t\}$. Then $T(n)\leq n2^nT(n/2)\\ = 2^{n(1+1/2+1/4...1/n)}\times (n*n/2*n/4*...*1)\\ \leq 2^{2n}\times n^{\log n} \ (2^{1+2+...+\log n}) \\ = 2^{2n}\times n^{(\log n)/2}$
The author uses induction to prove, but for me it's wrong. Could anyone make a judgement?
[edit 07/19]: I realized that asymptotically $n^{\log n}<2^n$ but the lhs is greater than a polynomial in $n$ anyway no?
[edit 07/20]:as the comments and answers stated, we can basically conclude that there exists some issue in that paper and the correct complexity is $O(4^nn^{log n})$. However this can be also viewed as "$O((4\times\epsilon)^n)$ for any $\epsilon>1$", so let's say the complexity is infinitely close to $4^n$ from above.
P.S. for any constant positive $c>1$, $n^{\log n}=c^{(\log_c n)\log n}\leq \max(c^{\log^2 n},c^{\log_c^2 n})<c^n$ (asymptotically)