The Partial Search Order Problem

Abstract

In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem introduced by Corneil et al. in 2010 asks for search orderings ending in a particular vertex. On the other hand, the problem of finding orderings that induce a given search tree was introduced already in the 1980s by Hagerup and received new attention most recently. Here, we consider a generalization of some of these problems by studying the question whether there is a search ordering that is a linear extension of a given partial order on a graph's vertex set. We show that this problem can be solved in polynomial time for Generic Search on general graphs as well as for searches called forgetful and partial orders of bounded width. Furthermore, we present polynomial-time algorithms on the classes of chordal bipartite graphs and split graphs for some searches including (Lexicographic) Breadth First Search. These algorithms generalize known algorithmic results for the End-Vertex Problem and the Search Tree Recognition Problem.