The Recognition Problem of Graph Search Trees
Jesse Beisegel, Carolin Denkert, Ekkehard A. Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler · SIAM Journal on Discrete Mathematics · 2021
Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given spanning tree of a graph is a search tree of a particular search on this graph was introduced by Hagerup in 1985, where the author showed that this problem is efficiently solvable for depth first search (DFS) trees and breadth first search (BFS) trees. If one defines such a search tree in the same way as done for BFS, i.e., by connecting every vertex to its first neighbor, then we call this an ${\cal F}$-tree. If, on the other hand, we connect it with its most recently visited neighbor (as in DFS) we call this an ${\cal L}$-tree. In this paper, we consider related search paradigms. We prove that the search tree problem can be solved in polynomial time for ${\cal L}$-trees of lexicographic depth first search, whereas the ${\cal F}$-tree recognition problem is $\mathcal{NP}$-complete for lexicographic breadth first search, lexicographic depth first search, maximum cardinality search, and maximal neighborhood search. Furthermore, we present polynomial results for both types of trees on chordal graphs.