Generalized graph search trees reveal new complexity results in algorithms
Generalized Graph Search Trees
Discrete MathematicsData Structures and Algorithms
Summary
Graph search trees help organize how a computer explores networks to solve problems. Previously, researchers focused on trees built by two main methods: picking the first neighbor visited or the last neighbor visited when adding a new node. This paper expands the idea by allowing any previously visited neighbor to be connected as the parent of a node, creating a more general kind of search tree. The authors explore how hard it is to recognize these generalized trees, finding that for most methods, this task is computationally difficult (NP-complete), but easier for certain types of graphs or starting points. Their work sheds light on the limits of these tree structures in graph algorithms.
graph search algorithmsgraph search treesBFS (breadth-first search)DFS (depth-first search)NP-completenessrecognition problembipartite graphschordal graphsalgorithmic graph theoryparent in search tree
Authors
Florian Krowiorz, Robert Scheffler
Abstract
Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.