On the Power of Graph Searching

Derek Corneill

Abstract

Since the early days of graph algorithms, graph searches such as Breadth and Depth First Search have formed the foundation of many practical graph algorithms. In 1976 Lexicographic Breadth First Search (LBFS) was introduced as a simple linear time way of recognizing whether a graph has any induced cycles of size greater than 3 (i.e., whether the graph is chordal). Starting in the 1990s many applications were discovered of LBFSand later, other searches were identified and exploited. Surprisingly, some such results contribute to algorithmic development in other areas of applications and mathematics.

In this talk, we will provide a fast overview of these developments through the examination of a very simple heuristic algorithm to find a hopefully large independent set (IS) in an arbitrary graph. It will be shown that by using a specific graph search (namely Lexicographic Depth First Search) as a preprocessing step, the heuristic