On the recognition of search trees generated by BFS and DFS
Robert Scheffler
Abstract
The spanning trees of a graph constructed by the graph searches BFS and DFS are some of the most elementary structures in algorithmic graph theory. BFS-trees are first-in trees, i.e., every vertex is connected to its first visited neighbor. DFS-trees are last-in trees, i.e., every vertex is connected to its most recently visited neighbor. It is known since the 1980s that the problem of deciding whether a given spanning tree of a graph is a BFS-tree or a DFS-tree can be solved in linear time. Here, we will show that swapping the search-tree paradigms between these searches makes the problem hard, i.e., it is NP-complete to decide whether a spanning tree of a graph is a first-in-tree of a DFS or a last-in-tree of a BFS. To the best of our knowledge the latter result is the first hardness result for the recognition of last-in-trees for some graph search. Additionally, we study the complexity of both problems on split graphs.