algorithm - 图中的非汉密尔顿路径消除

Question

假设我们有一个随机图。如何以最少的步数删除或添加边，以使结果图中的每条边都位于汉密尔顿路径中？

如果有人可以分享任何想法，我将不胜感激。

Answer 1

由于Angluin–Valiant ，有一种算法可以在某些随机图中快速找到 Hamilton 路径。也许您可以为图中的每条边重复运行它，以将该边扩展到汉密尔顿路径，并在失败时添加边。