Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time?

Question

Let G(V,E) be the graph and V = {$V_1$,$V_2$,....,$V_n$}. A dynamic programming approach solves the Hamiltonian path problem in $O(2^n n^3)$ time.

We can have a matrix : dp[s][i][j] : which computes for any subset (say s) of V whether there exists a hamiltonian path starting from vertex $V_i$ and ends at vertex $V_j$ if s includes $V_i$ and $V_j$.

Can we have only dp[s][i] and say whether there exists a hamiltonian path ending at vertex $V_i$ there by solving it in $O(2^n n^2)$ time. Can it be improved furthur?

Answer 1

Yes, the problem can be solved in $O^*(1.657^n)$ time using algebraic methods. See the FOCS paper of Björklund [1].

---

[1] Björklund, Andreas. "Determinant sums for undirected Hamiltonicity." Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.