algorithm - 有向图中的近似最长循环

Question

在有向图中找到最长的循环（循环我的意思是没有节点重复的循环）是一个 NP 难题，否则我们可以判断该图是否是哈密顿量。我的问题是：这个问题是否有任何 alpha 逼近多项式算法？

Answer 1

由于有向图中的最长有向路径问题不能在多项式时间内逼近n^(1-epsilon)for any的因子epsilon > 0，因此我们可以快速推断出有向图中的最长循环也是这种情况，除非 P=NP ( source )。

您可以按如下方式进行缩减：
选择一个顶点v，复制v到v1andv2中，同时复制所有相关的弧。v1现在找到从到的最长有向路径v2。
对图中的所有顶点执行此操作。这为您提供了图中最长的有向循环。

alpha结论：对于有向图中的最长循环问题，多项式时间没有近似值（当然，除非 P = NP）。