ハミルトン路問題
グラフのすべての頂点を通る一筆書き (ハミルトン路) の存在を示す問題。NP完全。
グラフのすべての頂点と辺を通る一筆書きはオイラー路
オイラー路の存在は頂点の次数の偶奇を調べれば$ \Omicron(|V|)で判定できる
オイラー路のうち閉路のものはオイラー閉路で、これの存在判定もオイラー路と同様に$ \Omicron(|V|)でできる
ハミルトン路のうち閉路のものがハミルトン閉路
ハミルトン閉路の存在を示す問題がハミルトン閉路問題
3-SAT からの帰着
http://dopal.cs.uec.ac.jp/okamotoy/lect/2019/npc/handout05.pdf
https://scrapbox.io/files/665513b059604d001dca646f.png
上に変数の値を表すガジェット
https://scrapbox.io/files/665516eb54079d001da93be3.png
上下の辺が排他的に使われるので 0, 1 を表せる
下に各節を表すガジェット
節内にはリテラルの値を表すガジェット
リテラルの値は (A) により変数の値と排他的に関連付けられる
https://scrapbox.io/files/665513d4529c12001cb0fb80.png
https://scrapbox.io/files/6655182095f7e3001d7949d8.png
すべての頂点を通らなければならないため、真ん中の 4 点を必ず通らなければならない
真ん中に 4 つも点を置く必要はあるのか？
2 点で良いのでは？
https://scrapbox.io/files/665513c37c8248002248c3a4.png
左だけ通る($ (x_1,x_2,x_3)=(0,1,1))場合
https://scrapbox.io/files/66551a2ef634d7001c735cce.png