找出多重图中每个顶点都在集合中或与集合中包含的至少一个顶点相连的最小顶点集的大小

Find the size of smallest set of vertices that every vertex in multigraph is in set, or is connected with at least one vertex contained in set

对于给定的多重图，找到最小顶点集的大小，使得多重图中的每个顶点都在集合中，或者与集合中包含的至少一个顶点相连。

它能比 O(2^n) 更好地解决吗？

您可能可以稍微优化一下，但一般来说 - 您无法获得次指数时间，这是 Vertex Cover Problem, which is known as NP-Hard，这意味着没有已知的多项式解并且普遍认为存在none.

如前所述，您无法在多项式时间内解决此问题，因为它是 NP-Hard。但是，您可以编写一个在 O(n^2) 中运行的 2 近似算法（您可以在 google 上轻松找到）。