Complexity results for recognizing generalized graph search trees

Generalized Graph Search Trees

Discrete MathematicsData Structures and Algorithms

Summary

Graph search trees help computers explore networks or maps by tracking the order in which points are visited. Traditionally, there were two common ways to build these trees, either by connecting a point to the first neighbor visited or to the last neighbor visited before it. This paper studies a wider range where any previous neighbor can be the parent, making the problem more flexible but also harder to solve. The authors find that for most types of searches, figuring out if a tree matches this pattern is very difficult (NP-complete), but easier for certain special graph types and specific searches. They also check whether knowing the starting point simplifies the problem.

What this means in practice

A theory result. No direct application yet.

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.
View PDFOpen arXiv