In an undirected edge-labeled graph, let $n$ denote the number of vertices and $p$ the number of labels. Previous work showed that, under the Exponential Time Hypothesis (ETH), there is no deterministic algorithm with running time $$ (np)^{o\left(\frac{\log n}{(\log\log n)^2}\right)} $$. In this paper, we provide a deterministic reduction that strengthens this conditional running-time lower bound to $$ (np)^{o\left(\frac{\log n}{\log\log n}\right)} $$.
Blogger's Review: This paper significantly enhances the running time lower bound for the global label min-cut problem through an improved reduction method, advancing the depth and breadth of theoretical computer science research in graph algorithms.