※ 引述《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