使用Meet-in-the-Middle算法的最小顶点覆盖问题

Question

我正在学习Meet-in-the-Middle算法，发现了以下练习：

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

我不知道如何做到这一点，只得到了以下提示：

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

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

- agassaa

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是图中边的数量。

- akashnil