显示不相交哈密顿路径的 np-完整性
Show np-completeness of Disjoint Hamiltonian Path
考虑不相交的哈密顿路径问题：
输入：可能是有向或无向的图
输出：此图是否至少存在 2 条边不相交的哈密顿路径？
边不相交意味着没有一条边被两条路径共享。
证明不相交哈密顿路径是 np-完全的。
有人告诉我这个问题是 np-complete，但我无法证明它是 np-hard。我尝试将原来的哈密顿路径和哈密顿循环简化为这个问题，但我想不出解决方案。
我想出了以下归约，不确定它是否最简单但很简单。
假设G是对应于HP实例的无向图。
现在按以下方式构造一个新图 G'：
- 保留 G 中的每个顶点。
- 对于 G 中的每条边 (u,v)，创建 4 个额外的顶点并按以下方式连接它们：
现在很容易看出，如果G有一条哈密顿路径，G'就会有两条边不相交的哈密顿路径，因为每条边都被某个子图替换了，而这个子图本身有两条边不相交的哈密顿路径（直走）或采用弯曲的边缘）。如果 G' 有 HP，那么 G 也有 HP，因为一旦你进入与原始边之一对应的子图，你别无选择，只能在另一端离开它，这对应于获取 G 中的原始边。唯一可能发生的 "problem" 是如果路径在这些子图中的一个内部开始或结束，但是我们可以忽略内部路径的一小部分并仍然获得 G 的 HP。
注意 G' 有一个 HP => G 有一个 HP => G' 有两个边不相交的 HP。因此，G 有一个 HP <=> G' 有两个边不相交的 HP。
转换显然可以在多时间内完成，因此你的问题是NP-Hard。
有向情况类似，只需相应地定向变换图中的边即可。
考虑不相交的哈密顿路径问题：
输入：可能是有向或无向的图
输出：此图是否至少存在 2 条边不相交的哈密顿路径？ 边不相交意味着没有一条边被两条路径共享。
证明不相交哈密顿路径是 np-完全的。
有人告诉我这个问题是 np-complete，但我无法证明它是 np-hard。我尝试将原来的哈密顿路径和哈密顿循环简化为这个问题，但我想不出解决方案。
我想出了以下归约，不确定它是否最简单但很简单。
假设G是对应于HP实例的无向图。 现在按以下方式构造一个新图 G'：
- 保留 G 中的每个顶点。
- 对于 G 中的每条边 (u,v)，创建 4 个额外的顶点并按以下方式连接它们：
现在很容易看出，如果G有一条哈密顿路径，G'就会有两条边不相交的哈密顿路径，因为每条边都被某个子图替换了，而这个子图本身有两条边不相交的哈密顿路径（直走）或采用弯曲的边缘）。如果 G' 有 HP，那么 G 也有 HP，因为一旦你进入与原始边之一对应的子图，你别无选择，只能在另一端离开它，这对应于获取 G 中的原始边。唯一可能发生的 "problem" 是如果路径在这些子图中的一个内部开始或结束，但是我们可以忽略内部路径的一小部分并仍然获得 G 的 HP。
注意 G' 有一个 HP => G 有一个 HP => G' 有两个边不相交的 HP。因此，G 有一个 HP <=> G' 有两个边不相交的 HP。
转换显然可以在多时间内完成，因此你的问题是NP-Hard。
有向情况类似，只需相应地定向变换图中的边即可。