algorithm - 显示不相交哈密顿路径的 np 完备性

Question

考虑不相交哈密顿路径问题：

输入：可以有向或无向的图

输出：该图是否存在至少 2 个边不相交的哈密顿路径？边不相交意味着两条路径不共享一条边。

证明不相交哈密顿路径是 np 完全的。

有人告诉我这个问题是 np-complete，但我无法证明它是 np-hard。我尝试将原始的哈密顿路径和哈密顿循环简化为这个问题，但我想不出解决方案。

标签： algorithmcomputer-sciencenp-completenp-hardhamiltonian-path

Answer 1

我想出了以下减少，不确定它是否最简单，但它很简单。

假设 G 是对应于 HP 实例的无向图。现在用以下方式构造一个新的图 G'：

• 保持 G 的每个顶点。
• 对于 G 中的每条边 (u,v)，创建 4 个额外的顶点并按以下方式连接它们：

现在很容易看出，如果 G 有一条哈密顿路径，则 G' 将有两条边不相交的哈密顿路径，因为每条边都被某个子图替换，该子图本身有两条边不相交的哈密顿路径（直走或走弯曲边）。如果 G' 有一个 HP，那么 G 也有，因为一旦你进入对应于原始边之一的子图，你别无选择，只能在另一端离开它，这对应于取 G 中的原始边。唯一可能发生的“问题”是路径是否在这些子图中开始或结束，但是我们可以忽略内部路径的一小部分，仍然获得 G 的 HP。

注意 G' 有一个 HP => G 有一个 HP => G' 有两个边缘不相交的 HP。因此，G 有一个 HP <=> G' 有两个边缘不相交的 HP。

转换显然可以在多时间内完成，因此您的问题是 NP-Hard。

有向情况类似，只需相应地引导转换图中的边即可。