求图中哈密顿步行的多项式时间算法

是否存在用于在图中找到哈密顿步行的多项式时间算法？

我的算法是N阶乘,而且非常慢.

1> ShreevatsaR..：

---

一般来说,由于哈密顿路径问题的(决策版本)是NP完全的,你不可能希望得到一个多项式时间算法来寻找哈密顿路径.您可以使用通常的N来略微提速!→N ² 2 ^N动态编程技巧(计算hp [v] [w] [S] ="是否存在具有端点v和w且其顶点是子集S"的路径,用于每个子集S和每两个顶点v和w使用DP),但这仍然是指数级的.

然而,有许多特殊类型的图表,哈密尔顿路径将始终存在,并且可以很容易地找到它们(参见Posa,Dirac,Ore等的工作)

例如,以下情况属实:如果图的每个顶点的度数至少为n/2,则图形具有哈密顿路径.事实上你可以在O(n ²)中找到一个,或者如果你更巧妙地在IIRC甚至O(n log n)中找到它.
[粗略草图:首先,只是在一些"哈密顿量"循环中连接所有顶点,如果边缘实际上在图中,则不要注意.现在对于周期中实际上不在图中的每个边缘(v,w),考虑周期的其余部分:v ... w.当deg(v)+ deg(w)> = n时,列表中存在连续的x,y(按此顺序),使得w是x的邻居,v是y的邻居.[证明:考虑{w的所有邻居的集合}和{v邻居列表中所有后继者的集合}; 它们必须交叉.]现在将你的周期[v ... xy ... wv]更改为[vy ... wx ... v]而不是它至少有一个无效的边缘,所以你最多需要n次迭代以获得真正的哈密顿循环.更多细节在这里.]

顺便说一下:如果你要找的只是一次包含每一条边的步行,它就叫做欧拉步行,对于有它的图形(奇数度的顶点数是0或2),可以很容易地在多项式中找到时间(快).

2> Daniel Spiew..：

---

你刚问了百万美元的问题.找到汉密尔顿路径是NP完全问题.一些NP难问题可以使用动态编程在多项式时间内解决,但(据我所知)这不是其中之一.

---

对于任何NP完全问题,没有已知的多项式时间算法; 如果其中一个问题只有一个算法,那么所有其他NP完全问题都可以在多项式时间内减少到它.我认为hazzen所指的是一些问题,例如背包,在多项式时间内可以很好地近似.但是,越接近完美近似,您从多项式得到的越远.