algorithm - 是否有任何有效的算法可以找到无向图中最长循环的长度？

Question

我想知道是否有任何有效的算法可以找到图中最长循环的长度？

该图是一个无向图。

该算法不必告诉循环中的顶点是什么，只需告诉长度即可。

Answer 1

寻找图中最长循环的问题是NP-hard，因为解决这个问题可以回答“这个图是哈密尔顿图吗？”(是否它具有哈密尔顿循环)，这本身就是一个 NP 完全问题。
所以，确实，没有高效的算法可以做到这一点。
有一些基于矩阵乘法的方法可以在图中找到长度为 k 的循环。您可以在 this quesion 中找到有关使用矩阵乘法查找循环的说明。 .但请注意，矩阵乘法方法允许检测 2 个顶点之间给定长度的 walks，并且允许在 walk 中重复顶点。