I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the random element?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
