An O(n) time algorithm for finding Hamilton cycles with high probability

on YouTube ↗24m

" summary

Claim: an algorithm finds a Hamilton cycle in G(n,p) with high probability in O(n) time under the model that neighbor queries return a uniform random neighbor in O(1). It first builds a perfect matching in linear time by adaptively exposing D neighbors with D = min(sqrt(n/T), log n) as the unmatched target set T shrinks, then takes a second matching so the union is a 2-regular graph whose cycles behave like a permutation (two matchings form permutation cycles of about log n many), and stitches those cycles using small exposed neighborhoods with data structures like AVL trees + linked lists.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 0:35Definitions - Hamilton Cycle
3. 1:35Definitions - Posa Rotations
4. 5:18Random Graphs - Threshold
5. 6:37Random Graphs - Similar Results
6. 7:20Algorithms
7. 8:35Technical Detail
8. 9:31Angluin and Valiant algorithm
9. 12:13Angluin and Valiant analysis
10. 13:16Improving the algorithm
11. 14:17Randomwalking
12. 16:17Method Idea
13. 16:34Random walking