※ 引述《alan23273850 (God of Computer Science)》之铭言： : 最近 arxiv 上出现了一篇很有趣的 paper： : https://arxiv.org/abs/2105.07608 : 各位的看法如何呢？ 先打个预防针 我并不保证我的理解是正确的 只是在这里说说我的看法 这几天花了点时间读这篇 我的结论是：这篇是错的 而错误的地方是尽管演算法本身是多项式时间 但它并没有正确的判定 Hamiltonian Cycle 是否存在 先来稍微说明一下他的演算法 首先任意决定一个起点 u 拆成两个节点 u1, u2 这两个点都有连到原本的邻居 於是新图上的 Hamiltonian Path 一定会以这两个节点为起点终点 这两点接起来就会变回原图的 Hamiltonian Cycle 这部分没有任何问题 演算法主要是用 Dynamic Programming 来设计 定义 PS[v, i, j] = v 当终点 长度 i 以下的最长简单路径 可以用到的倒数第 i - j 个节点的集合 PS[v, i] = 对於所有可能的 0 <= j <= i 把 PS[v, i, j] 串起来 i.e. PS[v, i] = { PS[v, i, 0], PS[v, i, 1], ..., {v} } 注意由於 v 一定是终点所以任何 PS[v, i, i] = {v} 另外由於起点和终点已经固定是 u1 和 u2 了 所以当 1 <= i < n 的时候 PS 只考虑 u1 u2 以外的点 当 i = 0 的时候 PS 只考虑 u1 当 i = n 的时候 PS 只考虑 u2 （这里省略了 Path Hologram 的说明因为很麻烦） 於是如果能正确定义 DP 的转移式 最後算出 PS[u2, n, 0] 如果刚好是 {u1} 就表示这张图存在 u1 到 u2 的 Hamiltonian Path 也就是原图存在 Hamiltonian Cycle 对於一条边 v -- w 当我们要用 PS[v, i - 1] 来更新 PS[w, i] 的时候 会分成两个 case： 1. 如果 PS[v, i - 1] 里并没有 w 也就是说最後面直接接上 w 也还是简单路径 可以很单纯的用 PS[v, i - 1] + {w} 来更新 PS[w, i] （保留比较长的，如果一样长就每层各别联集） 2. 如果 PS[v, i - 1] 有 w 那我们就必须先把 PS[v, i - 1] 里的 w 去掉 并且简单路径上必须经过 w 的其他节点也去掉（看一下论文 Figure 1 就懂了） 才能用 PStemp[v, i - 1] + {w} 来更新 PS[w, i] （由於去掉 w 之後的结果并没有要存回 PS[v, i - 1] 所以用 PStemp[v, i - 1] 来表示去掉 w 之後的 PS[v, i - 1]） 我认为问题就出在这第二个 case 考虑 K5（五个点的完全图）+ 一个分离节点的 case 令其节点集合为 {a, b, c, d, e} + {f} 首先把 a 拆成 a1, a2 当我们要用 PS[b, 4] 来更新 PS[c, 5] 的时候 PS[b, 4] 明显为 {{a1}, {c, d, e}, {c, d, e}, {c, d, e}, {b}} 可以发现中间有三个 c 需要去掉 於是去掉 c 得到 PStemp[b, 4] = {{a1}, {d, e}, {d, e}, {d, e}, {b}} 後面再接上 c 变成 PStemp[c, 5] = {{a1}, {d, e}, {d, e}, {d, e}, {b}, {c}} 到这里各位应该察觉到问题所在了 PStemp[c, 5] 所得到长度 6 的路径 其中有三个位置在抢两个节点 但是该论文的演算法并没有办法察觉这件事 於是会错误地判断这张图存在 Hamiltonian Cycle 其实在我看来该论文似乎也有考虑过类似的情形 所以避免掉有两个以上的位置抢一个节点了（CM operator Line 19） 但他没考虑到的是：三个以上的位置抢两个节点、四个以上的位置抢三个节点、以此类推 以上就是我对於这篇的看法 再说一次结论：这篇论文是错的 该演算法并没有正确的判定一张图是否存在 Hamiltonian Cycle -- ︿︿ ︿︿ ︿︿ ︿︿ ︿︿ ︿︿ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╳ キ ╳ ╳ ズ ╳ ╳ ラ ╳ ╳ ン ╳ ╳ ダ ╳ ╳ ム ╳ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ╲ ╱╱ ﹀﹀ ﹀﹀ ﹀﹀ ﹀﹀ ﹀﹀ ﹀﹀ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.230.194 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1622204710.A.2A2.html ※ 编辑: c910335 (140.113.230.194 台湾), 06/03/2021 22:55:27