On the End-Vertex Problem

For a given graph search algorithm and a graph G, a vertex v is said to be an end-vertex if there exists a corresponding search ordering of the vertices such that v is the last vertex in this ordering. It is known that the complexity of recognizing the end-vertices in general graphs is NP-hard for several search algorithms, such as Breadth First Search, Depth First Search, and their lexicographic variants. This motivated the study of end-vertices with respect to some other search algorithms. In this work we consider Maximum Cardinality Search (MCS) and Maximum Neighborhood Search (MNS) and present results concerning the complexity of the end-vertex problem with respect to these search methods. We give some proofs of NP-completeness of this problem in general graphs, as well as polynomial-time algorithms, when a graph is restricted to belong to certain graph classes. Joint work with J. Beisegel, C. Denkert, E. Köhler, M. Krnc, R. Scheffler, and M. Strehler.