Discrete Mathematics & Theoretical Computer Science 
Endvertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be recognized in polynomial time or not, as first studied in Corneil, Köhler and Lanlignel 2010. A graph search is a mechanism for systematically visiting the vertices of a graph. At each step of a graph search, the key point is the choice of the next vertex to be explored. Graph searches only differ by this selection mechanism during which a tiebreak rule is used. In this paper we study how the choice of the tiebreak in case of equality during the search, for a given graph search including the classic ones such as BFS and DFS, can determine the complexity of the endvertex problem. In particular we prove a counterintuitive NPcompleteness result for Breadth First Search solving a problem raised in Corneil, Köhler and Lanlignel 2010.
Source : ScholeXplorer
IsRelatedTo ARXIV 1810.12253 Source : ScholeXplorer IsRelatedTo DOI 10.23638/dmtcs21113 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1810.12253
