<p>It does look like their proof for the time bound has a minor error, though that part of the theorem statement itself looks right.</p>

<p>To adapt their proof, instead of picking $c$ so that for large $n$,</p>

<p>$2^{n + b\log(n)} \cdot 2^{(2n + c\log(n))/2 + 1} \le 2^{n + c\log(n)}$,</p>

<p>you want to pick $c$ to have</p>

<p>$2^{n + b\log(n)} \cdot 2^{2(n/2 + 1) + c\log(n/2+1)} \le 2^{2n + c\log(n)}$</p>

<p>for large $n$. (The "$/2 + 1$" gets pre-composed with $n + c\log(n)$, not post-composed.) This overall gives a time bound of $2^{2n + c\log(n)}$. Of course, only $c = \Omega(\log(n))$ can achieve this, but a choice of $c = O(\log(n))$ does work. This gives the stated time bound of $2^{2n}\cdot n^{O(\log(n))}$.</p>

CC BY-SA 3.0
2016-07-20T07:02:34.153Z
In fact they state the complexity as $2^{2n}2^{O(log(n))}$, both in the introduction part and also P499, 3rd line from the bottom. However, they did write  $2^{2n}n^{O(log(n))}$ in the Theorem3.1, point (b), and the proof concludes that $T(n)= 2^{2n}2^{O(log(n))}$... So you see the confusion! :P

Also, they "choose c as a constant". For me, I agree that the right complexity is what you stated, not theirs.
Leo
CC BY-SA 3.0
2016-07-19T18:18:44.820Z
2016-07-19T18:18:44.820Z
Andrew Morgan
<p>Just a note: the $n^{\log n}$ factor can be replaced by a polynomial, without much trouble. Here's one way to do it, not at all optimized...</p>

