如何证明两个顶点之间最长路径的NP完整性依赖汉密尔顿NP-HARD问题

Question

我有这个问题：我有一个无向图g（v，e）（其中v=顶点集，e=边缘集）。考虑两个顶点s和t：

之间的最大路径

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

.

简单路径是没有任何重复的顶点的路径，即，只能访问每个顶点一次。路径的长度从其组成的边缘给出。

所以我如何表明LPAP是使用HAMILTON PATH问题作为NP-HARD问题作为参考的NP-CHILL问题的NP-完整的问题？

Answer 1

欢迎来到该网站！让 $ g=（v，e）$ 是一个无向图。 如果 $ g $ 是hamiltonian，那么存在一个简单的周期 $ c $ 在 $ g $ 包含每个顶点，即 $ c $ 是 $ | v | $ 。 请注意，如果删除任何边缘 $ Vw $ 从 $ c $ ，您最终会有一条路径长度 $ | v | - 1 $ $ v $ 和 $ w $ 。 相反，如果你找到一个简单的道路 $ p $ 长度 $ | v | - 1 $ 两个顶点 $ v，w $ 通过边缘连接，您可以添加边缘 $ VW $ 到 $ p $ 获取汉密尔顿循环（如 $ p $ 不能包含 $ vw $ 由于是一个简单的路径）。 还观察到<跨越类=“math-container”> $ v $ 和 $ w $ 只要它们连接边缘。

所以我们可以获得以下减少： 从某些图 $ g=（v，e）$ ，选择一些边缘 $ vw \在e $ 并删除它以获取新图 $ g'=（v，e \ setminus \ {vw \}）$ 。 使用我们所做的观察结果，它遵循<跨度类=“math-container”> $ g'$ path $ p $ $ v $ 和 $ w $ 长度 $ | v | - 1 $ 如果且仅当添加 $ Vw $ 到 $ p $ 产生汉密尔顿人循环在原始图 $ g $ 。 作为 $ g'$ 可以从 $ g $ 在多项式时间中计算，我们有多项式减少< Span Class=“math-container”> $ \ mathrm {hamiltonian cycle} \ leq_ \ mathsf {p} \ mathrm {long path} $ ，从而显示您的问题是 $ \ mathsf {np} $ -hard（因为 $ \ mathrm {hamiltonian cycle} $ 是 $ \ mathsf {np} $ -hard已经）。

要显示 $ \ mathrm {long path} $ 在 $ \ mathsf {np} $ 我们注意到，图表中的路径可以有效地编码为其边的列表，并检查字符串实际上对图中的路径进行了编码，然后计算边缘的数量，以确定它是否足够长，可以在多项式中完成。时间。

因此，

我们发现 $ \ mathrm {long path} $ 是 $ \ mathsf {np} $ -complete。