algorithm - 有向图的最小支配集

Question

http://en.wikipedia.org/wiki/Dominating_set

现在，我有个想法要找到它，我需要你的意见

第一：
在图上创建一个秩系统，每个顶点都有一个秩。顶点等级为：
2*[出边数] - [入边数]

第二：
改变DFS算法：使其也返回生成林上所有根的组（不改变复杂度）

算法：
1. 以所有顶点作为最小支配集
开始 2. 以起始顶点：排名最高的顶点运行 DFS
3. 查看生成森林上的根，获取最小支配集的列表并删除每个顶点不是生成森林上的根
4. 重复 2-3 与保留在最小支配集上的下一个最高排名的顶点
5. 当您在最小支配集上的每个顶点上运行 DFS 时停止
6. 将其返回

我使用 adj-list，所以 DFS 是 O(|V| + |E|) 你觉得这个算法怎么样？它会起作用吗？我可以做得更好吗？该算法的摊销最坏情况是什么？

Answer 1

它会起作用吗？

不，一个简单的反例如下图：

排名是[1:6, 2:-1, 3:1, 4:-1, 5:-1].在第 2 步，您从顶点运行 DFS1.它是生成林中的唯一根，因此在第 3 步中，您删除所有其他顶点并返回。但是，这不是一个主导的集合！5既不在支配集中也不与支配集中的节点相邻。

该算法的摊销最坏情况是什么？

最坏的情况是 O(|V|+|E|+k ² )，其中 k 是返回集的大小。您将在第一次通过时删除除根以外的所有内容，因此接下来的 O(k) 次循环将仅花费 O(k) 次。

我能做得更好吗？

是的，在正确性和速度方面。删除当前顶点的所有邻居，然后继续移动到仍然在集合中的下一个顶点。这只需要 O(|V|+|E|)。

您似乎试图获得更接近全局最小值的东西；为此，我建议查阅有关“最小支配集逼近”的文献。