<p>Imagine there is a global graph $G$ with vertex set $[n]$, and a current induced subgraph $G' = (V',E')$ of $G$, with $n'=|V'|$. Instead of guessing the middle vertex along with each of the ${n' \choose \lfloor n'/2\rfloor}$ subset choices for $S \subseteq V'$, one can recurse only on the choice of $S$. Assume the recursive calls return $n \times n$ matrices $A_S$ and $A_{V'-S}$ such that:</p>

<ul><li> $A_S[i,j]$ equals the minimum cost of a Hamiltonian tour that starts with some vertex $i \in V$ (not necessarily in $S$), traverses only through vertices in $S$, then ends with some vertex $j \in V$ (not necessarily in $S$).  <li>$A_{V'-S}[i,j]$ is defined similarly.</ul>

<p>The algorithm should then return the $n\times n$ matrix $A_{G'}$, where for all $i,j=1,\ldots,n$, $A_{G'}[i,j] = \min_{S \subseteq V'} \min_{k\in V'} (A_S[i,k]+ A_{V'-S}[k,j])$.  Note that we do not have to store all these matrices; we could for example maintain $O(1)$ matrices per recursion layer (and the recursion depth is $O(n)$). After we compute the matrix product $A'[i,j] = \min_k (A_S[i,k]+ A_{V'-S}[k,j])$, we can simply take the MIN of $A'[i,j]$ with the current $A_{G'}[i,j]$ over all $i,j$, then erase $A_S$ and $A_{V'-S}$ before going to the next subset $S$. Thus the space usage is $poly(n)$.</p>

<p>Now the time recurrence is $T(n',n) = {n' \choose \lfloor n'/2\rfloor} \cdot (T(\lfloor n'/2\rfloor,n) + T(\lceil n'/2\rceil,n) + poly(n))$ for all $n' \leq n$ and $T(1,n) = poly(n)$, which yields $T(n',n) \leq 4^{n'} \cdot n^k$ for some $k \geq 1$. To verify this, note that the RHS of the recurrence is upper bounded by</p>

<p>$2^{n'+1} T(n'/2,n) + 2^{n'} \cdot poly(n) \leq 2^{n'+1} \cdot (4^{n'/2} (n/2)^k) + 2^{n'} n^k$
$= 2 \cdot 4^{n'} (n/2)^k + 2^{n'} n^k
\leq 4^{n'} n^k/2^{k-1} + 2^{n'} n^k$,</p>

<p>which is $\leq 4^{n'} n^k$ for $k \geq 3$ (for example). </p>

CC BY-SA 3.0
2016-08-09T07:34:29.277Z
It's a nice idea but i have some trouble with the recurrence: if i understood well, for each already computed $A_S$ and $A_{V'-S}$ we need to compute $A'$ (which takes $(n'/2)^3$) then update $A_{G'}$ (which take $(n'/2)^2$), and these costs should be a multiplicative instead of additive factor in the final recurrence.
Leo
CC BY-SA 3.0
2016-08-09T17:07:44.387Z
Yes, there was a misplaced parenthesis. Updated my answer, hope it's clearer.
Ryan Williams
CC BY-SA 3.0
2016-08-17T09:25:00.343Z
It's now clear for me. It's interesting to see that this approach is faster than the old one. While the framework is still Divide&Conquer, the use of matrices has some taste of Dynamic Programming. By using more memory (matrix) we gain in time. Maybe the result worth being mentioned somewhere in the literature :)
Leo
CC BY-SA 3.0
2016-08-08T11:21:26.053Z
2016-08-09T17:19:54.873Z
2016-08-09T17:19:54.873Z
Ryan Williams
<p>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!)$.</p>

<p>There is a elegant D&amp;C (divide &amp; 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. </p>

<p>In the following, I first provide some pointers then put the main idea of D&amp;C and my own analysis.</p>

<ul>
<li>The paper: <a href="https://www.google.com/webhp?sourceid=chrome-instant&amp;ion=1&amp;espv=2&amp;ie=UTF-8#q=expected%20computation%20time%20for%20hamiltonian%20path%20problem">expected computation time for hamiltonian path problem</a> </li>
<li>The algorithm is called <strong>HPA3</strong> on page 499 and 500.</li>
<li>P499, 3rd line from the bottom: ...run-time...$2^{2n}$ times a polynomial in $n$</li>
<li>P500, point (b), $T(n)=2^{2n}\times n^{O(l)}$ (which is a contradiction)</li>
<li>P500, ...choose a $c$ such that $T(n)=2^{2n+cl}$....</li>
</ul>

<p><strong>Main idea of D&amp;C</strong>
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. </p>

<p><strong>My analysis</strong>
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}$</p>

<p>The author uses induction to prove, but for me it's wrong. Could anyone make a judgement?</p>

<p><strong>[edit 07/19]</strong>: I realized that asymptotically $n^{\log n}&lt;2^n$ but the lhs is greater than a polynomial in $n$ anyway no?</p>

<p><strong>[edit 07/20]</strong>: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&gt;1$", so let's say the complexity is infinitely close to $4^n$ from above. </p>

<p>P.S. for any constant positive $c&gt;1$, $n^{\log n}=c^{(\log_c n)\log n}\leq \max(c^{\log^2 n},c^{\log_c^2 n})&lt;c^n$ (asymptotically)</p>

CC BY-SA 3.0
2016-07-20T08:06:56.043Z
Yes, this is a typo, the actual running time of their algorithm is $4^n n^{\log{n}}$ (see, e.g., "Exact Algorithms for Exact Satisfiability and Number
of Perfect Matchings" by Bjorklund and Husfeldt, A Taxonomic Introduction to Exact Algorithms by Husfeldt, or [1]). [1]:http://cstheory.stackexchange.com/a/11557/7454
Alex Golovnev
CC BY-SA 3.0
2016-07-20T08:50:47.570Z
Thanks @AlexGolovnev for providing evidences, the summary in your post is very nice. I just realized that the complexity ($O(4^nn^{log n})$) can be also viewed as "$O((4+\epsilon)^n)$ for any $\epsilon>0$", so let's say the complexity is infinitely close to $4^n$ from above, so their typo is not so far from the truth...:)
Leo
<cc.complexity-theory><ds.algorithms><graph-algorithms>
Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem
Leo
# Confusing running time analysis for the Divide & Conquer algorithm of Hamiltonian Path problem

(Asked by: username_0 on 2016-07-19)

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](https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=expected%20computation%20time%20for%20hamiltonian%20path%20problem)
* 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})

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: Yes, this is a typo, the actual running time of their algorithm is $4^n n^{\log{n}}$ (see, e.g., "Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings" by Bjorklund and Husfeldt, A Taxonomic Introduction to Exact Algorithms by Husfeldt, or [1]). [1]:http://cstheory.stackexchange.com/a/11557/7454  
> **username_0**: Thanks @AlexGolovnev for providing evidences, the summary in your post is very nice. I just realized that the complexity ($O(4^nn^{log n})$) can be also viewed as "$O((4+\epsilon)^n)$ for any $\epsilon>0$", so let's say the complexity is infinitely close to $4^n$ from above, so their typo is not so far from the truth...:)  

---

## 2 answers

### Answer by username_2 on 2016-07-19. Score: 4 | Accepted answer

It does look like their proof for the time bound has a minor error, though that part of the theorem statement itself looks right.

To adapt their proof, instead of picking $c$ so that for large $n$,

$2^{n + b\log(n)} \cdot 2^{(2n + c\log(n))/2 + 1} \le 2^{n + c\log(n)}$,

you want to pick $c$ to have

$2^{n + b\log(n)} \cdot 2^{2(n/2 + 1) + c\log(n/2+1)} \le 2^{2n + c\log(n)}$

for large $n$. (The "$/2 + 1$" gets pre-composed with $n + c\log(n)$, not post-composed.) This overall gives a time bound of $2^{2n + c\log(n)}$. Of course, only $c = \Omega(\log(n))$ can achieve this, but a choice of $c = O(\log(n))$ does work. This gives the stated time bound of $2^{2n}\cdot n^{O(\log(n))}$.

> **Comments:**
> **username_0**: In fact they state the complexity as $2^{2n}2^{O(log(n))}$, both in the introduction part and also P499, 3rd line from the bottom. However, they did write  $2^{2n}n^{O(log(n))}$ in the Theorem3.1, point (b), and the proof concludes that $T(n)= 2^{2n}2^{O(log(n))}$... So you see the confusion! :P  Also, they "choose c as a constant". For me, I agree that the right complexity is what you stated, not theirs.  

---

### Answer by username_3 on 2016-08-08. Score: 6

Just a note: the $n^{\log n}$ factor can be replaced by a polynomial, without much trouble. Here's one way to do it, not at all optimized...

Imagine there is a global graph $G$ with vertex set $[n]$, and a current induced subgraph $G' = (V',E')$ of $G$, with $n'=|V'|$. Instead of guessing the middle vertex along with each of the ${n' \choose \lfloor n'/2\rfloor}$ subset choices for $S \subseteq V'$, one can recurse only on the choice of $S$. Assume the recursive calls return $n \times n$ matrices $A\_S$ and $A\_{V'-S}$ such that:

* $A\_S[i,j]$ equals the minimum cost of a Hamiltonian tour that starts with some vertex $i \in V$ (not necessarily in $S$), traverses only through vertices in $S$, then ends with some vertex $j \in V$ (not necessarily in $S$).* $A\_{V'-S}[i,j]$ is defined similarly.

The algorithm should then return the $n\times n$ matrix $A\_{G'}$, where for all $i,j=1,\ldots,n$, $A\_{G'}[i,j] = \min\_{S \subseteq V'} \min\_{k\in V'} (A\_S[i,k]+ A\_{V'-S}[k,j])$. Note that we do not have to store all these matrices; we could for example maintain $O(1)$ matrices per recursion layer (and the recursion depth is $O(n)$). After we compute the matrix product $A'[i,j] = \min\_k (A\_S[i,k]+ A\_{V'-S}[k,j])$, we can simply take the MIN of $A'[i,j]$ with the current $A\_{G'}[i,j]$ over all $i,j$, then erase $A\_S$ and $A\_{V'-S}$ before going to the next subset $S$. Thus the space usage is $poly(n)$.

Now the time recurrence is $T(n',n) = {n' \choose \lfloor n'/2\rfloor} \cdot (T(\lfloor n'/2\rfloor,n) + T(\lceil n'/2\rceil,n) + poly(n))$ for all $n' \leq n$ and $T(1,n) = poly(n)$, which yields $T(n',n) \leq 4^{n'} \cdot n^k$ for some $k \geq 1$. To verify this, note that the RHS of the recurrence is upper bounded by

$2^{n'+1} T(n'/2,n) + 2^{n'} \cdot poly(n) \leq 2^{n'+1} \cdot (4^{n'/2} (n/2)^k) + 2^{n'} n^k$
$= 2 \cdot 4^{n'} (n/2)^k + 2^{n'} n^k
\leq 4^{n'} n^k/2^{k-1} + 2^{n'} n^k$,

which is $\leq 4^{n'} n^k$ for $k \geq 3$ (for example).

> **Comments:**
> **username_0**: It's a nice idea but i have some trouble with the recurrence: if i understood well, for each already computed $A_S$ and $A_{V'-S}$ we need to compute $A'$ (which takes $(n'/2)^3$) then update $A_{G'}$ (which take $(n'/2)^2$), and these costs should be a multiplicative instead of additive factor in the final recurrence.  
> **username_3**: Yes, there was a misplaced parenthesis. Updated my answer, hope it's clearer.  
> **username_0**: It's now clear for me. It's interesting to see that this approach is faster than the old one. While the framework is still Divide&Conquer, the use of matrices has some taste of Dynamic Programming. By using more memory (matrix) we gain in time. Maybe the result worth being mentioned somewhere in the literature :)  

---

