在有向图中近似最长的周期

Question

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

Answer 1

由于有向图中最长的有向路径问题不能在任何n^(1-epsilon)的系数epsilon > 0内的多项式时间内逼近，因此我们可以快速得出结论，除非有向图中最长的循环也是如此P ＝ NP（source）。

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

结论：在有向图中最长周期问题没有alpha-逼近。