在一幅无向边标记图中，设 $n$ 为顶点数，$p$ 为标签数。先前的研究表明，在指数时间假设（ETH）下，无法找到运行时间为 $$ (np)^{o\left(\frac{\log n}{(\log\log n)^2}\right)} $$ 的确定性算法。本文通过一个确定性归约，进一步加强了这一条件运行时间下界，提升至 $$ (np)^{o\left(\frac{\log n}{\log\log n}\right)} $$。
博主点评： 本文通过改进的归约方法，显著提高了全局标签最小割问题的运行时间下界，进一步推动了理论计算机科学在图论算法方面的研究深度与广度。