Using the DFS Algorithm for Finding Long Paths in Random and Pseudo-Random Graphs

The Depth First Search (DFS) algorithm is one of the most standard graph exploration algorithms, used normally to find the connected components of an input graph. Though perhaps less popular than its sister algorithm, Breadth First Search (BFS), the DFS algorithm is very simple and handy and has many nice properties; it is particularly well suited for finding long paths. In this talk I will discuss how basic properties of the DFS algorithm can be exploited to argue about the (typical) existence of long paths in random and pseudo-random graphs. Based partly on a joint work with Benny Sudakov.