What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)?
I was thinking of the following way :
First, calculate the number of Hamilton paths in the complete graph.
Remove one edge at a time, but I am not able to figure out how many paths would be reduced on removing an edge. Also how to prevent double counting while removing the edges ?
I came across a similar question here but that was about Hamilton cycles and not paths, I hope that changes the question significantly. Also the answers were not quite clear, hence this post.