Influence of the tie-break rule on the end-vertex problem
Pierre Charbit, Michel Habib, Antoine Mamcarz
Abstract
End-vertices 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
tie-break rule is used. In this paper we study how the choice of the
tie-break 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 end-vertex problem. In particular we prove a
counterintuitive NP-completeness result for Breadth First Search
solving a problem raised in Corneil, Köhler and Lanlignel 2010.
Full Text: PDF PostScript