algorithm - グラフ内の非ハミルトン パス消去

Question

ランダムグラフがあるとします。結果のグラフのすべてのエッジがハミルトン パスになるように、最小ステップ数でエッジを削除または追加するにはどうすればよいでしょうか?

誰かが何かアイデアを共有できれば、本当に感謝しています。

Answer 1

Angluin–Valiantにより、特定のランダム グラフでハミルトン パスをすばやく見つけるアルゴリズムがあります。おそらく、グラフの各エッジに対して繰り返し実行して、そのエッジをハミルトン パスに拡張し、それが失敗したときにエッジを追加することができます。