algorithm - 使用中间相遇的最小顶点覆盖

Question

我在研究中间相遇算法，发现了以下练习:

给定一个包含 n 个节点(n <= 30)的图，找出一个顶点数最少的集合，使得图中的每条边至少有一个节点在该集合内。

我不知道该怎么做，我得到的唯一提示是

复杂度 O(3^(n/2))

你能解释一下这个想法吗？

Answer 1

从图中取出一条边(u1, v1)，移除所有与它共享一个顶点的边。取出另一个(u2, v2)，...继续直到图的其余部分没有边。

你最终得到了一些顶点对

(u1, v1), (u2, v2), ..., (uk, vk)

其余的顶点是:

w1, w2, ..., wm

将第一组顶点称为配对顶点，将第二组未配对顶点。注意，2k + m = n，原始图中不成对的顶点之间没有边。

顶点覆盖必须包含u1、v1 或两者。每对 (uj, vj) 有 3 个选择。考虑所有 3^k 方法将成对的顶点包含到顶点覆盖中。

对于这些配置中的每一个，一个不成对的顶点 wi 将被包含在封面中当且仅当它的至少一个邻居不在封面中(注意每个 wi 的邻居是成对的顶点，因此它们是否包含在内是已知的)。

对于每个 3^k 选择的成对顶点，根据上述标准包括未成对的顶点，然后验证成对顶点之间的每条边都有来自覆盖的入射顶点，如果是，这是一个候选封面集。将最小尺寸的候选覆盖集之一作为输出。

上述算法的总体复杂度为 O(3^(n/2)E)，其中 E 是图中的边数。