Re: [閒聊] Hamiltonian Cycle Problem is in P?

看板 Prob_Solve
作者
時間
留言 4則留言,3人參與討論
推噓 2  ( 2推 0噓 2→ )
討論串 2
※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1622204710.A.2A2.html
1Falan23273850: 大大真的是猴腮雷,給你一個讚,應該請你去寫review 05/29 23:14
2Falan23273850: 要是這篇 paper 最後被 accept 就好笑了 05/29 23:14
3Fexpiate: 感謝大大花時間分享 05/30 14:51
※ 編輯: c910335 (140.113.230.194 臺灣), 06/03/2021 22:55:27
4Fkyrie77: 推 07/12 20:03

完整討論串

2 >> Re: [閒聊] Hamiltonian Cycle Problem is in P?
4 prob_solve 2021-05-28 20:25