Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth

We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f , and a multicut of capacity c such that f ≤ c ≤ O(ln(r + 1)) • f . It is well known that the multiflow-multicut gap on an r-vertex (constant degree) expander graph can be Ω(ln r), and hence our result is tight up to constant factors. Our proof is constructive, and we also obtain a polynomial time O(ln(r + 1))-approximation algorithm for the minimum multicut problem on treewidth-r graphs. Our algorithm proceeds by rounding the optimal fractional solution to the natural linear programming relaxation of the multicut problem. We introduce novel modifications to the well-known region growing algorithm to facilitate the rounding while guaranteeing at most a logarithmic factor loss in the treewidth.