7
$\begingroup$

We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there is an open source implementation of the algorithm, we can contribute to the testing of that code.We have a graph which has at least 10 Hamiltonian Cycles and we want to use that to find a specific Hamiltonian Cycle (How easy/hard is that will be our question).

Abstract of Broder et al's paper (from citeseer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1661 )

Consider a random graph G composed of a Hamiltonian cycle on n labeled vertices and dn random edges that "hide" the cycle. Is it possible to unravel the structure, that is, to efficiently find a Hamiltonian cycle in G? We describe an O(n 3 log n) steps algorithm A for this purpose, and prove that it succeeds almost surely. Part one of A properly covers the "trouble spots" of G by a collection of disjoint paths. (This is the hard part to analyze.) Part two of A extends this cover to a full cycle by the rotation-extension technique which is already classical for such problems.

Questions:

qn1) Has any one implemented Broder et al's algorithm?

qn 2) Are there recent paper better than Broder et al's algorithm –

qn 3) If there are 10 to 15 Hamiltonian cycles in a graph do their algorithm find all of them fast? –

  • A. Broder, A. M. Frieze and E. Shamir, "Finding hidden Hamiltonian Cycle," Random Structures and Algorithms , 5, 2006
$\endgroup$
  • 2
    $\begingroup$ Could you state your question, please? $\endgroup$ – András Salamon Oct 20 '10 at 16:18
  • $\begingroup$ agreed. msk, please fold these comments into the question $\endgroup$ – Suresh Venkat Oct 20 '10 at 19:51
  • 3
    $\begingroup$ (1) In case you have not noticed it, note that, contrary to what this question suggests, the randomized polynomial-time algorithm in the paper does not find a Hamiltonian cycle in an arbitrary graph. If it did, it would imply RP=NP (a huge result). (2) It is Hamiltonian, not Haniltonian. $\endgroup$ – Tsuyoshi Ito Oct 20 '10 at 23:31
  • 2
    $\begingroup$ There's a brand new algorithm: rjlipton.wordpress.com/2010/09/09/… $\endgroup$ – Yuval Filmus Oct 22 '10 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy