有向图中最长圈的逼近

Question

在有向图中寻找最长圈(循环i是指没有节点重复的循环)是一个NP难问题，否则我们可以判断该图是否为Hamiltonian图。我的问题是:对于这个问题有任何α-逼近多项式算法吗？

Answer 1

由于有向图中的最长有向路径问题不能在n^(1-epsilon)因子的多项式时间内对任意epsilon > 0进行逼近，我们可以快速地推导出有向图中的最长圈也是如此，除非P=NP (来源)。

您可以按以下方式进行减缩：

选择一个顶点v，将v复制到v1和v2中，复制所有相关的弧。现在找到从v1到v2的最长有向路径。

对图中的所有顶点都这样做。这给出了图中最长的有向圈。

结论:有向图的最长圈问题在多项式时间内不存在alpha-approximation (当然P=NP除外)。