最大切割图形图

Question

以下问题与 最大切割问题 在 立方图. 。在 这个 调查论文定理6.5州

可以在多项式时间内计算出最大的立方图切割

浏览其他一些相关结果（例如 这个 苏打纸）的印象是，即使对于立方实例，这个问题实际上是NP完成的。特别是，最后一篇论文指出，如果该图是亚立方体，则确实如此。

那让我想知道..发生了什么事？调查文件（以及其中引用的结果）是否有缺陷，还是我缺少某种意义？

Answer 1

最大切割与最大切割（最大切割）不同。在最大切割中，目标是找到切割最大边缘数量的切割。在最大切割中，目标是找到一个局部最大值：切割，使任何单个顶点的侧面切换不会导致剪切更多的边缘。存在这样的切割，因为最大切割也最大。但是，找到最大切割显然比仅找到最大切割要困难。