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