这里有人知道是否有可能消除无向和未加权图(n顶点(中的所有周期，以最小化移除顶点的数量的方式删除顶点，O(n^2)？
在最坏的情况下，图形可能是一个完整的图形。
如果可能，我该怎么做？如果不是，为什么？
谢谢
获取任何无向、未命名的图形，并将所有边加倍，以便在每对相邻顶点之间有一个循环。
现在，消除所有周期的最小顶点集也是原始图和修改图的最小顶点覆盖率。 见 https://en.wikipedia.org/wiki/Vertex_cover
找到最小顶点覆盖是一个 NP 困难问题，所以你的问题也是 NP 困难的。
如果您不想允许双边，则可以添加虚拟顶点来保持新边，您的问题仍然可以解决顶点覆盖。
这个问题被称为反馈顶点集，不幸的是它是NP困难的，这意味着没有人知道解决它的多项式时间算法。