全局标签最小割问题的一个紧密拟多项式界限

《ACM Transactions on Algorithms》：A Tight Quasi-Polynomial Bound for Global Label Min-Cut

全局标签最小割问题的复杂度分析表明，其存在准多项式时间随机算法但无法在指数时间假设下显著优化，且在W[1]-参数化下为NP难问题。

　　

摘要AI总结

摘要

摘要

我们研究了经典全局最小割问题的一个推广版本，称为全局标签最小割（有时也称为全局对冲最小割）：输入（多）图的边被标记（或划分为颜色类别或对冲），移除所有相同标签（颜色或来自相同对冲）的边需要花费一定的成本。该问题的目标是以最低成本断开图。

虽然$st$最小割版本已知是$\mathrm{NP}$难问题，但上述全局最小割版本存在一个准多项式时间的随机算法，该算法由Ghaffari、Karger和Panigrahi在[SODA 2017]会议上提出。他们认为这是“这个问题属于P类”的有力证据。我们证明了事实并非如此。我们通过证明准多项式时间可能是最优时间来完成了对全局标签最小割问题复杂性的研究：我们表明，如果存在一个运行时间为，这将与指数时间假设相矛盾。其中$n$表示顶点数，$p$表示输入中的标签数。确定下界的关键步骤是证明当以未切割标签的数量为参数时，全局标签最小割问题是$W$[1]难问题。换句话说，在几乎所有标签都需要被切割才能断开图的情况下，这个问题非常困难。

AI总结

AI生成的总结（实验性）

该总结是使用自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助发现、评估相关性，并帮助来自相关研究领域的读者理解本文内容。它是对作者提供的摘要的补充，作者提供的摘要仍然是论文的官方总结。点击此处了解更多信息。

点击此处对总结的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的版本。

AI生成的总结

该总结由基于已发表文章文本的自动化系统生成。

生成日期：2026年2月11日。

本文研究了一个称为全局标签最小割的问题，它将经典的全局最小割问题扩展到了边带有颜色的多图上，在这种情况下，移除所有相同颜色的边需要支付单一成本。目标是找到一组顶点，以最小的颜色移除成本断开图。这个问题与网络生存能力相关，因为一个连接的失败可能导致整个网络的失败。与标准的最小割问题不同，计算切割中颜色的函数不是次模的，因此无法使用现有的多项式时间技术来处理超图切割。

之前的工作已经证明了在颜色类别诱导的连通分量数量有限的情况下，该问题有多项式时间解法，并为一般问题开发了随机准多项式时间算法。然而，其确切的计算复杂性尚不清楚，人们推测它可能是多项式时间或准多项式时间。本文通过证明，在指数时间假设（ETH）下，没有任何算法能够显著快于准多项式时间解决全局标签最小割问题，从而解决了这一难题。具体来说，它表明改进现有的准多项式时间算法将违反ETH假设，表明了复杂的复杂性界限。

作者还证明了当以解决方案中未切割的颜色数量为参数时，全局标签最小割问题是W[1]难问题，这为固定参数可解性提供了有力证据。为了得出这些难度结果，本文引入了来自分割子图同构问题的归约方法。构建过程中使用了复杂的工具和填充边来强制解决方案结构，确保选择正确的子图精确对应于在输入图中按颜色切割顶点。

归约方法使用了基于素数的代数工具和精心设计的顶点映射来控制连通性模式。它利用构建图的组合属性来模拟分割子图同构问题中固有的选择约束。一个重要的概念性见解是“对偶”表述，即当几乎所有颜色都必须被切割时，复杂性才会出现，只有少数颜色被保留，从而需要对保留的颜色集进行指数级搜索。

通过将这些详细的归约方法与精细的复杂性论证相结合，作者得出了一个与已知最佳算法几乎一致的下界。因此，这项工作解决了关于全局标签最小割计算难度的一个重要未解决的问题，明确了它在多项式可解问题和NP难问题之间的位置。研究表明，虽然这个问题不太可能是NP难问题，但其复杂性本质上是准多项式的，并且在没有推进重大复杂性理论假设的情况下不太可能得到显著改进。

此内容由AI生成。了解更多