BARC Talk by Marcin Pilipczuk

Tuesday, February 25, 2025, Marcin Pilipczuk, Professor at the University of Warsaw, Poland, will give a talk on "Faster diameter computation in graphs of bounded Euler genus".

Abstract:
A classic result by Roditty and Vassilevska-Williams shows that computing a diameter of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Orthogonal Vectors Conjecture fails. In a breakthrough work, Cabello showed a subquadratic algorithm in planar graphs. Building upon a line of research on distance profiles, Le and Wulff-Nilsen at SODA'24 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. 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, Michał Pilipczuk, and Giannos Stamoulis.

Bio:
Marcin graduated from University of Warsaw in 2012. After postdocs in Bergen and Warwick, and a semester at Berkeley, he returned for a professorship position in Warsaw. He joined BARC for a sabbatical in academic year 2022/23 and is now Professor at the Institute of Informatics at the University of Warsaw. Marcin's research interests lie on the boundary of graph algorithms and structural graph theory. This includes fixed-parameter algorithms, graph minors, algorithms in planar graphs, and studying graph classes excluding small induced subgraphs.

Host:
Mikkel Thorup