使用中间相遇的最小顶点覆盖
Minimal Vertex Cover using Meet-in-the-Middle
我在研究中间相遇算法，发现了以下练习：
给定一个有n个节点的图（n <= 30），找出一个顶点数最少的集合，使得图中的每条边至少有一个节点在集合中。
我不知道该怎么做，我得到的唯一提示是
复杂度 O(3^(n/2))
你能解释一下这个想法吗？
从图中取出一条边(u1, v1)，去掉所有与它共享一个顶点的边。再取出一个(u2, v2), ...继续直到图的其余部分没有边。
你最终得到许多顶点对
(u1, v1), (u2, v2), ..., (uk, vk)
其余的顶点是：
w1, w2, ..., wm
调用第一组顶点配对顶点，第二组未配对顶点。注意，2k + m = n，原始图中不成对的顶点之间没有边。
顶点覆盖必须包含 u1、v1 或 both。每对 (uj, vj) 有 3 个选择。考虑将成对顶点包含到顶点覆盖中的所有 3^k 方法。
对于这些配置中的每一个，一个不成对的顶点 wi 将被包含在封面中当且仅当它的至少一个邻居不在封面中（注意每个 wi的邻居是成对的顶点，所以它们是否被包含是已知的）。
对于每个3^k选择的成对顶点，根据上述标准包括未成对的顶点，然后验证成对顶点之间的每条边都有来自覆盖的入射顶点，如果是，则它是一个候选封面集。取一个最小尺寸的候选覆盖集作为输出。
上述算法的总体复杂度为 O(3^(n/2)E)，其中 E 是图中的边数。
我在研究中间相遇算法，发现了以下练习：
给定一个有n个节点的图（n <= 30），找出一个顶点数最少的集合，使得图中的每条边至少有一个节点在集合中。
我不知道该怎么做，我得到的唯一提示是
复杂度 O(3^(n/2))
你能解释一下这个想法吗？
从图中取出一条边(u1, v1)，去掉所有与它共享一个顶点的边。再取出一个(u2, v2), ...继续直到图的其余部分没有边。
你最终得到许多顶点对
(u1, v1), (u2, v2), ..., (uk, vk)
其余的顶点是：
w1, w2, ..., wm
调用第一组顶点配对顶点，第二组未配对顶点。注意，2k + m = n，原始图中不成对的顶点之间没有边。
顶点覆盖必须包含 u1、v1 或 both。每对 (uj, vj) 有 3 个选择。考虑将成对顶点包含到顶点覆盖中的所有 3^k 方法。
对于这些配置中的每一个，一个不成对的顶点 wi 将被包含在封面中当且仅当它的至少一个邻居不在封面中（注意每个 wi的邻居是成对的顶点，所以它们是否被包含是已知的）。
对于每个3^k选择的成对顶点，根据上述标准包括未成对的顶点，然后验证成对顶点之间的每条边都有来自覆盖的入射顶点，如果是，则它是一个候选封面集。取一个最小尺寸的候选覆盖集作为输出。
上述算法的总体复杂度为 O(3^(n/2)E)，其中 E 是图中的边数。