6
$\begingroup$

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)

$\endgroup$
  • 4
    $\begingroup$ 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]:cstheory.stackexchange.com/a/11557/7454 $\endgroup$ – Alex Golovnev Jul 20 '16 at 8:06
  • $\begingroup$ 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...:) $\endgroup$ – Leo Jul 20 '16 at 8:50
4
$\begingroup$

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))}$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Leo Jul 20 '16 at 7:02
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Leo Aug 9 '16 at 7:34
  • $\begingroup$ Yes, there was a misplaced parenthesis. Updated my answer, hope it's clearer. $\endgroup$ – Ryan Williams Aug 9 '16 at 17:07
  • $\begingroup$ 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 :) $\endgroup$ – Leo Aug 17 '16 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.