汉密尔顿路径的修改

Question

虽然我知道 汉密尔顿路径问题 是$ { sf np} $ - 完整，我认为可以在多项式时间内解决以下变体：

给定带有顶点的平面图$ v $，edge set $ e $，start node $ s $和目标节点$ f $，我们的任务是找到从$ s $到$ f $的汉密尔顿路径或写这条路径不存在。

最后一个条件: ：在路径中，除了选择直接连接的顶点外，我们还可以选择与一个邻居相关的那些。

编辑: ：任何顶点的度数最多为四个（$ deg（v_i） le 4 $）。

有人有任何想法如何证明可以在多项式时间内解决这一问题吗？

可能很难理解，所以我将举一个例子：

在左侧的示例中，对于$ s = 1，f = 12 $，解决方案是路径$ 1、11、8、7、5、9、2、10、10、4、6、3、12 $。

在正确的示例中，对于$ s = 1，f = 15 $，没有哈密顿路径。

Answer 1

也许这个问题仍然是NP完整的；此减少应起作用：给定平面图$ g $和两个节点$ s $和$ t $（启动和结尾），以这种方式将其扩展到新的图$ g'$：对于每个节点$ u $ of $ $ $ g $添加两个节点$ u_1，u_2 $和两个边缘：$（u，u_1），（u_1，u_2）$（非正式地添加一个 尾巴 用两个新节点制成）。

只有两种方法可以通过有效的汉密尔顿路径（即覆盖三个节点）穿越三个节点小工具：

a）$ out rightarrow u rightarrow u_2 rightarrow u_1 rightarrow ut $ and turvess

b）$ out rightarrow u_1 rightarrow u_2 rightarrow u rightarrow ut $ $

在这两种情况下，节点$ u $都必须遍历，并且不能在路径的另一部分重复使用。

现在，为了强制每个节点中的两个遍历之一，将两个尾巴添加到$ s $：$（s，s_1），（s_1，s_2）$和$（s，s_3），（s_3，s_4）$并选择为$ g'$ the节点$ s_1 $的启动节点。遍历和留下$ S $的唯一方法是$ s_1 rightArrow s_2 rightarrow s rightarrow s4 rightarrow s3 rightarrow uterarow ut $。这迫使$ g'$的所有剩余节点（小工具）上遍历（a）。选择$ t_2 $作为$ g'$中的结尾节点。

因此，原始图$ g $具有从$ s $到$ t $的汉密尔顿路径，并且仅当$ g'$具有“修改”（允许一个节点跳跃）的汉密尔顿路径从$ s_2 $到$ t_2 $。

编辑：

• 如果$ deg（v_i） leq 4 $上述还原仍然有效，因为即使在平面立方图中，哈密顿路径也是NP完整的。在Planr Cubic Graph $ deg（v_i）= 3 $中，因此可以用如上所述的尾巴扩展节点。如果启动节点具有3度，则只需添加另一个节点$ s'$，一个边缘$（s，s'）$，然后将两个尾巴添加到$ s'$。

• 但是，如果$ deg（v_i） leq 3 $，那么问题落在$ mathsf {p} $中，以下算法 应该 工作（但我没有考虑太多）：

计算从$ s $到$ t $的最短路径：$ s rightarrow u_1 rightarrow ... rightArrow u_m rightarrow t $，然后使用每个节点的深度搜索来扩展路径；这将导致一棵具有最短路径的跨越树作为“骨干”。对于最短路径的每个$ u_i $，只有一个分支$ u_i，b_1，b_2，...，b_k $（因为$ v_i $的度数为$ leq 3 $），并且可以使用跳跃覆盖：

$ u_i> b_2> b_4> ...> b_k> b_k> b_ {k-1}> ...> b_3> b_1> u_ {i+1} $如果$ k $偶数
$ u_i> b_2> b_4> ...> b_ {k-1}> b_k> b_k> b_ {k-2} ...> b_3> b_1> u_ {i+1} $如果$ k $是奇数

唯一的问题是，如果$ s $和/或$ t $具有学位3。在这种情况下，必须仅使用$ s $的一个事件边缘重复几次（最终只有一个$ t $的事件边缘） 。

为了正式证明算法是正确的，必须证明每条汉密尔顿路径（跳高）从$ s $到$ d geg（v_i） leq 3，deg（s）= 1，deg（t） ）= 1 $图形可以转换为上述形式的哈密顿路径（带有跳跃）（从最短路径的跨越树）。它不是直接的，但看起来直觉（但也许我只是在徘徊:)。