作者c910335 (達人)
看板Prob_Solve
標題Re: [閒聊] Hamiltonian Cycle Problem is in P？
時間Fri May 28 20:25:05 2021
※ 引述《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/m.aspx?n=bbs/Prob_Solve/M.1622204710.A.2A2.html
1F：推 alan23273850: 大大真的是猴腮雷，給你一個讚，應該請你去寫review 05/29 23:14
2F：→ alan23273850: 要是這篇 paper 最後被 accept 就好笑了 05/29 23:14
3F：→ expiate: 感謝大大花時間分享 05/30 14:51
※ 編輯: c910335 (140.113.230.194 臺灣), 06/03/2021 22:55:27
4F：推 kyrie77: 推 07/12 20:03