C&O Reading Group - Nikhil Kumar

Friday, October 13, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth, Part II

Speaker: Nikhil Kumar
Affiliation: University of Waterloo
Location: MC 6029

Abstract: I will present a recent max-flow min-cut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known s-t flow problem, where we are given multiple source-sink pairs and goal is to maximize the total flow. A natural upper bound on the value of total flow is the value of the minimum multicut : the minimum total capacity of edges that need to be removed in order to disconnect all the source-sink pairs. We will show that given a treewidth-r graph, there exists a (fractional) multi-commodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F. It is well known that the multiflow-multicut gap on an r-vertex (constant degree) expander graph can be Ω(log r), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time O(log r)-approximation algorithm for the minimum multicut problem on treewidth-r graphs. I will try to cover all the relevant background material in the talk.

Based on joint work with Tobias Friedrich, Davis Issac, Nadym Malek and Ziena Zeif.