论文标题
近似Max-Flow Min-Multicut定理，用于有界树宽的图形
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
论文作者
论文摘要
我们证明了一个近似的Max-Multiflow Min-Multicut定理，用于有限的树顶图。特别是，我们显示以下内容：给定树宽 - $ r $图，存在一个（分数）的价值$ f $的多商品流量，以及一个多重容量$ c $的多物品流，使得$ f \ f \ leq c \ leq c \ leq \ mathcal {o}（O}（\ ln（r+1））\ cdot f $。众所周知，在$ r $ vertex（恒定度）膨胀仪图上的多流式差距可以为$ω（\ ln r）$，因此我们的结果是紧密的，直到恒定因素。我们的证明是建设性的，我们还获得了一个多项式时间$ \ mathcal {o}（\ ln（r+1））$ - 近似算法，用于TreeWidth-$ r $ graphs上的最小多冲突问题。我们的算法通过将最佳分数解决方案舍入到多次问题的自然线性编程松弛方面来进行。我们将新颖的修改引入了众所周知的生长算法，以促进圆形，同时保证最多可对数因子损失。
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 \leq c \leq \mathcal{O}(\ln (r+1)) \cdot 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 $\mathcal{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.
