多路切割的复杂性（扩展摘要）

在多路切割问题中，给定一个带边权的图和一组称为终端的顶点子集，并要求找到一组最小权重的边，使得每个终端与其他终端相分离。当终端的数量 k 为 2 时，这只是最小割最大流问题，可以在多项式时间内解决。我们表明，当 k = 3 时，该问题变为 NP-hard，但对于任何固定的 k，在平面图中可以在多项式时间内解决。然而，当 k 不固定时，平面问题是 NP-hard 的。我们还描述了一种针对任意图的简单近似算法，确保在最佳切割权重的 2–2/k 倍范围内。