スパースグラフ上の最短ハミルトニアンパス問題を解く方法は?

Problem: Given a positive-weighted
undirected graph, find the shortest path (in terms of total sum of
edges) that visits each node exactly once.

ノードのサブセット$ S $とS $のノード$ i に対して、$ D [S] [i] $は$ S $内で$ i
$で終わる最短パスの長さを示します。

SHP問題の一般的な解決策は、すべてのサブセット$ S $とすべてのノード$ i $に対して$ D [S] [i]
$を計算するための動的プログラミングを使用することです。 $ n $がノードの数ならば、この解の時間と記憶の複雑さはそれぞれ$
mathcal {0}(2 ^ nn ^ 2)$と$ mathcal {O}(2 ^ nn)$です。大きなグラフ(例えば$ 100
$ノードを持つ)では実現できません。

しかしながら、グラフが非常にまばらである(例えば、ノードがわずかな近隣しかない)場合、1つのはこれらの複雑さが大幅に低下すると期待する。非常に疎なグラフのためのSHPの解決方法や実装方法についての洞察を私が誰かから得ることができれば、とても感謝しています。
理論的な複雑さは必ずしも低いとはいえない実用的なアルゴリズムや実装を探していますが、最短のものを見つける前にハミルトニアンパスが存在するかどうかを確認することもできます。すばらしいです。

ご協力いただきありがとうございます!

ベストアンサー

確かに、Eppsteinは、すべての頂点の次数が最大で3であれば、TSPは時間$ O(1.26 ^
n)$で解くことができることを示しています。

David Eppstein:
  立方グラフのトラベリングセールスマン問題。
  J.グラフアルゴリズムAppl。 11(1):61-81(2007)

LiśkiewiczとSchuster(2014)による$ O(1.255 ^
n)$のような、この結果の若干の改良も知られています。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です