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

Question

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

输入:一个可能是有向或无向的图

输出:此图是否至少存在 2 条边不相交的哈密顿路径？边不相交意味着没有一条边被两条路径共享。

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

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

Answer 1

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

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

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

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

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

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

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