论文标题
全球标签最小限制的紧密的准多项式限制
A tight quasi-polynomial bound for Global Label Min-Cut
论文作者
论文摘要
我们研究了经典的全球最低切割问题的概括，称为全球标签最小剪辑（或有时是全球对冲的最小切割）：输入（多）图的边缘被标记（或分区为颜色类别或树篱），并删除同一标签（颜色或同一对冲）的所有边缘。问题要求以最低成本断开图表。 虽然已知该问题的$ ST $ -CUT版本是NP-HARD，但已知上述全局剪切版本承认是准杂种随机$ n^{o（\ log \ mathrm {opt}）} $ - 时间算法是由于Ghaffari，Karger，Karger和Panigrahi 2017]。他们认为这是``强有力的证据表明这个问题在p中''。我们表明事实并非如此。 We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time $(np)^{o(\log n/ (\log \log n)^2)}$ would contradict the Exponential Time Hypothesis, where $n$ is the number of vertices, and $p$ is the number of labels in输入。下边界的关键步骤是证明全局标签最低速率是W [1] - hard当通过未切割标签的数量参数时。换句话说，在制度中，几乎所有标签都需要切断图形连接的制度很困难。为了将这种下限变成准多项式时间下限，我们还需要重新审视Marx引起的框架[理论计算。 [2010]证明下限，假设通过模式的边缘数来通过子图同构问题进行指数时间假设。在这里，我们提供了此问题硬度的替代简化证明，该证明相对于参数的制度的选择更具用途。
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the $st$-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized $n^{O(\log \mathrm{OPT})}$-time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as ``strong evidence that this problem is in P''. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time $(np)^{o(\log n/ (\log \log n)^2)}$ would contradict the Exponential Time Hypothesis, where $n$ is the number of vertices, and $p$ is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the Subgraph Isomorphism problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters.
