End vertices of graph searches can exhibit strong structural properties and
are crucial for many graph algorithms. The problem of deciding whether a given
vertex of a graph is an end-vertex of a particular search was first introduced
by Corneil, Köhler and Lanlignel in 2010. There they showed that this problem
is in fact NP-complete for LBFS on weakly chordal graphs. A similar result for
BFS was obtained by Charbit, Habib and Mamcarz in 2014. Here, we prove that the
end-vertex problem is NP-complete for MNS on weakly chordal graphs and for MCS
on general graphs. Moreover, building on previous results, we show that this
problem is linear for various searches on split and unit interval graphs.