On the power of standard DFS and BFS
For graph theory researchers, it simplifies recognition algorithms for well-structured graph classes using only basic graph searches.
The paper shows that standard DFS and BFS can recognize and certify several graph classes (trivially perfect, split, bipartite chain, proper interval) with simpler algorithms than previous methods, including a single DFS for trivially perfect graphs and a two-BFS scheme for proper interval graphs.
It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972] and Breadth First Search (BFS) can be used to compute distance in graphs [GY. Handler. Transportation Science, 1973]. We furthermore demonstrate that these standard graph searches are powerful enough to recognize and certify several well-structured graph classes. Specifically, we provide a single DFS approach for recognizing and certifying trivially perfect graphs that is significantly simpler than previous methods using [FPM. Chu. Information Processing Letters, 2008]. We further show that a single BFS can recognize split graphs and bipartite chain graphs, and we improve upon the triple LexBFS algorithm for proper interval graphs [DG. Corneil. Discrete Applied Mathematics, 2004] by proposing a two consecutive BFS recognition scheme. These results are underpinned by characterizations using vertex orderings that avoid specific patterns [L. Feuilloley, M. Habib. SIAM Journal on Discrete Mathematics, 2021]. Finally, we provide a structural study of connected proper interval graphs, proving that their characterizations via special orderings are unique up to reversal and the permutation of true twins.