2022/11/11 by Tobias Friedrich, Davis Issac, Friedrich, Tobias +7 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2211.06267
openalex publication_date 2022/11/11 · openalex created_date 2022/11/21 · openalex updated_date 2026/07/28
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.