Faster diameter computation in graphs of bounded Euler genus
Time: 14:00 -- Location: bat 650, 445
Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs. Building upon a line of research on distance profiles, Le and Wulff-Nilsen [SODA 2024] presented a \(O(n^{2-c_h})\)-time algorithm for diameter in \(K_h\)-minor-free graphs, where \(c_h = \Theta(1/h)\). However, known lower bounds do not refute the possibility of an \(O_h(n^{2-c})\)-time algorithm in \(K_h\)-minor-free graphs for some universal constant \(c\) (not depending on \(h\)). We present such an algorithm for the case of bounded Euler genus graphs (and \(c=0.04\)) and discuss where our approach fails for the general excluded-minor case.
Joint work with Kacper Kluk, Marcin Pilipczuk, and Michał Pilipczuk.