What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?
There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund [1]. These algorithms are often algebraic and the "random element" stems from the application of the Schwartz–Zippel lemma. Usually, the algorithms work so that the graph property we are interested in is somehow represented as a (multivariate) polynomial with the property that that a solution exists precisely when the polynomial is not identically zero.



[1] Björklund, Andreas. "Determinant sums for undirected hamiltonicity." SIAM Journal on Computing 43.1 (2014): 280-299.