Title: Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
| Speaker: | Nikhil Kumar |
| Affilation: | 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)