Is it possible to force a graph search algorithm to visit a selected vertex as last? Corneil, Kohler, and Lanlignel showed that this end-vertex decision problem is NP-complete for Lexicographic Breadth-First Search (LexBFS). Charbit, Habib, and Mamcarz extended the intractability result, and showed that the end-vertex problem is hard also for BFS, DFS, and LexDFS. We ask for positive results, and study algorithmic and combinatorial questions. We show that the end-vertex problem for BFS and DFS can be solved in O~* (2~n) time, hereby improving upon the straightforward and currently best known running-time bound of O~*(n!). We also determine conditions that preserve end-vertices in subgraphs when extending to larger graphs. Such results are of interest in algorithm design, when applying techniques such as dynamic programming and divide-and-conquer.
展开▼
