ハミルトン完成

グラフハミルトニアンを作成するためのエッジの追加

ハミルトン完備化問題とは、グラフをハミルトンにするためにグラフに追加するエッジの最小数を見つけることです。

この問題は、一般の場合、明らかにNP困難です（その解は、与えられたグラフがハミルトン閉路を持つかどうかを判定する NP完全問題に対する答えを与えるため）。関連する決定問題である、与えられたグラフにK個の辺を追加してハミルトングラフを生成できるかどうかを判定する問題はNP完全です。

さらに、ハミルトン完備化はAPX 複雑性クラスに属し、つまり、この問題に対して効率的な定比近似アルゴリズムが存在する可能性は低い。^[1]

この問題は、直列並列グラフ^[2]とそのサブグラフ^[3]（外平面グラフを含む）や、木の線グラフ^{[4] [5]や}サボテングラフ[ ⁶^] などの特定のグラフクラスでは多項式時間で解ける可能性があります。

ガマルニックらは、木上の問題を解く線形時間アルゴリズムを使用して、スパースランダムグラフをハミルトングラフにするために必要な漸近的なエッジ数を研究しました。^[7]

参考文献

^ Wu, QS; Lu, Chin Lung; Lee, Richard CT (2000)、「木構造上の重み付きハミルトン経路完成問題に対する近似アルゴリズム」、Lee, DT; Teng, Shang-Hua (編)、アルゴリズムと計算、第11回国際会議、ISAAC 2000、台北、台湾、2000年12月18～20日、議事録、Lecture Notes in Computer Science、第1969巻、Springer、pp. 156～ 167、doi :10.1007/3-540-40996-3_14、ISBN 978-3-540-41255-7
^ 高見沢健;西関剛; 斉藤暢 (1982)「直列並列グラフ上の組合せ問題の線形時間計算可能性」、Journal of the ACM、29 (3): 623– 641、doi : 10.1145/322326.322328、S2CID 16082154。
^ Korneyenko, NM (1994)、「グラフのクラスにおける組合せアルゴリズム」、離散応用数学、54 ( 2–3 ): 215– 217、doi : 10.1016/0166-218X(94)90022-1、MR 1300246
^ Raychaudhuri, Arundhati (1995)、「木の総区間数とその線グラフのハミルトン完備数」、Information Processing Letters、56 (6): 299– 306、doi :10.1016/0020-0190(95)00163-8、MR 1366337
^ Agnetis, A.; Detti, P.; Meloni, C.; Pacciarelli, D. (2001)、「木の線グラフのハミルトン完備数を求める線形アルゴリズム」、Information Processing Letters、79 (1): 17– 24、doi :10.1016/S0020-0190(00)00164-2、MR 1832044
^ デッティ、パオロ; メローニ、カルロ (2004)、「サボテンの線グラフのハミルトン完備数を求める線形アルゴリズム」、離散応用数学、136 ( 2–3 ): 197– 215、doi :10.1016/S0166-218X(03)00441-4、MR 2045212
^ Gamarnik, David; Sviridenko, Maxim (2005)、「スパースランダムグラフのハミルトン完備化」(PDF)、離散応用数学、152 ( 1–3 ): 139– 158、doi :10.1016/j.dam.2005.05.001、MR 2174199

[1] Wu, QS; Lu, Chin Lung; Lee, Richard CT (2000)、「木構造上の重み付きハミルトン経路完成問題に対する近似アルゴリズム」、Lee, DT; Teng, Shang-Hua (編)、アルゴリズムと計算、第11回国際会議、ISAAC 2000、台北、台湾、2000年12月18～20日、議事録、Lecture Notes in Computer Science、第1969巻、Springer、pp. 156～ 167、doi :10.1007/3-540-40996-3_14、ISBN 978-3-540-41255-7

[2] 高見沢健;西関剛; 斉藤暢 (1982)「直列並列グラフ上の組合せ問題の線形時間計算可能性」、Journal of the ACM、29 (3): 623– 641、doi : 10.1145/322326.322328、S2CID 16082154。

[3] Korneyenko, NM (1994)、「グラフのクラスにおける組合せアルゴリズム」、離散応用数学、54 ( 2–3 ): 215– 217、doi : 10.1016/0166-218X(94)90022-1、MR 1300246

[4] Raychaudhuri, Arundhati (1995)、「木の総区間数とその線グラフのハミルトン完備数」、Information Processing Letters、56 (6): 299– 306、doi :10.1016/0020-0190(95)00163-8、MR 1366337

[5] Agnetis, A.; Detti, P.; Meloni, C.; Pacciarelli, D. (2001)、「木の線グラフのハミルトン完備数を求める線形アルゴリズム」、Information Processing Letters、79 (1): 17– 24、doi :10.1016/S0020-0190(00)00164-2、MR 1832044

[6] デッティ、パオロ; メローニ、カルロ (2004)、「サボテンの線グラフのハミルトン完備数を求める線形アルゴリズム」、離散応用数学、136 ( 2–3 ): 197– 215、doi :10.1016/S0166-218X(03)00441-4、MR 2045212

[7] Gamarnik, David; Sviridenko, Maxim (2005)、「スパースランダムグラフのハミルトン完備化」(PDF)、離散応用数学、152 ( 1–3 ): 139– 158、doi :10.1016/j.dam.2005.05.001、MR 2174199