Hi all,
this week we will have seminar given by a vising grad student from Slovenia. The seminar is in the usual time slot. I'm writing this a bit earlier in case you may want to discuss something (I believe she only stays this week).
Title: On the End-Vertex Problem of Graph Searches Speaker: Nevena Pivač (University of Primorska)
End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. In the lecture we will present a selection of known and new results related to end vertices of various graph searches.
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öohler, 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.
Regarding new results, 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-time solvable for various searches on split and unit interval graphs.
Joint work with Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Robert Scheffler, Martin Strehler. Preprint available at https://arxiv.org/abs/1810.12253.
-- Robert Šámal IÚUK MFF UK -- CSI of Charles University