Space Complexity for Approximate All-Pairs Max Flows
Abstract:
The influential Gomory–Hu tree shows that, in an undirected edge-capacitated graph, all-pairs max flows can be represented using a single tree, yielding an O(n)-space data structure. I will show that the situation is very different for directed graphs, and even for undirected graphs with unit vertex capacities: any such data structure requires Ω(n²) space, even when allowing a √n-additive approximation.
Biosketch:
Thatchaphol Saranurak is an assistant professor of Electrical Engineering and Computer Science at the University of Michigan. His research focuses on fast graph algorithms across different models of computation, robust algorithms against adaptive adversaries, and continuous optimization techniques for combinatorial problems. He is the recipient of several honors, including the 2023 Presburger Award, an NSF CAREER Award, and a Sloan Research Fellowship, as well as best paper awards at SODA 2023 and PODC 2019.