#### Theory Seminar

# APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

Ohad TrabelsiUniversity of Michigan

WHERE:

3725 Beyster BuildingMap

WHEN:

Friday, December 3, 2021 @ 3:00 pm - 4:00 pm

This event is free and open to the publicAdd to Google Calendar

This event is free and open to the publicAdd to Google Calendar

WEB: Event Website

SHARE:

We design an n^{2+o(1)}-time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on n nodes. This bound is almost-optimal in terms of n, and it improves on the recent \tO(n^{2.5}) bound by the authors (STOC 2021), which was the first to break the cubic barrier. Consequently, the All-Pairs Maximum-Flow (APMF) problem has time complexity n^{2+o(1)},and for the first time in history, this problem can be solved faster than All-Pairs Shortest Paths (APSP). We further observe that an almost-linear time algorithm (in terms of the number of edges m) is not possible without first obtaining a subcubic algorithm for multigraphs.