使用oracle机器在多项式时间内找到哈密顿路径

Question

假设你有一个可以在多项式时间内确定某个图中是否存在哈密尔顿路径的Oracle。（提醒：哈密尔顿路径问题属于NPC问题）。

描述如何利用该Oracle来在多项式时间内< strong>找到一个图中的哈密尔顿路径。

任何想法？

- Shlomi Kriheli

---

这可能更适合计算机科学堆栈交换 - 这不是关于编程。 - Arya McCarthy

Answer 1

哈密顿路径是指恰好经过每个顶点一次的路径。

如果您拥有一个预言机，可以测试逐个删除每条边。如果预言机表示仍然存在路径，则保留删除的边，否则恢复该边并尝试下一条边。

一旦您遍历了所有边，剩下的就是哈密顿路径。

- Peter de Rivaz

---

我不确定我理解了。当你说我们可以依次删除每条边时，我怎么知道我一定可以从手头的图中删除一条边？我的意思是，在某些图中，即使我尝试删除一条边，仍然可能没有哈密顿路径。那么我们为什么要删除边呢？ - Shlomi Kriheli

我们的想法是从一个有很多边的图开始。预言家告诉我们这个图有一条哈密顿路径，但没有告诉我们在哪里。我们试图通过去除边来尽可能简化图形，同时保留路径。一旦我们完成了去除边的工作，我们将得到一个非常简单的链式图，它必须等于哈密顿路径。你说得对，有时候去掉一条边会导致路径消失，但在这些情况下，我们需要把边放回去并尝试其他边。 - Peter de Rivaz

因此，我们确实可以得到一张拥有大量边缘的图表，而我们确定该图表包含哈密顿路径，但我们不知道其具体位置。如您所述，去除这些边缘最终将只留下属于哈密顿路径的边缘，对吗？ - Shlomi Kriheli

Answer 2

如果图中有n-1条边，我们就完成了（它必须是一条链。否则，就没有哈密顿路径）。

否则，我们可以删除一些边。让我们遍历所有的边。如果在没有固定边的图中仍然存在路径，我们就可以删除它并继续前进。

这个解决方案需要O(m^2)个oracle查询，因此它在多项式时间内工作。

- kraskevich