0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.